Year: 2021

Abstract:
Cooperative multi-agent reinforcement learning (MARL) is making rapid progress for solving tasks in a grid world and real-world scenarios, in which agents are given different attributes and goals. For example, in Starcraft II battle tasks, agents are initialized with the various move, defense, and attack abilities according to their unit types. Current researchers tend to treat different agents equally and expect them to form a joint policy automatically. However, ignoring the differences between agents in these scenarios may bring policy degradation. Accordingly, in this study, we quantify the agent’s difference and study the relationship between the agent’s role and the model performance via Role Diversity, a metric that can describe MARL tasks. We define role diversity from three perspectives: policybased, trajectory-based, and contribution-based to fully describe the agents’ differences. Through theoretical analysis, we find that the error bound in MARL can be decomposed into three parts that have a strong relation to the role diversity. The decomposed factors can significantly impact policy optimization on parameter sharing, communication mechanism, and credit assignment strategy. Role diversity can therefore serve as a flag for selecting a suitable training strategy and helping to avoid possible bottlenecks on current tasks. The main experimental platforms are based on Multiagent Particle Environment (MPE) and The StarCraft Multi-Agent Challenge (SMAC), with extensions to ensure the requirement of this study are met. Our experimental results clearly show that role diversity can serve as a robust description for the characteristics of a multi-agent cooperation task and help explain the question of why the performance of different MARL training strategies is unstable according to this description. In addition, role diversity can help to find a better training strategy and increase performance in cooperative MARL.

heading: 1 INTRODUCTION
text: Recently, multi-agent reinforcement learning (MARL) has captured people’s attention due to its impressive achievements in the field of super human-level intelligence in video games [3, 6, 52, 57], card games [7, 25, 44, 59], and real-world applications [62–64]. These achievements have benefited substantially from the success of single-agent reinforcement learning (RL) [14, 15, 30, 42, 43] and rapid progress of MARL from both the competitive and the cooperative side.
On the competitive side, existing works focus on game theory among adversary agents with guaranteed policy convergence via theoretical analysis [5, 17, 27, 29, 56]. Whereas the achievements on the cooperative MARL are more based on empirical results in cooperative multi-agent system (MAS) [4, 21, 28, 39, 46, 51, 61]. One key problem of cooperative MARL is that whether one algorithm is better than another depends on the MARL tasks as showed in Fig. 1a. Current researches focus on developing algorithms on the tasks they are good at but lack the study of why the performance declines on other tasks [16, 35, 55, 55, 58]. Even adopting the state-of-the-art algorithms does not guarantee a strong performance [13, 35, 48, 55, 58]. This may due to the varying characteristic (e.g agent’s attributes and goals) of MARL tasks and scenarios, one single algorithm is not able to cover them all, which means we have to change the training strategy according to the current scenario.
From this perspective, we need to find a metric to describe different MARL tasks and use this description to help determine the best strategy combination as showed in Fig. 1b. Considering that
Under review as a conference paper at ICLR 2022
Role
Diversity
Communication
Sharing
Credit
Assignment
Task 2
Task n
…
Role
Diversity
Algorithm for Task 2
Algorithm for Task n
…
Parameter
Sharing
Task 2
Task 1
MARL
Algorithm 1
Performance
the main component of MAS is the agents, we propose a new definition Role in MAS to quantify the agents’ difference and use Role Diversity to describe MAS. We then analyze how the role diversity impacts the MARL both theoretical and experimental. For theoretical analysis, we use the decomposed estimation error of the joint action-value function Qtot in MARL to discuss how role diversity impacts the policy optimization process. The experiment further verifies the theoretical analysis that the role diversity is strongly related to the model performance and can serve as a good description of a MAS. As shown in Fig. 1, with the role diversity description of each task, we can now avoid possible bottleneck of a MARL algorithm with the combination of different parameter sharing, communication, and credit assignment strategies. With the definition of role diversity and the analysis of its impact on MARL, we can also explain the question of why the model performance varies across different tasks.
Role diversity are defined from three aspects: policy-based, trajectory-based, and contribution-based in Sec. 3 which are measured by action distribution, observation overlap, and Q/state value diversity. Through theoretical analysis, we find each type of role diversity has different impact to different terms of decomposed estimation error: algorithmic error, approximation error, and statistical error (Sec. 4). We conduct comprehensive experiments covering three main topics in MARL: parameter sharing , communication , and credit assignment in Sec. 5 and provide a set of guideline on choosing MARL training strategy in Sec. 6. The main experiments are conducted on MPE [28] and SMAC [39] benchmarks, covering a variety of scenarios with different role diversity. The impact of role diversity is evaluated on representative MARL algorithms including IQL [49], IA2C [31], VDN [48], QMIX [35], MADDPG [28], and MAPPO [58], covering independent learning methods, centralised policy gradient methods, and value decomposition methods. The experiment results prove that the model performance of different algorithms and training strategies is largely dependent on the role diversity. Scenarios with large policy-based role diversity prefer no parameter sharing strategy. Communication is not needed in scenarios with large trajectory-based role diversity. Learnable credit assignment modules should be avoided when training on scenarios with large contributionbased role diversity.
The key contributions of this study are as follows: First, the concepts of the role and role diversity are defined to describe MARL tasks. Second, a theoretical analysis of how role diversity impacts MARL policy optimization with estimation error decomposition is built. Third, role diversity is proven to be strongly related to performance variance when choosing different training strategies, including parameter sharing, communication, and credit assignment on the MARL benchmarks. Finally, a set of guidelines for selecting a training strategy based on role diversity is provided.

heading: 2 RELATED WORK
text: Researches on the development of cooperative MARL algorithms are mainly in three aspects: parameter sharing, communication and credit assignment.
For parameter sharing, the common approach in cooperative MARL is to fully share the model parameters among the agents [16, 35, 48, 55]. In this way, the policy optimization can benefit from the shared experience buffer with samples from all different agents, providing a higher data efficiency. However, it has also been noted in recent works that parameter sharing is not always a good choice [8, 34, 50]. In some scenarios, a selective parameter sharing strategy, or even no parameter sharing,
can significantly benefit agent performance and surpass the full parameter sharing. However, the question of why different parameter sharing strategies have different impacts on different scenarios remains open. In this study, we find that the role diversity can serve as a strong signal for selecting the parameter sharing strategy.
The communication mechanism is an intrinsic part of the multi-agent system (MAS) framework [18, 19, 23, 28, 47]. It provides the current agent with essential information of other agents to form a better joint policy, which substantially impacts the final performance. In some cases, communication restrictions exist, which hinder us from freely choosing communication methods [28, 39]; in most cases, however, the communication is available and it is optional on when to communicate and how to ingest the shared information [19, 45]. We present a comprehensive study on the relationship between role diversity and information sharing via communication mechanisms and demonstrate that role diversity determines the necessity of communication.
For the credit assignment, most cooperative MARL algorithms adopt Q-learning or policy gradient as the basic policy optimization method, which is combined with an extra value decomposition module [16, 35, 48, 55] or shared critic function [13, 28, 58] to optimize the individual policy. Some other works find that leveraging the reward signal is unnecessary; however, optimizing the individual policy independently (independent learning, IL) can still get a strong joint policy [34, 49]. It then becomes slightly difficult to decide which credit assignment method (including IL) is better as there is no single method in cooperative MARL that is robust and always outperforms others (compared to PPO [43] or SAC [14] in single-agent RL) on different tasks. In this study, we contend that role diversity is the key factor that impacts the performance of different credit assignment strategies.
In the next section, we present the role definition from three aspects including policy-based, trajectory-based, and contribution-based, and propose the measurement of different role diversity types to describe a MARL task.

heading: 3 ROLE DIVERSITY
text: Using role to describe the characteristic of the agents in the MARL context has been proven to be effective in many recent works [8, 24, 54, 55]. However, the definition of the role concept remains largely unclear. In work [55], the role is defined as the higher-level option in the hierarchical RL framework [20]. In work [8], the role is defined as the environmental impact similarity of a random policy. These definitions are intuitive and cannot accurately describe the role difference. In this study, we attempt to define the role in a more comprehensively way from three different aspects: policy-based, trajectory-based, and contribution-based. More specific scenario-based illustration can be found in Fig. 7 and Fig. 8. With our refined role, a strong relationship between role diversity and the MARL optimization process can be built and the performance variance can be further explained.

heading: 3.1 POLICY-BASED ROLE
text: In MARL, different agents output different actions based on its current status. As common sense would indicate, actions taken at the same timestep can indicate different roles [55]. However, there are many exceptions. For instance, if we have two soccer players passing a ball to each other repeatedly [21], although the action is different at each time step, the roles of these two soccer players can be very similar from the perspective of the whole soccer game. Therefore, it is not sufficient to distinguish the role difference based on a single timestep. Instead, we contend that this difference should be defined based on a period. As this role is purely based on policy distribution π, we refer to it as a policy-based role.
Specifically, we define the policy-based role as the statistics of the actions’ frequency over a period, which is n steps backward and forward from the current timestep. Here, n is the time interval that is half the length of the total time. More details can be found in Fig. 8a, where we provide a real scenario from SMAC. Policy-based role difference can be represented as follows:
raT = 1
2n+ 1 T+n∑ t=T−n πat (1)
where T represents the current timestep, n is the time interval, a is the agent index, π is the policy distribution. We adopt symmetrical KL divergence to measure the distance of different policy-based
1s1m1h1M_vs_5z4m_vs_3z
roles. The total role distance of A agents can be computed as follows:
dpT = 1∑A−1 0 A∑ a0=0 A∑ a1=a0 (KL(ra0T |r a1 T ) +KL(r a1 T |r a0 T )) (2)
where dpT represents the policy-based role distance at timestep T , A represents the total agent number, and KL represents Kullback–Leibler divergence.
We also provide a case study of how policy-based role diversity varies in Fig. 2a. From a real battle scenario (4m vs 3z) taken from SMAC, we find three stages including Find a good position, Focus on enemy and Find each one’s best strategy. In stage 1, agents try to find their own best location; the role diversity is large. In stage 2, agents focus on the same enemy target; the policies become similar and the role diversity is decreased. In stage 3, the formation of the agents is broken up by the enemies. Policy-based role diversity again increases as each agent is required to find its own best strategy to deal with its current situation.

heading: 3.2 TRAJECTORY-BASED ROLE
text: A policy-based role only considers the role diversity from the action distribution perspective. A slight action difference may not diversify policy-based role; however, this difference can be enlarged by time, which eventually results in a de facto behavior difference. The most significant phenomenon caused by this is the agent’s trajectory. Again, consider a soccer game where players repeatedly pass a ball to each other; these players may have a similar policy-based role, but their trajectories are different. This difference is enhanced by the partial observation setting that exists in many popular cooperative MARL environments [39, 46, 61] as the partial observed input from different agents shares a less common pattern when the vision scope is smaller. Therefore, trajectory-based role diversity is an important supplement to policy-based role diversity.
Generally speaking, we can define the trajectory-based role as the record of the agent’s movement. However, the determination of the extent to which two trajectories differ is not a straightforward matter. To measure this difference, we use an indirect metric called observation overlap percentage.
Using observation overlap to measure the trajectory-based role difference is: I. easy to compute, II. able to utilize a constant scale from 0 to 1 and III. strongly related to observation scope, which means that two trajectories can have varying role distances. For instance, in an A-agent multi-agent system, the trajectory difference can be computed as follows:
dtrajT = 1∑A−1 0 A∑ a0=0 A∑ a1=a0 da0,a1T . (3)
Here, da0,a1T is the observation overlap percentage of the total area between agent a0 and agent a1 at timestep T . An example of calculating the observation overlap percentage in SMAC [39] can be found in Appx. C. We provide the observation overlap percentage curves in Fig. 2b to demonstrate how trajectory-based role diversity varies in different scenarios.

heading: 3.3 CONTRIBUTION-BASED ROLE
text: To help ensure the authenticity of the modern MAS, agents are initialized with different attributes in recently proposed MARL environments [21, 28, 39, 46]. For instance, in [21], the roles of forward and goalkeeper are quite different and characterized by different observation scopes, action spaces, and reward functions. The type differences are easy to notice but hard to define, as is the role distance between them.
Here, we use an indirect variable called contribution to measuring the type difference. In cooperative MARL, the final target is to obtain an optimal joint policy consisting of A individual policies. To do this, the credit assignment strategy is proposed in [13, 35, 48] to leverage the reward signals to each agent to achieve individual policy optimization. A good credit assignment strategy should be able to leverage the reward signal in a manner equal to each agent’s contribution to the global reward. In this way, the Q value (Q function in off-policy RL) or state value (critic function in on-policy RL) of each agent can be estimated based on the leveraged reward signal. From this perspective, the Q value or the state value can be regarded as the agent’s contribution to the team. Generally speaking, we use the Q value or state value to measure the contribution of a single agent. Contribution-based role diversity can be computed as follows:
dcontT = 1∑A−1 0 A∑ a0=0 A∑ a1=a0
d va0 ,va1 T
max(va0 , va1) . (4)
Here, v is the Q value or state value of the policy output and dva0 ,va1T is the absolute value difference between the agents’ output. In addition, we use max function to keep the range of contribution-based role diversity from 0 to 1. We provide the Q value (mean & max) curves in Fig. 2c to demonstrate that the contribution-based role diversity can vary a lot in different scenarios.
More detailed role definition, connection, and application discussion can be found in Appx. C, D and E. In this paper, all the role diversity values and curves including dpT , d traj T , and d cont T come from VDN[28] and separated training with no communication for robust performance and trainingefficient.

heading: 4 THEORETICAL ANALYSIS
text: In this section, we use a simple scenario as an example to illustrate the role diversity. Suppose each agent makes individual observations and the learning procedure of all agents is independent. We provide finite-sample analysis for the estimation error of the joint action-value function and identify the terms corresponding to the role diversity. We denote Q∗tot and Q ∗ i as the optimal joint and individual Q-function respectively and write ‖ · ‖p,µ as the Lp norm with respect to a probability measure µ. Motivated by [48] and [35], we consider a simple case:
Q∗tot ≈ F (Q∗) = w>Q∗ with w ∈ ∆n, Q∗ = (Q∗1, . . . , Q∗n), where n is the number of agents and ∆n is the (n − 1)-dimensional probability simplex. Here, the credit assignment function F is a weighted sum of Q∗i , i ∈ [n] with non-negative weights. We then study the excess risk that is the error gap between the estimated and optimal solution:
Err = ‖Q∗tot − ŵ>Qt‖1,µ − ‖Q∗tot − (w∗)>Q∗‖1,µ,
where w∗ and ŵ are the optimal and estimated weights and Qt is the output of FQI algorithm at the iteration t. We further denote Q as the space of individual Q-functions and write ω(Q) = supQ∈Q infQ′∈Q ‖Q′ − TQ‖22,ν . In Sec. B.3, we prove that
Err ≤ √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q∗)∥∥∥∥ 1,µ
+ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN0 N ) + 4γT+1 (1− γ)2 M, (5)
where N is the sample size and T is the number of iterations. In addition, φµ,ν is the concentration coefficient andN0 represents the 1/N -covering number ofQ. Please refer to Sec. B.1 for the detailed definitions.
The first term on the RHS of (5) reflects the benefit of credit assignment that is strong related to the Contribution-Based Role (Sec. 3.3). When Varn(Q∗) is non-negligible, minimizing ‖w∗ − ŵ‖ can significantly decrease the excess risk. The second term that involves ω(Q) stands for the approximation error caused by functional approximation in Q. It depends on the concentration of the sample and the scale of the hypothetical space. The remaining two tems are statistical error and algorithmic error. If the sample size is sufficiently large and the learning time is long enough, they can be arbitrarily small. In Sec. B.5, we assume Q is a sparse ReLU network and TQ is a composition of Hölder smooth functions, and analyze the convergence rate as N,T →∞. Next, we demonstrate that the variance term Varn(Q∗) is related to both the Policy-Based Role (Sec. 3.1) and the Trajectory-Based Role (Sec. 3.2). We consider the case in which all agents share one estimated Q-function and denote the optimal share Q-function as Q̄∗. Sec. B.4 proves that
Errshare ≤ ∥∥∥∥∥ n∑ i=1 w∗i (Q ∗ i − Q̄∗) ∥∥∥∥∥ 1,µ + √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q̄∗(z,u))∥∥∥∥ 1,µ
+ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN ′0 nN ) + 4γT+1 (1− γ)2 M, (6)
where N ′0 is the 1/(nN)-covering number of Q and Q̄∗(z,u) = ( Q̄∗(z1, u1), Q̄∗(z2, u2), . . . , Q̄∗(zn, un) ) .
The first term on the RHS of (6) stands for the bias caused by parameter sharing. If all Q∗i are the same, the bias will disappear. Therefore, the Policy-Based Role is related to this bias. Second, the variance Varn(Q̄∗) here is caused by the trajectory diversity. To reduce this term, we should should ensure that all agents have similar observations. In addition, the Trajectory-Based Role measures the concentration of all agents’ support set. It is therefore natural to group the highly overlapped agents into one sub-joint agent via communication mechanism. This can be compared to the separate case in (5), where approximation error and the learning error are the same. In Sec. B.5, we show that the parameter sharing improves the convergence rate of the statistical error via sample pooling, while the communication decreases the convergence rate by activating more input variables.

heading: 5 EXPERIMENT
text: In this section, we mainly demonstrate how model performance varies with role diversity and how to adjust the training strategy in the context of cooperative MARL. The experimental results show the following: 1. that the performance of different parameter sharing strategies is strongly related to the Policy-Based Role (Sec. 5.1). 2. that the benefit brought by different communication mechanisms can be easily affected by the Trajectory-Based Role (Sec. 5.2). 3. that the performance of the credit assignment method, or the centralized training strategy, is largely dependent on the Contribution-Based Role (Sec. 5.3). 4. that the choosing of training strategies should be determined by the scale of role-diversity for different scenarios. The main experimental platforms are MPE [28] and SMAC [39]. Extensions are made to fulfill the requirements of parameter sharing and the communication mechanism, these include separated training of policy in Sec. 5.1 and information exchange among agents in Sec. 5.2. All results come from eight random seeds. More details regarding the experimental settings can be found in the appendix.

heading: 5.1 PARAMETER SHARING
text: Policy-based role influences the convergence speed and final performance of different parameter sharing strategies in cooperative MARL. The scenarios we choose from the MPE and SMAC benchmarks are simple but diverse, covering policy-based role diversity that ranges from small to large. In table. 1 and Fig. 3, we provide policy-based role diversity and the model performance curve on these chosen scenarios. For the SMAC benchmark, we adopt two metrics to count ruT in Eq. 1. The first metric is real policy diversity, which treats each action as an independent. The second way is semantic policy diversity, which distributes the actions to different groups according to their semantic type (e.g. move & attack). There is no semantic policy-based role in scenarios chosen from the MPE benchmark as all the actions are of the same semantic type (move). The policy-based role diversity is then calculated according to Eq. 2. The base MARL credit assignment strategy we choose in table. 1 is VDN[48], combined with a fully/partly/no parameter sharing strategy. For details of how the partial parameter sharing strategy works, please refer to the Appx. F. We also evaluate other popular credit assignment strategies including IQL[49], IA2C, MADDPG[28] MAPPO[58], MAA2C and QMIX[35] combined with a fully/no parameter sharing strategy in Fig. 3. IA2C and MAA2C are the extension of A2C[31] on multi-agent scenarios.
Table. 1 outlines the performance of three parameter training strategies including No shared, Partly shared and Shared with the base credit assignment method VDN[48]. Detailed framework and settings can be found in Appx. F. As the policy-based role diversity increases, the performance of the Shared strategy is degraded in terms of both convergence speed (half training steps) and the final reward (full training steps). One interesting phenomenon also emerges: the same agent type (e.g. 3s vs 5z, 4m vs 4z) does not always indicate small policy-based role diversity, and vice versa (e.g. 1s1m1h1M vs 3z), which means it is hard to define the role before identifying an adequate policy. Fig. 3 shows the model performances of two parameter sharing strategies including No shared and Shared with different credit assignment methods. For policy gradient-based methods, we extend the training steps from the standard 2M to 20M (10 times) as the convergence speed of policy gradientbased methods (e.g. MAPPO, MAA2C) is slower than Q value-based methods. From Fig. 3, we find that different credit assignment methods have a slight impact on parameter sharing strategies but the trend in which no parameter sharing strategy achieves performance improvement continues to be present as the policy-based role diversity increases.
Here we conclude that, scenarios with large policy-based role diversity prefer no parameter sharing strategy, and vice versa. Suitable parameter sharing strategy helps obtain faster convergence speed and higher final performance.

heading: 5.2 COMMUNICATION
text: More information is better. This principle is common sense in many areas including computer vision or natural language processing. With a bigger dataset and more detailed and accurate annotations, the model can be better optimized. However, in reinforcement learning, the data is sampled using the current policy; in most cases, this policy learning starts with a randomly initialized neural network. In this way, the provision of more information may introduce a burden for the policy optimization and can moreover further degrade the sampled data quality, which gives rise to a vicious
circle. Therefore, it is critical to determine when and how to accept the extra information provided via communication mechanism in the context of cooperative MARL. As discussed in Sec. 4, the pattern of different agents’ support sets for policy optimization can determine whether or not the extra information is needed. Notably, the similarity of these support sets is largely dependent on the trajectories of different agents, corresponding to the trajectory-based role diversity defined in Sec. 3.2. Small trajectory-based role diversity corresponds to a similar support set pattern, which means that forming a concentrated input is preferred for policy optimization. Experiment results in table. 7 and Fig. 4 further prove that scenarios with larger observation overlap are more suitable for communication. Detailed setting of communication mechanism on SMAC can be found in Appx. G
To prove that small trajectory-based role diversity prefers obtaining extra information via communication and vice versa, we conduct extra experiments to study the relationship between the pattern of the input observation (support set) and the model performance by shrinking the vision scope (r in eq. 14). The results can be found in table 2. The results show that the model performance is strongly related to the vision scope and the trajectory-based role diversity determines whether the small or large vision is preferred. Small trajectory-based role diversity prefers large vision scope, indicating the similar pattern of support set is better. Large trajectory-based role diversity prefers small vision scope, which means enlarging the pattern difference benefits the policy optimization. This further prove that extra information provided by communication forms a similar pattern of support set which is preferred in scenarios with small trajectory-based role diversity.

heading: 5.3 CREDIT ASSIGNMENT
text: The performance of different credit assignment methods is strongly related to the contributionbased role. We mainly focus on three representative Q value-based MARL algorithm: VDN[48], QMIX[35] and IQL[49], and compare their performance on different scenarios that have different contribution-based role diversity measured by Q value according to Eq. 4. The result can be found
in table. 3. In small Q diversity (' 0.5) scenarios, QMIX significantly outperforms VDN with both shared and no shared strategies. With the increase of Q diversity, the performance of QMIX starts to degrade. In scenarios where agents have significantly different Q value distribution (Fig. 18 1s1m1h1M vs 3/4/5z), VDN significantly outperforms QMIX. As for IQL, the performance is not as good as VDN and QMIX in most scenarios. However, IQL is not sensitive to Q diversity and can perform well in easy scenarios like 1s1m1h1M vs 3z. Combined with theoretical analysis in Sec. 4, we can conclude that QMIX is not suitable for a large contribution-based role diversity scenario because of the additional value decomposition module, which is a sum function in VDN and a learnable neural network in QMIX. The neural network fails to minimize the approximation error for Qtot, and is an extra burden when the reward function (or the contribution to the global reward) is diverse. IQL has no such problem as it treats Qtot as the individual Q value. From this part, we conclude that using credit assignment methods with learnable value decomposition module should be avoided in scenarios with large contribution-based role diversity.

heading: 6 FINDING A BETTER TRAINING STRATEGY
text: Based on our theoretical and experimental analysis, we contend that role diversity is a strong candidate metric to aid in selecting the proper training strategy for cooperative MARL. Specifically, if the policy-based role diversity is large, we should choose a no parameter sharing strategy, and vice versa. If the trajectory-based role diversity is large, we should avoid communication or other unnecessary information sharing, and vice versa. If the contribution-based role diversity is large, the fixed credit assignment method or independent learning method is preferred, and vice versa. In this way, we can avoid the possible performance bottlenecks in the context of cooperative MARL. Notably, however, the question remains as to how we might obtain an accurate measurement of the role diversity before the training. In this study, all the role diversity comes from VDN and separated training with no communication because we require the baseline method in our study to be robust and training-efficient. The fact however remains that, in some cases, roles are different in ways that are easy to notice and require no trained policy.

heading: 7 CONCLUSION
text: In this paper, we define the role and role diversity to describe a cooperative MARL task and explain the question of why the model performance varies in different scenarios. We claim that a strong relationship between the role diversity and model performance exists and we prove it through both theoretical analyses on MARL error bound decomposition and experiments conducted on MARL benchmarks. The experiment results clearly show that the role diversity significantly impacts the model performance of different training strategies and this effect is ubiquitous in various environments and algorithms. Finally, we provide a guideline on choosing the proper training strategies for cooperative MARL based on the role diversity description.

heading: A PROBLEM FORMULATION
text: Multi-agent Reinforcement Learning A cooperative multi-agent task is a decentralized partially observable Markov decision process [33] with a tuple G = 〈S,A,U , P, r,Z, O, n, γ〉. Let S denote the global state of the environment, whileA represents the set of n agents and U is the action space. At each time step t, agent a ∈ A ≡ {1, ..., n} selects an action u ∈ U , forming a joint action u ∈ Un, which in turn causes a transition in the environment represented by the state transition function P (s′|s,u) : S ×Un×S → [0, 1]. All agents share the same reward function r(s,u) : S ×Un → R , while γ ∈ [0, 1) is a discount factor. For any state-action pair, the reward r is bounded by M , i.e. |r| ≤ M. We consider a partially observable scenario in which each agent makes individual observations z ∈ Z according to the observation function O(s, a) : S ×A → Z . Each agent has an action-observation history that conditions a stochastic policy πt, creating the following joint action value: Qπ(zt,ut) = Est+1:∞,ut+1:∞ [Rt|zt,ut], where Rt = ∑∞ i=0γ irt+i is the discounted return.
Centralized training with decentralized execution Centralized training with decentralized execution (CTDE) is a commonly used architecture in the MARL context. Each agent is conditioned only on its own action-observation history to make a decision using the learned policy. The centralized value function provides a centralized gradient to update the individual function based on its output. Therefore, a stronger individual value function can benefit the centralized training.

heading: B PROOFS
text: In this section, we present more detailed results and the proofs for the theoretical analysis in Sec. 4. In Sec. B.1, we denote more notations and state the concentration property of Markov decision process. Sec. B.2 presents two useful lemmas about the error propagation and one-step approximation respectively. In Sec. B.3, we consider a simple example of the decentralized and cooperative MARL and provide the finite-sample analysis for the estimation error of the joint action-value function. We use the value decomposition [35, 48] and the finite-sample results for single-agent RL [10]. For more related results about MARL, please refer to [60] and [53]. Sec. B.4 studies the parameter sharing case that all agents share one deep Q network. In Sec. B.5, we assume Q is a sparse ReLU network and TQ is a composition of Hölder smooth functions. Then we discuss the convergence rate of the statistical error as the sample size tends to infinity. According to Sec. B.3, B.4 and B.5, one can find that each type of role diversity have different impact to the decomposed estimation error. Furthermore, we explain the benefits of the training options, e.g. parameter sharing (Sec. 5.1), communication (Sec. 5.2) and credit assignment (Sec. 5.3), and discuss how these options impact the convergence rate of approximation error and statistical error.
We summarize our results as follows:
• The parameter sharing strategy introduces a bias term by constraining the diversity of individual action-value functions, which corresponds to the policy-based role diversity. At the same time, it speeds up the convergence rate of statistical error by pooling training data.
• The communication mechanism reduces the variance caused by the trajectory-based role diversity but slows down the convergence rate of approximation error by introducing more active input variables.
• When the contribution-based role diversity is nonnegligible, the credit assignment can significantly reduce the estimation error of the action-value function.

heading: B.1 MORE NOTATIONS AND ASSUMPTIONS
text: We denote the joint optimal action-value function by
Q∗tot(z,u) = Q ∗ tot(z1, . . . , zn, u1, . . . , un),
where z is the global state of the environment, u = {u1, . . . , un} is the action set that collects the action of each agent ui and zi is the observation of the agent i generated from the emission distribution zi ∼ Λ(z|i, s). We further denote the individual optimal action-value function by Q∗i and write
Q∗(z,u) = ( Q∗1(z1, u1), . . . , Q ∗ n(zn, un) )
as the vector of all agents’ action-value functions. According to the value decomposition assumption, the joint optimal Q-function Q∗tot can be approximated with
F (Q∗)(z,u) = F (Q∗1(z1, u1), . . . , Q ∗ n(zn, un)),
where F ∈ F is a credit assignment function. The VDN method [48] approximates the joint as a sum of individual action-value functions that condition only on individual observations and actions. Then a decentralised policy arises simply from each agent selecting actions greedily with respect to its Qi. Since n is a fixed integer, we write the hypothetical space of credit assign functions that only contains one function as:
F = { F (Q) = 1
n n∑ i=1 Qi : with Q = (Q1, . . . , Qn) } .
The QMIX method [35] generalizes the value decomposition scheme and prove that if
∂Qtot(z,u) ∂Qi(zi, ui) ≥ 0, for ∀1 ≤ i ≤ n, ∀z ∈ Zn, ∀u ∈ Un,
then the global arg max performed on joint Q-function yields the same result as a set of individual arg max operations performed on each agent Q-function, that is
arg max u Q(z,u) =
 arg maxu1 Q1(z1, u1) arg maxu2 Q2(z2, u2)
... arg maxun Qn(zn, un)  . Motivated by VDN and QMIX, we consider a simple case throughout this section:
F = { F (Q) = w>Q : w ∈ ∆n and Q = (Q1, . . . , Qn) } ,
where ∆n is the n− 1 dimensional probability simplex. Suppose the individual action-value function is estimated by the fitted-Q iteration (FQI) algorithm [9, 38]. At the iteration 0 ≤ t ≤ T , we write Q̃i,t and πi,t as the output of FQI algorithm and the corresponding greedy policy respectively. Let Qπi,t be the Q-function corresponding to πi,t. Then the joint action-value function is estimated by F̂ (Qt), where
Qt(z,u) = ( Qπ1,t(z1, u1), Qπ2,t(z2, u2), . . . , Qπn,t(zn, un) ) .
To proceed further, we give the following assumption that controls the similarity between two probability distributions under the Markov decision process.
Assumption 1. Let µ, ν ∈ P(Z × U) be two probability measures that are absolutely continuous with respect to the Lebesgue measure on Z × U . Let {πt} be a sequence of joint policies for all the agents, with πt : Z → P(U) for all time t. Suppose the initial state-action pair (z0, u0) has distribution µ, and the action ut is sampled from the joint policy πt. For any integer m, we denote by PπmPπm−1 · · ·Pπ1µ the distribution of {(zt, ut)}mt=1 under the policy sequence {πt}t=1,...,m. Then, the m-th concentration coefficient is defined as
κ(m;µ, ν) = sup π1,...,πm
[ Eν ∣∣∣d(PπmPπm−1 · · ·Pπ1µ)
dν ∣∣∣2]1/2 , where d(PπmPπm−1 · · ·Pπ1µ)/dν is the Radon-Nikodym derivative of PπmPπm−1 · · ·Pπ1µ with respect to ν and the supremum is taken over all possible policies.
Furthermore, let ν be the stationary distribution of the samples {(zt, ut)} from the Markov decision process and let µ be a fixed distribution on S ×U . We assume that there exists a constant φµ,ν such that
(1− γ)2 · ∑ m≥1 γm−1 ·m · κ(m;µ, ν) ≤ φµ,ν .
To proceed further, we denote Q as the space of individual Q-functions and let
ω(Q) = sup Q∈Q inf Q′∈Q ‖Q′ − TQ‖22,ν ,
where ‖ · ‖2,ν as the L2 norm with respect to a probability measure ν. In the following, we take ν as the independent data sampling distribution in the FQI algorithm, e.g. experience replay [26].
We say a collection {Q1, . . . , QK} ⊆ Q is an δ-cover of Q if for each Q ∈ Q, there exists Qk such that ‖Q−Qk‖ ≤ δ. The δ-covering number of Q with respect to ‖ · ‖ is
N(Q, δ, ‖ · ‖) := inf{K ∈ N : there is an δ-cover of Q with respect to ‖ · ‖}.
In the following, we take the L∞(Z × U) norm on Q by
‖Q−Q′‖L∞(Z×U) = sup (z,u)∈Z×U ∣∣Q(z, u)−Q′(z, u)∣∣. For the sake of simplicity, we rewriteN(Q, δ, ‖ ·‖) asNδ. In Sec. B.3, we study the estimation error of the joint action-value function and prove that the statistical error depends on lnN0/N , where N0 is the 1/N -cover of Q and N is the sample size. For the parameter sharing settings, the sample size increases while the cover number also increases due to the smaller δ. Thus, we still do not know whether the parameter sharing improves the convergence rate of the statistical error. So we present a fine-grain analysis to discuss the convergence rate in Sec B.5.

heading: B.2 USEFUL LEMMAS
text: Lemma 1. (Theorem 6.1 in [10]). For each agent i ∈ [n], we denote {Q̃i,t}0≤t≤T as the iterates of FQI Algorithm. Let πi,t be the one-step greedy policy with respect to Q̃i,t, and let Qπi,t be the action-value function corresponding to πi,t. Under Assumption 1, we have
‖Q∗i −Qπi,t‖1,µ ≤ 2φµ,νγ
(1− γ)2 max t∈[T ]
‖TQ̃i,t−1 − Q̃i,t‖2,ν + 4γT+1
(1− γ)2 M. (7)
Proof: Please see Appx C.1 of [10] for a complete proof.
This lemma quantifies the error propagation procedure of each agent action-value functions through each iteration of FQI Algorithm. The first term on the RHS is the one-step statistical error and will not vanish even when the iteration goes to infinity (T → ∞). For more related error propagation results, please refer to [11, 12, 22, 32, 40].
Lemma 2. (Theorem 6.2 in [10]). Let {(zij , uij)}j∈[N ] be N i.i.d. random variables. For each j ∈ [N ], let rij and z′ij be the reward and the next state corresponding to (zij , uij). In addition, for any fixed Q̃i,t−1 ∈ Q, we define yij = rij+γ ·maxu Q̃i,t−1(z′ij , u). Based on {(zij , uij , yij)}j∈[N ], we define Q̃i,t as
Q̃i,t = arg min Q∈Q
1
N N∑ j=1 ( Q(zij , uij)− yij )2 .
Then for any δ > 0, we have
‖TQ̃i,t−1 − Q̃i,t‖22,ν ≤ 4ω(Q) + C M2 (1− γ)2 lnNδ N + C Mδ 1− γ , (8)
where ω(Q) = supQ∈Q infQ′∈Q ‖Q′ − TQ‖2ν and Nδ is the δ-covering number of Q with respect to the norm ‖ · ‖∞. Proof: Please see Appx C.2 of [10] for a complete proof.
B.3 INDIVIDUAL Q-FUNCTION
Theorem 1. We consider the separated strategy that each agent has its own action-value function and reward. All agents’ learning process is independent. Suppose {Q̃i,t}0≤t≤T are the output of FQI Algorithm for the agent i. Let πi,t be the one-step greedy policy with respect to Q̃i,t, and let Qπi,t be the action-value function corresponding to πi,t. We rewrite
Qt = ( Qπ1,t , Qπ2,t , . . . , Qπn,t ) , and Q∗ = ( Q∗1, Q ∗ 2, . . . , Q ∗ n ) .
Recall that 0 ≤ γ < 1 is the discount factor, the reward function is bounded, i.e., |r(s, u)| ≤ M , Q is the space of individual Q-functions and ω(Q) = supQ∈Q infQ′∈Q ‖Q′ − TQ‖22,ν . Then, under Assumption 1, we have
‖Q∗tot − F̂ (Qt)‖1,µ ≤ ‖Q∗tot − (w∗)>Q∗‖1,µ
+ √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q∗(z,u))∥∥∥∥ 1,µ
+ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN0 N ) + 4γT+1 (1− γ)2 M,
where N0 is the 1/N -covering number of Q with respect to the norm ‖ · ‖∞ and
Varn ( Q∗(z,u) ) = 1
n n∑ i=1 ( Q∗i (zi, ui)− 1 n n∑ i=1 Q∗i (zi, ui) )2 .
Proof: It is easy to see that
‖Q∗tot − F̂ (Qt)‖1,µ = ‖Q∗tot − F ∗(Q∗) + F ∗(Q∗)− F̂ (Q∗) + F̂ (Q∗)− F̂ (Qt)‖1,µ ≤ ‖Q∗tot − F ∗(Q∗)‖1,µ + ‖F ∗(Q∗)− F̂ (Q∗)‖1,µ + ‖F̂ (Q∗)− F̂ (Qt)‖1,µ. (9)
Here the first term at the RHS of (9):
‖Q∗tot − F ∗(Q∗)‖1,µ = ‖Q∗tot − (w∗)>Q∗‖1,µ (10) represents the best achievable estimation error under the value decomposition assumption. Next we consider the second term in the inequality (9):
‖F ∗(Q∗)− F̂ (Q∗)‖1,µ = ‖(w∗)>Q∗ − ŵ>Q∗‖1,µ = ‖(w∗ − ŵ)>Q∗‖1,µ
For any given z = (z1, . . . , zn) and u = (u1, . . . , un),
(w∗ − ŵ)>Q∗(z,u) = n∑ i=1 (w∗i − ŵi)Q∗i (zi, ui)
= n∑ i=1 (w∗i − ŵi) ( Q∗i (zi, ui)− 1 n n∑ i=1 Q∗i (zi, ui) ) .
The second equality holds since ∑n i=1(w ∗ i −ŵi)×c = 0 for any constant c. By the Cauchy–Schwarz inequality, we have
(w∗ − ŵ)>Q∗(z,u) ≤ √√√√ n∑ i=1 (w∗i − ŵi)2 × √√√√ n∑ i=1 ( Q∗i (zi, ui)− 1 n n∑ i=1 Q∗i (zi, ui) )2
= ‖w∗ − ŵ‖ × √ nVarn ( Q∗(z,u) ) where
Varn ( Q∗(z,u) ) = 1
n n∑ i=1 ( Q∗i (zi, ui)− 1 n n∑ i=1 Q∗i (zi, ui) )2
is the variance of the output vector of Q∗ given z and u. Plugging the positive upper boundary of (w∗ − ŵ)>Q∗ into the expression of ‖F ∗(Q∗)− F̂ (Q∗)‖1,µ, we obtain that
‖F ∗(Q∗)− F̂ (Q∗)‖1,µ ≤ ∥∥∥∥‖w∗ − ŵ‖ ·√n ·Varn(Q∗(z,u))∥∥∥∥
1,µ
= √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q∗(z,u))∥∥∥∥ 1,µ . (11)
Here the term ‖ √ Varn ( Q∗(z,u) ) ‖1,µ stands for the diversity of the agents.
Finally, we deal with the third term on the RHS of (9). Notice that ‖F̂ (Q∗)− F̂ (Qt)‖1,µ = ‖ n∑ i=1 ŵi(Q ∗ i −Q πt i )‖1,µ
≤ n∑ i=1 ŵi‖Q∗i −Q πt i ‖1,µ.
Therefore, it suffices to consider the deep Q-learning procedure of each agent separately and to give upper bound of ‖Q∗i −Q πt i ‖1,µ for each i ∈ [n]. According to (7) and (8),
‖Q∗i −Q πt i ‖1,µ ≤
2φµ,νγ
(1− γ)2 max t∈[T ]
‖TQ̃i,t−1 − Q̃i,t‖2,ν + 4γT+1
(1− γ)2 M
≤ 2φµ,νγ (1− γ)2
√ 4ω(Q) + C M 2
(1− γ)2 lnNδ n + C ′ Mδ 1− γ +
4γT+1
(1− γ)2 M
≤ 4φµ,νγ (1− γ)2
√ ω(Q) + C 2Mφµ,νγ
(1− γ)3 √ lnNδ N + C ′ 2 √ Mφµ,νγ (1− γ)5/2 √ δ + 4γT+1 (1− γ)2 M.
We take δ = 1/N and write N0 as the 1/N -covering number of Q. Then, we have
‖Q∗i −Q πt i ‖1,µ ≤
4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN0 N ) + 4γT+1 (1− γ)2 M.
Furthermore,
‖F̂ (Q∗)− F̂ (Qt)‖1,µ ≤ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN0 N ) + 4γT+1 (1− γ)2 M. (12)
Combining the results of (10), (11) and (12), we know
‖Q∗tot − F̂ (Qt)‖1,µ ≤ ‖Q∗tot − (w∗)>Q∗‖1,µ
+ √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q∗(z,u))∥∥∥∥ 1,µ
+ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN0 N ) + 4γT+1 (1− γ)2 M.
Remark. The term √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q∗(z,u))∥∥∥∥ 1,µ shows the benefits of learning credit assignment, where w∗ stands for the best credit assignment scheme. Here we assume ŵ is given and do not take the modelling and learning of ŵ into consideration. In practice, ŵ is the output of a credit distribution network and its learning procedure also influence the convergence properties of individual Q-functions. On the other hand, Varn(Q) corresponds to the contribution-based role diversity in Sec. 3.3. Therefore, when the variance is nonzero, a good credit assignment ŵ can the estimation error. For the parameter sharing case in the next section, we decompose the variance term into the sum of a bias and a variance caused by policy-based role diversity and the trajectory-based role diversity respectively. This decomposition does not always hold. Here, we assume that all agents’ learning processes are independent and that each agent has its own reward function. In practice, these assumptions are idealistic and limited.

heading: B.4 SHARED Q-FUNCTION
text: Theorem 2. We consider the parameter sharing strategy that all individual agents shares one actionvalue function. Suppose {Q̃t}0≤t≤T are the output of FQI Algorithm. Let πt be the one-step greedy policy with respect to Q̃t, and let Qπt be the action-value function corresponding to πt. We further denote Q̄∗ as the optimal shared action-value function and write
Q̄t(z,u) = ( Qπt(z1, u1), Qπt(z2, u2), . . . , Qπt(zn, un) ) ,
Q̄∗(z,u) = ( Q̄∗(z1, u1), Q̄∗(z2, u2), . . . , Q̄∗(zn, un) ) .
Recall that 0 ≤ γ < 1 is the discount factor, the reward function is bounded, i.e., |r(s, u)| ≤ M , Q is the space of individual Q-functions and ω(Q) = supQ∈Q infQ′∈Q ‖Q′ − TQ‖22,ν . Then, under Assumption 1, we have
‖Q∗tot − F̂ (Q̄t)‖1,µ ≤ ‖Q∗tot − (w∗)>Q∗‖1,µ + ∥∥∥∥∥ n∑ i=1 w∗i (Q ∗ i − Q̄∗) ∥∥∥∥∥ 1,µ
+ √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q̄∗(z,u))∥∥∥∥ 1,µ
+ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN ′0 nN ) + 4γT+1 (1− γ)2 M.
where N ′0 is the 1/(nN)-covering number of Q with respect to the norm ‖ · ‖∞ and
Varn ( Q̄∗(z,u) ) = 1
n n∑ i=1
( Q̄∗(zi, ui)− 1
n n∑ i=1 Q̄∗(zi, ui)
)2 .
Proof: Similar to the arguments in (9), we have ‖Q∗tot − F̂ (Q̄t)‖1,µ ≤ ‖Q∗tot − F ∗(Q∗)‖1,µ + ‖F ∗(Q∗)− F ∗(Q̄∗)‖1,µ +‖F ∗(Q̄∗)− F̂ (Q̄∗)‖1,µ + ‖F̂ (Q̄∗)− F̂ (Q̄t)‖1,µ. (13) The term ‖Q∗tot−F ∗(Q∗)‖1,µ caused by the value decomposition is the same to that in (9). So (10) still holds. For the second term on the RHS of (13),
‖F ∗(Q∗)− F ∗(Q̄∗)‖1,µ = ‖(w∗)>(Q∗ − Q̄∗)‖1,µ
= ∥∥∥∥∥ n∑ i=1 w∗i (Q ∗ i − Q̄∗) ∥∥∥∥∥ 1,µ ,
which is the bias term caused by the parameter sharing. Next, we turn to a turn that is related to the trajectory-based role diversity. Similar to (11), we know(
F ∗(Q̄∗)− F̂ (Q̄∗) ) (z,u) = (w∗ − ŵ)>Q̄∗(z,u)
= n∑ i=1 (w∗i − ŵi)Q̄∗(zi, ui)
= n∑ i=1 (w∗i − ŵi)
( Q̄∗(zi, ui)− 1
n n∑ i=1 Q̄∗(zi, ui)
)
= √ n× ‖w∗ − ŵ‖ × √ Varn ( Q̄∗(z,u) ) .
On the other hand, by (7) and (8),
‖Q∗ −Qπt‖1,µ ≤ 2φµ,νγ
(1− γ)2 max t∈[T ]
‖TQ̃t−1 − Q̃t‖2,ν + 4γT+1
(1− γ)2 M
≤ 2φµ,νγ (1− γ)2
√ 4ω(Q) + C M 2
(1− γ)2 lnNδ nN + C ′ Mδ 1− γ +
4γT+1
(1− γ)2 M
≤ 4φµ,νγ (1− γ)2
√ ω(Q) + C 2Mφµ,νγ
(1− γ)3 √ lnNδ nN + C ′ 2 √ Mφµ,νγ (1− γ)5/2 √ δ + 4γT+1 (1− γ)2 M.
We take δ = 1/(nN) and write N ′0 as the 1/(nN)-covering number of Q. Then, we have
‖Q∗ −Qπt‖1,µ ≤ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN ′0 nN ) + 4γT+1 (1− γ)2 M.
Therefore,
‖F̂ (Q̄∗)− F̂ (Q̄t)‖1,µ ≤ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN ′0 nN ) + 4γT+1 (1− γ)2 M.
Summarizing the above results, we have
‖Q∗tot − F̂ (Q̄t)‖1,µ ≤ ‖Q∗tot − (w∗)>Q∗‖1,µ + ∥∥∥∥∥ n∑ i=1 w∗i (Q ∗ i − Q̄∗) ∥∥∥∥∥ 1,µ
+ √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q̄∗(z,u))∥∥∥∥ 1,µ
+ 4φµ,νγ (1− γ)2 √ ω(Q) +O( √ lnN ′0 nN ) + 4γT+1 (1− γ)2 M.

heading: B.5 CONVERGENCE RATE
text: Similar to the Theorem 4.4 in [10], we assume that Q belongs to a family of sparse ReLU networks and TQ can be written as compositions of Hölder smooth functions. Here T is the optimal Bellman operator. We start with the definition of a (L+ 1) layers and {dj}L+1j=1 width ReLU networks:
f(x) = WL+1σ(WLσ(WL−1 . . . σ(W2σ(W1x+ v1) + v2) . . . vL−1) + vL),
where σ is the ReLU activation function, and Wl and vl are the weight matrix and the bias in the l-th layer, respectively. The family of sparse ReLU networks is defined as
F(L, {dj}L+1i=0 , s) =
{ f : max
l∈[L+1] ‖W̃l‖∞ ≤ 1, L+1∑ l=1 ‖W̃l‖0 ≤ s, max j∈[dL+1] ‖fj‖∞ ≤ M 1− γ
} ,
where W̃l is the parameter matrix that containsWl and vl and fj is the j-th output of f. On the other hand, the set of Hölder smooth functions is
Cr(D, β,H) = f : D → R : ∑
α:|α|<β
‖∂αf‖∞ + ∑
α:‖α‖1=bβc sup x,y∈D, x 6=y
|∂αf(x)− ∂αf(y)| ‖x− y‖β−bβc∞ ≤ H  , whereD is a a compact subset of Rr, b·c stands for the floor function and ∂α = ∂α1∂α2 · · · ∂αr with α = (α1, α2, . . . , αn)
>. Furthermore, we write G({pj , tj , βj , Hj}j∈[q]) as the family of functions that can be decomposed into the composition of a sequence of Hölder smooth functions {gj}j∈[q]. That is, for any function f ∈ G({pj , tj , βj , Hj}j∈[q]),
f = gq ◦ gq−1 ◦ · · · ◦ g2 ◦ g1, where for any k ∈ [pj+1] and j ∈ [q], the k-th component of the function gj is a Hölder smooth function, i.e., gjk ∈ Ctj ([aj , bj ]tj , βj , Hj). For simplicity, we take pj+1 = 1. Here we assume that the input of gjk is tj-dimensional, where tj can be much smaller than pj . More specific, the deep Q network we used is a sparse ReLU network for any given action u. Therefore, we rewrite the space of individual Q-functions Q as
F0 = {f : S × U → R : f(, u) ∈ F(L, {dj}L+1j=0 , s) for any u ∈ U}.
Furthermore, for any Q ∈ F0, we assume TQ is a composition of Hölder smooth functions and belongs to the following family:
G0 = {f : S × U → R : f(, u) ∈ G({pj , tj , βj , Hj}j∈[q]) for any u ∈ U}.
To proceed further, we denote
α∗ = max j∈[q] tj 2β∗j + tj , β∗j = βj × ∏ l=j+1 min(βl, 1), and β∗q = 1.
Now we are ready to state the following result.
Theorem 3. Suppose the assumptions of Theorem 1 hold and for any Q ∈ F0, TQ ∈ G0, where T is the optimal Bellman operator. The sample size N is sufficiently large such that there exists a constant ξ > 0 satisfies
max  q∑ j=1 (tj + βj + 1) 3+tj , ∑ j∈[q] ln(tj + βj), max j∈[q] pj  . (lnN)ξ. The network architecture of the Q-function is well designed such that
L . (lnN)ξ ∗ , r ≤ min
j∈[L] dj ≤ max j∈[L] dj . N
ξ∗ , and s Nα ∗ (lnN)ξ ∗
for some constant ξ∗ > 1 + 2ξ. The number of iterations T is sufficiently large, such that
T ≥ C ′(1− α∗) lnN,
where C ′ is a constant. Then, under Assumption 1, we have
‖Q∗tot − F̂ (Qt)‖1,µ ≤ ‖Q∗tot − (w∗)>Q∗‖1,µ
+ √ n× ‖w∗ − ŵ‖ × ∥∥∥∥√Varn(Q∗(z,u))∥∥∥∥ 1,µ
+O ( (lnN)1+2ξ ∗ N −minj∈[q] β∗j 2β∗ j +tj ) .
Proof: This is a direct conclusion reached by Theorem 4.4 in [10]. That is, for any agent i ∈ [n],
‖Q∗i −Qπi,t‖1,µ ≤ O ( (lnN)1+2ξ ∗ N (α ∗−1)/2 ) + 4γT+1
(1− γ)2 M.
The approximation error in Theorem 1 that involves ω(Q) is bounded above via Theorem 5 in [41]. The upper bound for the cover number N0 is derived from Theorem 14.5 in [2]. Please refer to Section 6 in [10] and Sec. B.3 for a complete proof.
Remark: Note that
4γT+1
(1− γ)2 M → 0 as T →∞,
which is the algorithmic error that converges to zero at a linear rate of T. In Theorem 3, we assume T is sufficiently large such that this error is negligible comparing to the statistical error. If we ignore the logarithmic term, the convergence rate of the statistical error is about
max j∈[q]
N − β∗j 2β∗ j +tj .
Here β∗j and tj are parameters of the functional space of TQ. Therefore, the parameter sharing (Sec. 5.1) keeps β∗j and tj unchanged and increases the sample size N to nN by pooling training data. In addition, tj is the number of active input variables of gj . Thus, the communication mechanism (Sec. 5.2) slows down the convergence rate by enlarging tj .

heading: C OBSERVATION OVERLAP PERCENTAGE CALCULATION

heading: C.1 OVERLAP PERCENTAGE CALCULATION IN GAMES
text: In this part, we demonstrate how to calculate the observation overlap percentage in SMAC [39]. As the partial observable area is circular, and the coordinate system is a 2D map with axis X and Y, the observation overlap on one battle scenario can be computed as:
l = √
(xa0 − xa1) · (xa1 − xa0) + (ya0 − ya1) · (ya1 − ya0) p = (1 + 2 · r)/2
s = 2 · √ p · (p− l) · (p− r) · (p− r)
o = 2 · cos−1(l/(2 · r)) · r · r − s da0,a1T = o/(π · r 2)
(14)
Here r is the vision scope. Notice that if l < 2r, dT equals zero as no overlap exists. We provide the observation overlap curve in Fig. 2b to show how trajectory-based role distance varies in one game.

heading: C.2 OVERLAP PERCENTAGE CALCULATION IN REAL WORLD SCENARIO (SEMANTIC)
text: In this part, we demonstrate how to apply the observation overlap concept and trajectory-based role diversity calculation (Eq. 3) to real-world scenarios. Different from game scenarios like SMAC and MPE, the observation of real-world tasks is usually an image. For example, in the vision language navigation task (VLN[1]), agents take real indoor scene pictures as the input, combine them with language description to locate the target as shown in Fig. 5. Considering the learning efficiency, object detection techniques like YOLO[36] and FasterRCNN[37] are used in VLN to help extract the objects from the scene pictures as semantic information. The semantic information can be recorded as part of the agents’ trajectory, enabling agents to use the past information for future decisions. Under the multi-agent setting, agents are required to cooperate and find the target together. Therefore, trajectory overlap should be avoided, which means that large trajectory-based role diversity is preferred in this task, and policies that cause trajectory overlap should be punished. Directly using scene pictures as input or its feature pattern can bring large noise in observation overlap calculation. Instead, using semantic information from the detected object can significantly reduce the noise and serve as a good observation history representation. As shown in Fig. 5, the red dotted frames indicate that the blue agent and green agent share some similar observation semantic in their trajectories. In this way, the trajectory-based role diversity of multi-agent VLN task can be calculated the same as Eq. 3. Only the da0,a1T is replaced by the observation semantic overlap, which is the shared detected object percentage in total detected objects. In this way, without knowing the exact trajectory, we still manage to calculate the trajectory distance. And using overlap to represent the trajectory-based role diversity, we can keep this metric in a fixed range from 0 to 1.

heading: C.3 OVERLAP PERCENTAGE CALCULATION IN REAL WORLD SCENARIO (RAW)
text: It is also possible that we can get observation overlap directly based on real image MARL tasks. As showed in Fig. 6. Passing the input image to pre-trained CNN/Transformer backbone and getting its feature, we can use cosine similarity or channel-wise similarity to compute the overlap between different observation features as da0,a1T in Eq. 3. However, these methods can bring large noise to this metric. Moreover, how to stabilize the reinforcement learning with real pictures as input is still under investigation. In addition, it is rare in MARL tasks that the only information provided in the training stage is one single image. Location and communication are necessary auxiliary information to help learn the coordination of agents in most MARL tasks. Therefore, simply using the raw image to calculate the observation overlap can be a choice, but not the best choice.

heading: D TYPES OF ROLE
text: We present two illustration figures for different types of role based on MPE [28] and SMAC [39]. Fig. 7 is based on MPE. Grey circles and black circles represent agents and goals respectively. Dashed arrows in different colors represent different actions. Larger circles receive more rewards when they reach the goal.
Fig. 8 is based on SMAC. A detailed explanation can be found in the caption.

heading: E CONNECTIONS OF DIFFERENT ROLES
text: Is there any redundancy in the definition of different kinds of role diversity in Sec. 3? Here we discuss the connections of different role diversity.
From the theoretical perspective, the contribution-based role diversity is a compound description of role diversity. It corresponds to the variance term in (5). For the parameter sharing case, we decompose this variance into a sum of two terms: a bias term corresponds to the policy-based role
diversity and a variance term corresponds to the trajectory-based role diversity. Therefore, under the simple scenario in Sec. 4, we can find a clear relationship between different role diversity.
From the experiment perspective, the decomposition in (6) may not hold because of the more complicated settings. We have discussed this issue in the remark on Page 18. Here we collect all different role diversity data in Table. 4. We find scenarios like 3s vs 5z have relatively small diversity in the policy-based role while the observation overlap of trajectory diversity is small. Scenarios like 4m vs 5m have small policy-based role diversity while the observation overlap is large. Contributebased role diversity can not be inferred from the policy diversity and trajectory diversity, and is more depending on the agents’ behavior difference.
In conclusion, the relationship between different roles exists in MARL training theoretically, while this relationship is not so significant in the experimental perspective due to more complicated settings of the real MARL tasks. Yet the strong relation between different role diversity and the MARL training process still exists with no conflict with the conclusion of this paper.

heading: F PARAMETER SHARING
text: Four different parameter sharing strategies are tested in our experiment including shared, no shared, partly shared, and selectively shared[8]. For partly shared, we only shared the GRU cell across different agents while keeping the embedding layer of the policy function model separated for each agent. For selectively shared strategy, we reproduce the grouping results following[8]. An illustration figure can be found in Fig. 9.

heading: F.1 SELECTIVELY SHARING THE PARAMETER
text: Here we provide the selective parameter sharing strategy result in Table. 5 as a supplement for Table. 1. The main purpose for doing so is to verify whether this method can serve as a general solution for parameter sharing strategy choosing issue. Selective parameter sharing strategy partitions the agents into the different groups automatically with an encoder-decoder model. However, the partition process is before the MARL training stage, which can not fully catch the policy difference. And according to the grouping result column in Table. 5, the selective parameter sharing strategy tends to divide agents by their initial attributes. This works well in scenarios like 1s1m1h1M vs 4z and 1c1s1z vs 1c1s3z but ignores the fact that the same type of agents may evolve to different functions during MARL training, which is the weakness of the selective parameter sharing strategy.

heading: G COMMUNICATION FRAMEWORK
text: The communication mechanism is important for MARL. The information shared can be location, action, and partial observation as showed in Fig. 10a. In many cases, communication is optional where the agent should learn when to communicate and how to ingest the information (dash line in Fig. 10b). In our experiment, we only consider the observation sharing method where the support set of policy functions contains both self partial observation and the aggregated observation information from other agents. The aggregated information is obtained by getting the mean value of other agents’ observation and concatenate with the self partial observation. This means the support set of policy functions is now much similar to the global state.
observation
RL
policy of agent 3
policy for agent 2
predict agent 1’s policy
predict agent 3’s policy
supervised
RL

heading: H CREDIT ASSIGNMENT
text: Credit assignment is the key part module for cooperative MARL, especially for the value decomposition-based method as it leverages the reward signal to each agent by approximate the Qtot. Then the learned individual policies combine to form a joint policy interacting with the MAS.

heading: I EXPERIMENT TABLE & CURVE

heading: Credit Assignment

heading: Global Reward

Review summaries:
This work looks at defining role diversity as a means for analyzing multi agent dynamics. It proposes three different perspectives on analyzing roles in multiagent systems. One is from a policy perspective (based on KL divergences), an trajectory perspective (how much do the agents overlap in what they observe), and a team-contribution perspective (weighing the effects of the agent to the team reward). 

This paper study the relation between role diversity of tasks and the MARL model performance. The role diversity (difference among agents) is described from three perspectives: policy-based, trajectory-based, and contribution-based. The authors analyze how the role diversity impacts the MARL performance in theory and experiments. The empirical results show a strong relation among the three metrics and the three main topics in MARL (parameter sharing, communication, and credit assignment).

To address the problem of algorithm choosing in different MARL tasks, this paper proposes to use role diversity as a metric to describe MARL tasks. For choosing parameter sharing, communication mechanism, and credit assignment strategy, this paper defines three role diversity metrics, i.e. policy-based, trajectory-based, and contribution-based, respectively. They also find that the error bound in MARL can be decomposed into three parts that have a strong relation to the role diversity. To evaluate the proposed method, they further conduct some experiments on MPE and SMAC environments.