Solving Homogeneous and Heterogeneous Cooperative Tasks with Greedy Sequential Execution
Authors: Shanqi Liu
Dong Xing
Pengjie Gu
Xinrun Wang
Bo An
Yong Liu
Venue: ICLR 2024 spotlight (2024)
Keywords: Multi-Agent Cooperation
Credit Assignment
Homogeneous and Heterogeneous Cooperative Tasks
Primary area: reinforcement learning

Abstract: Cooperative multi-agent reinforcement learning (MARL) is extensively used for solving complex cooperative tasks, and value decomposition methods are a prevalent approach for this domain. However, these methods have not been successful in addressing both homogeneous and heterogeneous tasks simultaneously which is a crucial aspect for the practical application of cooperative agents. 
On one hand, value decomposition methods demonstrate superior performance in homogeneous tasks. Nevertheless, they tend to produce agents with similar policies, which is unsuitable for heterogeneous tasks. On the other hand, solutions based on personalized observation or assigned roles are well-suited for heterogeneous tasks. However, they often lead to a trade-off situation where the agent's performance in homogeneous scenarios is negatively affected due to the aggregation of distinct policies. An alternative approach is to adopt sequential execution policies, which offer a flexible form for learning both types of tasks. However, learning sequential execution policies poses challenges in terms of credit assignment, and the limited information about subsequently executed agents can lead to sub-optimal solutions, which is known as the relative over-generalization problem. To tackle these issues, this paper proposes Greedy Sequential Execution (GSE) as a solution to learn the optimal policy that covers both scenarios. In the proposed GSE framework, we introduce an individual utility function into the framework of value decomposition to consider the complex interactions between agents. 
This function is capable of representing both the homogeneous and heterogeneous optimal policies. Furthermore, we utilize greedy marginal contribution calculated by the utility function as the credit value of the sequential execution policy to address the credit assignment and relative over-generalization problem. We evaluated GSE in both homogeneous and heterogeneous scenarios. The results demonstrate that GSE achieves significant improvement in performance across multiple domains, especially in scenarios involving both homogeneous and heterogeneous tasks.

Published as a conference paper at ICLR 2024
SOLVING HOMOGENEOUS AND HETEROGENEOUS Co- OPERATIVE TASKS WITH GREEDY SEQUENTIAL EXE- CUTION
Shanqi Liu', Dong Xing', Pengjie Gu², Xinrun Wang"*, Bo An Yong Liu 1 *Zhejiang University Nanyang Technological University Skywork AI, Singapore (shanqi 1iu, dongxi (g) jzju.ec edu. en, yongl fuui ppc. zju. edu.cn, (pengjie. gu, xinrun. wang, boan) @ntu.nneeee. sg
ABSTRACT
Cooperative multi-agent reinforcement learning (MARL) is extensively used for solving complex cooperative tasks, and value decomposition methods are a preva- lent approach for this domain. However, these methods have not been successful in addressing both homogeneous and heterogeneous tasks simultaneously which is a crucial aspect for the practical application of cooperative agents. On one hand, value decomposition methods demonstrate superior performance in homogencous tasks. Nevertheless, they tend to produce agents with similar policies, which is unsuitable for heterogeneous tasks. On the other hand, solutions based on per- sonalized observation or assigned roles are well- for heterogeneous tasks. However, they often lead to a trade-off situation where the agent's 's performance in homogeneous scenarios negatively affected due to the aggregation of distinct policies. An alternative approach is to adopt sequential execution policies, which offer a flexible form for learning both types of tasks. However, learning sequential execution policies poses challenges in terms of credit assignment, and the limited information about subsequently executed agents can lead to sub-optimal solutions, which is known as the relative over- wver-generalization problem. To tackle these issues, this paper proposes Greedy Sequential Execution (GSE) as solution to learn the optimal policy that covers both scenarios. In the proposed GSE framework, we introduce an individual utility function into the framework of value decomposition consider the complex interactions between agents. This function capable of representing both the homogeneous and heterogeneous optimal policies. Further- more, we utilize greedy marginal contribution calculated by the utility function as the credit value of the sequential exccution policy to address the credit assignment and relative wwer-eeneralization problem. We evaluated GSE in both homogeneous and heterogeneous scenarios. The results demonstrate that GSE achieves signifi- cant improvement in performance across multiple domains, especially in scenarios involving both homogeneous and heterogeneous tasks.
INTRODUCTION
Centralized training with decentralized execution (CTDE) provides popular paradigm for value- based cooperative multi-agent reinforcement learning (MARL), which has been extensively employed learn effective behaviors in many real- real-world tasks from agents' experiences (Sunehag et al. 2017] Rashid et al. 2018). These tasks encompass different types of scenarios, including homogeneous scenarios where agents are required to take similar actions, e.g., bimanual manipulation (Lee et al. 2013, Caccavale et al., 2008), and heterogeneous scenarios where agents are required to take distinct actions, e.g., autonomous driving through a crossroad (Chnn et al. [222I. Following the Individual Global Maximum (IGM) principle (Hostallero et al. 2019), these value decomposition methods can learn centralized value functions as monotonic factorizations of each agent's 's utility function and enable decentralized execution. Meanwhile, as the parameters of the utility network can be shared among all agents (Gupta et al. 2017), the number of parameters to be trained can be significantly
"Co-corresponding Authors

---

Published as a conference paper at ICLR 2024
reduced. These features together increase the potential of previous CTDE solutions to be applied in large-scale scenarios involving either homogeneous or heterogencous tasks.
Assuming that scenarios only involve either homogeneous heterogeneous tasks is oversimplified. as many roaldworld scenarios require agents to learn both tasks simultancously (for example, running restaurant requires waiters and cooks cooperate within each group and between these two groups (Knott et al.) 2021)). However, existing value decomposition methods have not been successful in addressing both types of tasks simultaneously. In homogeneous scenarios, the monotonic value function restricts the value function to sub-optimal value approximations in environments with non- monotonic payoffss (Wang et al., 2020a Son al. 2019). they cannot represent the policy that an agent's 's optimal action depends on actions from other agents. This problem, known as the relative overgeneralization (Panait et al. 2006), prevents the agents from solving all kinds of homogeneous tasks. Recent methods have attempted to address this issue by encouraging agents to simultaneously take the same cooperative actions to find optimal policies in non- mon-oontooiic payoft' (Rashid et al.) 2020 Mahajan et al. 2019). However, while agents acquiring similar policies can be advantageous for learning in non-monotonic homogeneous scenarios, it impedes the ability of agents to adapt to heterogeneous scenarios. Meanwhile, in heterogeneous scenarios, one of the main challenges is obtaining distinct policies among agents when the utility network is shared among all of them. This shared utility network makes it difficult for agents learn and exhibit diverse policies that necessary for such scenarios. Therefore, several methods employ techniques such as incorporating agent ID as input to construct different policies (Li et al. (021a)) or assigning different roles to encourage diverse behaviors (Christianos et al., 2021; Wang et al., 2020c).. Nevertheless, these methods still encounter other challenges. They tend result fixed policies that can only represent a single solution mode of the task, which precludes cooperation when working with dynamically changing agents (Fu et al.] (022). In addition, simply aggregating distinct policies results in a trade-off scenario, where performance in homogeneous scenarios is negatively impacted (Christianos) jt al. 202T Li et al. 2021a).
To address these challenges, sequential execution policies have been introduced. These policies allow agents to take actions based on the actions of previous agents, enabling the learning of both homogeneous and heterogeneous tasks (Fu et al., 2022 Liu et al. (02I). In this approach, as latter agents can adjust their actions based on the actions of earlier agents, they can exhibit either homogeneous or heterogeneous policy to cooperate with the previous agents, depending the specific situation. However, sequential execution methods encounter challenges in credit assignment, as the policy form does not conform the IGM principle, precluding current value decomposition methods from learning each agent's individual utility. Additionally, as the former executed agents lack action information about the latter agents. the former executed policies may still converge to a sub-optimal solution and cannot solve the relative overgeneralizztion problem thoroughly.
In this work, we propose Greedy Sequential Execution (GSE) which is capable of addressing these problems and adapting to both homogeneous and heterogeneous tasks. Specifically, we first propose a value decomposition scheme that captures the interactions between agents while adhering to the IGM principle. This value decomposition enables agents to learn individual utilities that take into account interactions with all other cooperative agents. We demonstrate that such individual utilities can accurately represent both homogeneous and heterogeneous payoff matrices. However, since the individual utilitics require the actions of all other agents to conduct actions, which is infcasible in sequential execution, they cannot be directly used as the policy's 's value function. To address this issue, we further propose an explicit credit assignment method that calculates a greedy marginal contribution the credit value for each agent's policy in sequential execution. The insight behind this is that each agent's optimal cooperative policy is to maximize the marginal contribution of joining the group of previously executed agents while considering that the latter agents will take optimal cooperative actions to cooperate with it. We show that the greedy marginal contribution can overcome the relative vver-generalization problem by avoiding taking conservative actions that lead to mis- mus-coordination. Furthermore. using the explicit credit assignment method can address the challenges of learning each agent's individual utility the sequential execution policy. It allows for the precise allocation of credit to each agent's ' actions, enabling effective learning of the sequential execution policy. We evaluated GSE in comparison to several state-of-the-ar baselines in various scenarios, including homogeneous tasks, heterogeneous tasks, and a combination of both tasks. The results demonstrate that our proposed method achieves a significant improvement in performance
2

---

Published as a conference paper at ICLR 2024
8
A
B
A
B
6-
11
A
+r1
-2
A
-
th
12
2
B
72
0
B
+11
22
0.0 0.2
0.4
0.6
0.8
1.0
Pb
Homogeneous
Heterogeneous
Figure 1: Left:: The illustration of Eq. 4 and Eq. (5) The orange area is where the methods using Qi(Ti, a;) as the individual utilities have the maximum possibility to solve both tasks depicted by the example payoff matrixes. Middle: Non- monotonic payoff matrix of the homogeneous example, where agents are required to take action simultaneously achieve cooperation and taking action alone results in a penalty. Right: Payoff matrix of the heterogeneous example, where taking the same action is punished and taking distinct action is rewarded.
across all domains and the most prominent advantages in scenarios involving both tasks, while other methods struggle to provide effective solutions.
PRELIMINARIES
Dec-POMDP. A fully cooperative multi-agent sequential recision-making task can be described as decentralized partially observable Markov decision process Prec)POMDP), which is defined by set of possible global states 5, actions A1,... An, and observations .,, At each time step, each agent i (1. n chooses action a; E A,, and they together form joint action The next state is determined by a transition function P S x U + S. The next observation of each agent 0, E 2 is updated by observation function 0 S Ω. All agents share the same reward r: : x U + The objective is to learn a local policy (a,(s), for each agent such that they can cooperate maximize the expected cumulative discounted return R, Σド= T' The joint value function is Qtot = E 1:00 [e st; un]. The observation of each agent can also be replaced by the history of actions and observations of each agent to handle partial observability (Sunehag et al., 2017 Rashid et al. 2018). The history of actions and observations agent can be viewed as тę which (o)
U.
Value Decomposition Methods. Current value decomposition methods represent the joint action value function Quat as mixing of per-agent utility functions to form the CTDE structure, where Individual Global Max (IGM) principle (Hostallero al. 2019 is wildly used to enable efficient decentralized execution:
arg max (QoorQQrr u)) (arg max(Q arg max (Q (Tn an))).
en
QMIX (Rashid et al. 2018) combines the agent utilities via a continuous monotonic function to satisfy IGM, i.e.,
Q (s,u) = (1) Qu(Tn,
aQ2MIX
aQ: O,ViEn.
Shapley Value and Marginal Contribution. We introduce the concept of the marginal contribution of Shapley Value (Shapley 2016). The marginal contribution of Shapley Value for agent is defined as
Φ = - =C(()))(((/))
(3)
where C' is team of agents that cooperate with another to achieve common goal, and C/i represents the set in the absence of agent v(C) refers to the value function that estimates the cooperation of set of agents.

---

Published as a conference paper at ICLR 2024
3 MOTIVATING EXAMPLES
In this section, we utilize two example tasks as motivating examples to illustrate the advantages and limitations of various methods. Their payoff matrices are depicted in Figure
3.1 ISSUES OF CURRENT METHODS
We investigate the limitations of current value decomposition methods by analyzing the form of individual utility. Currently, these methods model the individual utility of each agent as a value function Qi 04) to learn the decentralized policy. However, since the returns of both the homo- geneous and heterogeneous tasks depend on the actions of other agents, such an individual utility is not sufficient to represent the cooperation policy. We propose more comprehensive individual utility function, (T, 2z ,a,), where uj represents the joint actions of all other agents who have the potential to cooperate (discussed in detail in Section 4.1). According to this decomposition, the individual utility Q; a;) can be viewed as a variable sampled from the distribution (2 u, a.) over u This understanding enables us to demonstrate that (T, as) cannot represent homogeneous and heterogeneous policies simultaneously, resulting in the trade-off when learning both types of tasks concurrently. We illustrate this through the two motivating example scenarios.
For the two example tasks, the learned policy fails to represent the optimal policy when
11
2pb
pb
In the homogeneous scenarios, while the learned policy can never represent the optimal policy in the heterogeneous scenarios and the possibility P. of achieving cooperation is
Pr = 2- Ps -0 - (p)))-
(5)
where ps is the probability of each policy taking action B. The detailed derivation and proof are included in Appendix 5. Figure Tillustrates the result of Eq. 4 and Eq. (5). The result indicates that as the pa grows the r2 grows exponentially in the homogeneous scenarios. Therefore, we notice that there is trade-off as solving the homogeneous non- monotonic matrixes requires the ps to decrease to zero, while solving the heterogeneous matrixes needs to increase ps when ps, is below 0.5. As result, the ability of these methods to effectively learn both homogeneous and heterogeneous tasks simultaneously is limited.
3.2 SEQUENTIAL EXECUTION AS REMEDY
Another method is proposed that models individual utility as (T,(T: 01:--1 az), which a sequential execution policy. We illustrate that as P& serves known variable for the subsequently executed agent, the utility of the latter agent can choose actions in accordance with the actions of the former agent, thereby achieving the desired similar or distinct policies. As result, the overall policy can encompass both homogeneous and heterogeneous policies. Although the interactions between agents involve communication, the bandwidth is limited as the actions are one-hot vectors. Therefore, these methods retain the potential to be implemented in complex real-worle scenarios. However, the individual utility (T (T a;) does not satisfy the IGM principle as the former agents' utilities lack the necessary information about other agents' actions (detailed in the Appendix 6), which precludes implicit credit assignment. Additionally, the individual utility of the former agent remains Q' (T&, a.), which encounters the problem of relative veerraenealiiziion. Therefore, while the policy form is capable of representing the target policy mode, it is not guaranteed to converge to it.
4 GREEDY SEQUENTIAL EXECUTION
In this section, we propose Greedy Sequential Execution (GSE) to address the problems of credit assignment and relative over-generalization in the sequential execution policy. Specifically, we first propose a value decomposition that can capture the interactions between agents while adhering to the IGM principle. Then, propose actor-critic structure based on the value decomposition that trains a critic and calculates a greedy marginal contribution as credit value for sequential execution policy training. This explicit credit value addresses the credit assignment problem in learning
4

---

Published as a conference paper at ICLR 2024
Crbic
Actor
MIXING
Ca M. .)
Agent
Agent
(T,
C (.1.
MINUS
PICT. D)
Figure 2: The architecture of our method. Upper (Blue): The architecture for critic Q² (T; u; a;) that we elaborated Section 4.1 Lower (Green): The framework of the calculation of the greedy marginal contribution based on Q (Ti, U; .aa) and the sequential execution policy Q2 (T,, 01:1-1 0.).
sequential execution policy. Meanwhile, the greedy value of marginal contribution tackles the relative overgeneralized problem of former executed agents in sequential execution. As result, GSE achieves optimal cooperation in scenarios involving both homogeneous and heterogeneous tasks by effectively learning the sequential execution policy.
4.1
VALUE DECOMPOSITION
Since the current individual utility Qi(Ti, ai) is insufficient represent the optimal policy in both homogencous and heterogeneous scenarios, illustrate that (T u, a,) is more comprehensive utility which can capture the interactions between agents.
Theorem 4.1. For any Tsor(s, u), the corresponding Qtoi(s, = IE each agent's 's utility (T( ut as) satisfies
and
arg maggaaxQroe(ss u)) farg max "T, (1)), arg max (Q" Un an)))-
(6)
Detailed proof can be found in Appendix 4. Theorem 4.1 indicates that the value decomposition using utility Q (Tr, aa)) can represent the value decomposition given any reward function and satisfies the IGM principle. Therefore, we can use all Q: to calculate Qtot through a monotonic mixing network similar QMIX, and Theorem illusttttate the mixing value is unbiased. Specifically, the overall critic value function consists of each agent's adaptive utility (T,,,, ", aa) and a mixing network to produce the global Q-value Qioe u). The critic value function learned by optimizing
(T)(f) = E, (S,, uz) -y1 V/1 rt max Qtol (St+1. U1+1). u
4.2 CREDIT ASSIGNMENT VIA GREEDY MARGINAL CONTRIBUTION
The utilization of the critic value function as the agent policy's s value function feasible due to its reliance on the actions of all other agents, resulting in deadlock situation. An alternative approach is the utilization of a sequential execution policy, represented by Q2 A1:--1; a;), which allows for the consideration of the actions of former agents. However, this approach does not adhere to the principles of IGM principal and encounters the relative over-generale weergenerallizatonn problem. To overcome these limitations, contribution of Shapley values for the learning of a policy capable addressing both homogeneous and heterogeneous tasks.
propose explicit credit assignment method utilizing marginal
5

---

Published as a conference paper at ICLR 2024
According to the sequential execution process, each agent takes actions with the actions of former executed agents, which is equivalent to agent i joining a group consisting of former executed agents. Therefore, the policy represented by Q' (Ta, d1:4-1, az) should aim to maximize the marginal contribution of agent i joining the group of former executed agents. Based on the critic value function, the marginal contribution of agent i can be calculated
(Ti, 11:i-1, a,) = vTT)) - (T,/i) - (' 01:--1 a;) (T 01:-1))
(8)
where Φ is the marginal contribution. The reason behind this is that the uniqueness of the optimal action within the entire action space, where the primary actions often result in mis-coordination. Therefore, we can use (T as the value of agent not joining the former group to calculate the marginal contribution. However, such a calculation still faces other problems. Since the critic value function Q trained by taking "; instead of 01:1-1 1 as input, the accuracy of the calculated marginal contribution may be affected. Additionally, such marginal contribution encounters the relative over-generan seer-gnneralization problem, as the value of action og depends on overall joint actions "; and the current marginal contribution cannot consider the actions of latter agents 0;+1:ns leading the marginal contribution of a, converge to an average value as we discussed in Section 3 these problems, we propose greedy marginal contribution,
To address
0f (Ti, 01---, a.) = Q2, 01:1-1: 11:--1:9,41m. a;) (T 11:-11 11411,
where i1 is the optimal cooperative actions cooperate with former agents that maximize di. This approach ensures that the marginal contribution accurately represents the potential optimal value of action ag rather than an average value, thus addressing the issue of relative over- wer-generallzation. Furthermore, by including full information about u, as inputs, this approach allows for the accurate calculation of values by Φi- However, 41+1m not directly observable. Intuitively, the greedy marginal contribution means that each agent takes the action under the condition that all the latter agents will take the optimal cooperative action to cooperate with it. Therefore, we use the greedy actions oi Ion from the behavior policy to represent the di+1xx'
4++1m {arg max (Q++ (TI, a1:)) arg max(Q" d1m-1))3 a:ll
(10)
dn
However, such an estimation is not guaranteed to be correct when the behavior policy has not converged in the early training period. Therefore, we additionally use the Monte Carlo method to estimate the 4,41 to address this problem. Specifically, we sample M random joint actions as
i=1:M and search for the ai+im with the maximum value of Φ; in the collection of d 1.41on
J=1:M and
1+ to be the a1+1xx
In this way, we have our sequential execution policy's value function ( 01;--1 az) and decen- tralized policy as π (aa:TTi, 11:--1) = arg max., (Q' (T:, (1:--1;0)). The overall loss is
(M) = E, (T a1;-1,a;) 07 (Ti, a1)]1
(11)
In terms of practical implementation, we utilize an attention structure to address the varying di- mensions of a1-i-1. enabling the implementation of parameter sharing. The overall structure of our method is shown in Figure? 2
UNDERSTANDING TASK TYPES THROUGH MULTI-XOR GAMES
To evaluate how the different task types affect the performance of all methods, we devise a simple one-step randomized Multi-XOR game. Agents in the game can either take a cooperative action C' or a lazy action L. The game requires two out of four agents to take cooperative actions C simultancously to achieve successful cooperation. In contrast, if a single agent takes cooperative actions C, a homogeneous penalty applied, and when more than two agents take cooperative actions C, heterogeneous penalty is given. To prevent agents from learning fixed strategy, we randomly selected a dummy agent at the beginning of each episode, which cannot participate in cooperation and can only take the lazy action L. We set three scenarios according to the challenges of tasks, the homogeneous scenario with only the homogeneous penalty, the heterogeneous with only the heterogeneous penalty, and the mixing scenario with both penalties. These methods that compared include CDS (Li et al. 2021a). which employs mutual information to learn agent ID-specific policies; Shapley (Li et al. 2021b), which utilizes Shapley Value to estimate complex agent interactions; and

---

Published as a conference paper at ICLR 2024
0.3
Hemesgeneous
Hotarogenesus
Mixingg
1003
0.2
CDC
Returrss
-2.2
5.0
0.3
1.0
1.5
2.0
3,5
4.0
0.0
05
1.0
3.3
2.0
3.0
53
0.0
0.5
3.0
1.3
3.0
3.5
Figure 3: Results Multi- game. Left: Homogencous challenge. Middle: Heterogeneous chal-
lenge. Right: Mixing scenario that combines both the Homogeneous and Heterogeneous challenges.
both MAVEN (Mahajan et al. 2019) and QMIX (Rashid et al., 2018), which are common value decomposition methods. For detailed introduction all the methods compared, please refer to Appendix 1. Detailed reward settings are included in Appendix 2.
The results displayed in Figure indicate that our method effectively masters both homogeneous and heterogeneous tasks in the randomized Multi-XOR game. Specifically, in the homogeneous scenario, all other methods fail to overcome the non-monotonicity and learn a lazy policy that never engages in cooperative action to avoid penalties, except for MAVEN which is proposed to learn cooperative policy non-monotonic environments. In the heterogeneous scenario, MAVEN and QMIX fail to learn heterogeneous policies and take cooperative action together, resulting in failure. In the mixing scenario, our method also outperforms other methods, indicating its robustness in handling both homogeneous and heterogeneous tasks simultaneously. Overall, our method demonstrates superior performance in adapting to different types of cooperative tasks compared to other methods.
6
EXPERIMENTS
6.1 EXPERIMENTAL SETTINGS
We have developed series of challenging cooperative scenarios that involve the integration of both homogeneous and heterogeneous tasks evaluate all methods. The experiments are conducted based on MAgent (Zheng et al. 2018) and Overcooked (Sarkar et al. 2022). We implement five tasks MAgent: lift, heterogeneoux lift, multi_target _lift, pursuil and bridge. These scenarios can be classified into three categories: homogencous, heterogencous, and mixing.
Homogeneous scenarios: our implementation, we have included two homogeneous scenarios within the task of lift. Specifically, the lift task requires the coordination of two agents to lift cargo, Successful completion of the task necessitates the simultaneous execution of the "lift" action by both agents, otherwise, the cooperation will fail and the agent who takes the action will incur penalty of -r2, similar to the homogeneous task discussed in Section 3 To evaluate all methods, we have chosen scenarios with -r 0 and -12 -0.3. these scenarios represent situations without and with the relative over-generalization problem, respectively.
Heterogeneous scenarios: In heterogeneous. _lft,, agents must lift cargos cooperatively with changing partners. Rewards are given for two-agent lifts, with penalties for more than two. Each episode randomly excludes one or two agents from cooperating, preventing fixed policy learning. The challenge of this task lies in the fact that agents must adapt to varied partners for successful lifting. This necessitates the learning of heterogeneous policy to succeed.
Homogeneous & heterogeneous scenarios: We also implement three tasks that necessitate both homogeneous and heterogeneous policies to be solved. The first task, multi multi_taraee target _ift, is similar to lift. but with different cargos with varying rewards. The challenge of this task is that agents must learn to lift cargos with lower rewards in order to achieve optimal cooperation, instead all competing to lift cargos with higher rewards. The second task, purswit, requires agents to catch prey and rewards are only given when two agents attack together, otherwise, penalty imposed. Additionally, the prey will be killed if more than two agents attack together, resulting in significant penalty, thus requiring agents to perform differently to avoid killing the prey. In the third bridge task, agents start opposite sides of the map and must navigate through single tunnel, initially blocked by
7

---

Published as a conference paper at ICLR 2024
Lit, pud
Lif. piu-0
Heterogeneeursiim
120
10xgn
50
100
CD4
-10
1.0
Multi langel
Brridge
15
658
Raturns
0.5
0.5
0.0
0.2
0.6
1.5
0.00 025 0.50
0.75
1.25
7,00
0.30
0.25
0.50
0.75
1.25
7,00
Epicodes
Epicodes
Epiodds
Figure 4: Top: The performance results in lift with the penalty dropping from 0 to -0.3 and heteroge- neous_lit lift. Bottom: The results in multi multi-target lift, pursuit and bridge.
Nedium
Mars
Maves
12
Retumss
k.2
-30
Estsodes
Episooes
Epiccoes
Figure 5: Results of Overcooked. Difficulty increases from left right.
obstacle. Two agents must cooperate to break this barrier, then learn to retreat, preventing tunnel blockage for others.
We also designed three scenarios in Overcooked that require both homogeneous and heterogeneous policies. In the game, the objective is cook and deliver soups. We designed the picking of onions to be a cooperative action that requires two agents to work together. However, the cooking and delivering process introduce the need for agents exhibit different behaviors, such as yielding to others. We evaluated our approach on three maps of different difficulties; an casy small map with multiple onions,
small map with single onion, and challenging large map with single onion. Please refer to Appendix 2 and Appendix 3 for more experimental settings.
In the experiments, the methods compared are introduced in Section [ All the baseline methods use the agent ID as extra input to enable the learning of heterogeneous policies, while our method does not. All methods use the same basic hyperparameters and network structures with similar parameters to ensure the comparison is fair.
6.2 PERFORMANCE
We evaluate the performance of various methods in three types of scenarios: homogeneous, het- erogeneous, and homogeneous & heterogeneous. The results of MAgent scenarios are shown in Figure and Overcooked are Figure The results for the homogeneous scenarios indicate that the performance of all comparison methods is heavily influenced by the increase in penalty. Most methods are able to learn an optimal policy when the penalty is zero, but they fail to converge to cooperative policy when the penalty is -0.3. Their policies converge sub-optimal policy that never takes cooperative actions in order to avoid the mos-coordination penalty, except for MAVEN which is proposed to solve the relative overgeneralization problem. In contrast, method can find the optimal cooperative policy in both scenarios regardless of the growing penalty. This result indicates that method is able to overcome the relative veergeeneralization problem.
8

---

Published as a conference paper at ICLR 2024
0.3
MUEXOR
2.0
Hukilarget
MJIXXOR
53
Lit. p.
n/ Airrrgga cotoibution
Wiree condiatter
tipple sparts
Ratumn
0.0
0.0
0.1
0.0
1/0
0.3
Epicodes
Episode
Episodes
Ephoodes
Figure 6: The first two figures are ablations of specific parts of our method. The third figure is the ablation of sample number M, the fourth figure is training with larger scale of agents.
In the heterogeneous scenario, we observe that QMIX converges to sub-optimal policy that all agents lift together, resulting in penalties. Similarly, other methods also struggle to learn the cooperative policy but can learn to take lazy actions to avoid penalties. All of these policies reflect a failure learn distinct policies that can adapt to dynamically changing partners. In contrast, our method demonstrates the ability to adapt to the actions of other agents and outperforms other methods in terms of both final performance and sample efficiency when learning heterogeneous policy.
Lastly, we evaluate all methods in mixing scenarios involving both homogeneous and heterogeneous tasks. The results show that our method has the most significant advantage these scenarios. In MAgent scenarios, most methods coverage to the conservative policy since the penalty comes from mis-coordination of both homogeneous and heterogeneous actions which they cannot handle simultancously. However, CDS can solve the bridge scenario, which is because the homogencous behavior only involves breaking the obstacle and most required behaviors are heterogencous actions. In Overcooked scenarios, we compared methods that can handle complex homogeneous and heterogeneous tasks, respectively. The results consistent with other mixing scenarios. Since the learning difficulty of these tasks mainly arises from learning two conflicting tasks modes simultaneously, this result indicates that our method can unify the learning of similar and distinct policies. On the contrary, all other methods struggle to learn an efficient policy to solve the tasks due to their narrow policy representation ability.
method with MAVEN and CDS as they represent
6.3 ABLATIONS
We conduct several ablation studies to evaluate the effectiveness our proposed method in homo- geneous & heterogeneous scenarios, mulli_larget and multi_XOO Specifically, we evaluate our method training without using greedy actions, meaning we relied on marginal contributions instead of greedy marginal contributions. Additionally, we evaluated the method without using marginal contributions, instead directly using the policy value function to fit the Qtot- The results of these evaluations are presented in Figure The results indicate that training without using greedy actions can significantly degrade performance, as using greedy actions helps to overcome the relative over- generalization problem. Training without using marginal contributions also degrades performance in both scenarios as the sequential execution policy does not satisfy the IGM principle, underscoring the importance of our proposed utility function. Additionally, we evaluated how the sample number M affects performance. The results demonstrate that small value of M can be problematic as it may not select the greedy value of actions. However, a reasonably large value of M is sufficient as increasing M beyond 5 does not further improve performance. Finally, we evaluated our method with larger number of agents, specifically by using double or triple the number of agents compared to our standard configurations. The results in Figure digure/ddmmonstrat demonstrate that our method is capable of handling a larger number of agents without affecting performance.
7 CONCLUSION
This work introduces Greedy Sequential Execution (GSE), a unified solution designed to extend value decomposition methods for tackling complex cooperative tasks in real-world scenarios. Our method employs a utility function that accounts for complex agent interactions and supports both homogeneous and heterogeneous optimal policies. Furthermore, by implementing greedy marginal contribution, GSE overcomes the relative over- senrreeerrlliztionn problem. Our experiments show that GSE significantly improves performance across various domains, especially in mixed-task scenarios.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was supported by NSFC 62088101 Autonomous Intelligent Unmanned Systems and China Scholarship Council.
REFERENCES
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learning. JEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172 2008.
Fabrizio Caccavale, Pasquale Chiacchio, Alessandro Marino, and Luigi Villani. Six-dof impedance control of dual-arm cooperative manipulators. IEEE/ASME Transactions On Mechatronics, 13(5):
576-586, 2008.
Dong Chen, Mohammad Hajidavalloo, Zhaojian Li, Kaian Chen, Yongqiang Wang, Longsheng Jiang, and Yue Wang. Deep multi-agent reinforcement learning for highway on-ramp merging in mixed traffic. arXiv preprint arXiv:2105.05701, 2021.
Filippos Christianos, Georgios Papoudakis, Muhammad A Rahman, and Stefano V Albrecht. Scaling multi-agent reinforcement learning with selective parameter sharing, In International Conference on Machine Learning. pp. 1989-199 1998. PMLR, 2021.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference Artificial Intelligence, 2018
Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang, and Yi Wu. Revisiting some common practices in cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 6863- 6877. PMLR, 2022.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In Autonomous Agents and Multiagent Systems: AAMAS 2017 Workshops, Best Papers, São Paulo, Brazil, May 8-12, 2017, Revised Selected Papers 16, pp. 66-83. Springer, 2017.
Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning. International Conference on Machine Learning, pp. 3930-3941. PMLR, 2021.
Wan Ju Kang David Earl Hostallero, Kyunghwan Son, Daewoo Kim, and Yung Yi Qtran. Learning factorize with transformation for cooperative multi-agent reinforcement learning. In Proceedings of the 31st International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2019.
Shariq lqbal and Fei Sha. Actor-attention-citiic for multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 2961-2970. PMLR, 2019.
Paul Knott, Micah Carroll, Sam Devlin, Kamil Ciosek, Katja Hofmann, Anca D Dragan, and Rohin Shah. Evaluating the robustness of collaborative agents. arXiv preprint 2rX.v:2101.05507 2021.
Jakub Grudzien Kuba, Ruiging Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2109.112511 2021.
Jinoh Lee, Pyung Hun Chang, and Rodrigo S Jamisola. Relative impedance control for dual-arm robots performing asymmetric bimanual tasks. IEEE transactions on industrial electronics, 61(7): 3786-3796, 2013.
Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang Celebrating diversity in shared meltti-geetrrimfooremmmee learning. Advances in Neural Information Processing Systems, 34:3991 -4002, 2021a.
reinforcement
10

---

Published as a conference paper at ICLR 2024
Jiahui Li, Kun Kuang, Baoxiang Wang, Furui Liu, Long Chen, Fei Wu, and Jun Xiao. Shapley counterfactual credits for multi- reinforcement learning. In Proceedings of the 27th ACM 2021b.
SIGKDD Conference on Knowledge Discovery & Data Mining, pp.
Shanqi Liu, Licheng Wen, Jinhao Cui, Xuemeng Yang, Junjie Cao, and Yong Liu. Moving forward in formation: A decentralized hierarchical learning approach to multi-agent moving together. In 2021 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pp. 4777-4784 IEEE, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Picter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-competiivee environments. arXiv preprint arXiv: 1...::/700.02275. 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. Advances in neural information processing systems, 32, 2019.
Liviu Panait, Sean Luke, and R Paul Wiegand. Biasing coevolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation, 10(6):629 6459 2006.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent bidirectionalll--coormii to play starcraft combat games. arXiv preprint arXiv: 1703. 10069, 2017.
nets: Emergence of human-level coordination in learning
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4295-4304. PMLR, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in neural information processing systems, 23:10199-10210 2020.
Bidipta Sarkar, Aditi Talati, Andy Shih, and Dorsa Sadigh. Pantheonrl: marl library for dynamic training interactions. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 13221- 13223, 2022.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 170..0077744 2017.
Lloyd S Shapley. 17. A value for r-person gumes. Princeton University Press, 2016.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. International Conference Machine Learning, pp. 5887-5896. PMLR, 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. coloosdecoooooitiion networks for cooperative multi-agent learning. arXiv preprint arXiv: arXiv: 706.05226, 2017.
Justin K Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, and Benjamin Black. Revisiting parameter sharing in multi-agent deep reinforcement learning. arXiv preprint arXiv:2005.1366 13625, 2020.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent gelaamnig. In International Conference on Learning Representations, 2020a.
Jianhong Wang, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. Shapley q-value: local reward approach to solve global reward games. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 7285-7292, 2020b.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforcement learning with emergent roles. In Proceedings of the 37th International Conference on Machine Learning, 2020c.
Muning Wen, Jakub Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. Multi- agent reinforcement learning is a sequence modeling problem. Advances in Neural Information Processing Systems, 35: 35:16509-16521, 2022.
11

---

Published as a conference paper at ICLR 2024
Erfu Yang and Dongbing Gu. Multiagent reinforcement learning for multi-robot systems: A survey. Technical report, tech. rep. 2004.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0195,, 2021.
Yifan Zang, Jinmin He, Kai Li, Haobo Fu, Qiang Fu, and Junliang Xing. Sequential cooperative multi-agent reinforcement learning. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 485 0035-993 2023.
Lianmin Zheng, Jiacheng Yang. Han Cai, Ming Zhou, Weinan Zhang, Jun Wang, and Yong Yu. Magent: A many-agene reinforcement learning platform for artificial collective intelligence. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
12

---

Published as a conference paper at ICLR 2024
A RELATED WORK
Recent works have extended MARL from small discrete state spaces (Yang & Gu 2004 Busoniu
et al., (008)) to high-dimensional, continuous state spaces (Lowe et al. 2017 Peng et al., 2017)
The progresses of deep reinforcement learning give rise to an increasing effort in designing general-
purpose deep MARL methods for complex multi-agent environments, including COMA (Foesster ct al. 2018). MADDPG (Lowe et al., 2017), MAPPO (Yu et al., 202I) and etc. Currently, CTDE
is considered to be the de facto mainstream paradigm in this field (Lowe et al.] [qal] & Sha 2019). In terms of specific methods, the Value- Decomppsoooooiio Network (VDN) (Sunehag et al. 2017) utilizes the factorization of joint-action Q-values as the sum of each agent's s utility. QMIX (Rashid
ct al. 2018) is am extension of VDN which allows the joint action Q-value to be a monotonically increasing combination of cach agent's 's utility, which can vary depending on the global state. There are also other variants proposed to extend the applicability of the value decomposition methods. For
instance, QPLEX (Wang et al.) 2020a) and QTRAN (Son et al., 2019) aim to learn value functions with complete expressiveness capacity. MAVEN MMahajan et al. (019)) hybridises value and policy- based methods by introducing a latent space for hierarchical control. This allows MAVEN to achieve committed, temporally extended exploration. Weighted QMIX (Rashid et al. 2020) is based on QMIX and rectifies the suboptimality by introducing weights to place more importance on the better joint actions. Vnn (Gupta et al. (02T)) learns set of related tasks simultancously with linear decomposition of universal successor features. Despite the effectiveness of these methods, they are commonly designed to facilitate the learning of similar policies, it can be detrimental to the acquisition of heterogeneous policies.
To solve the heterogeneous tasks, previous methods choose to add agent-specific information to the observation or assign different roles to learn the distinct policies. PSHA (Terry et al. 2020) proposes an agent indication to enable agents to represent heterogeneous policies. CDS (Li al. 202
uses mutual information to Iearn an agent ID-specific policy to deal with the problem of learning diversity policies. ROMA (Wang et al. 2020c proposes role-oriented MARL framework to make agents specialized in certain tasks. However, these methods, which solely focus on learning distinct policies, often come at the cost of sacrificing the advantages associated with learning in homogeneous scenarios. Furthermore, these methods tend to learn fixed policies that lack the necessary flexibility.
Other methods use sequential execution policy represent distinct policies. AR (Fu al. 2022) proposes a centralized sequential execution policy to solve permutation games. MAiF (Liu et al. 2021) uses a sequential execution policy to learn a path-finding and formation policy for a multi- agent navigation task. These methods can represent the optimal policy in both homogeneous and heterogeneous scenarios. However, a naive sequential execution policy is not guaranteed to converge to optimal policy and has the problem of credit assignment. Additionally, there are also methods such as HAPPO (Kuba et al. (22T)) that use sequential policy updates to guarantee monotonic policy improvement of PPO (Schulman et al.) 2017). MAT (Wen et al., 2022) adopts sequential policy updates within the structure of a transformer. This design is aimed at executing updates both monotonically and in parallel, thereby enhancing the time efficiency compared to previous methods like HAPPO. SeCA (Zang et al. (223) constructs a new advantage value to improve upon PG-based methods. Different from focusing on an increment of PG-based methods, our work is proposed to extend the applicability of value decomposition methods to solve the mixing of homogeneous and heterogeneous tasks.
Our work is also related to the credit assignment. Previous methods usually use implicit credit assignment methods to learn the policy, such VDN and QMIX. However, explicit credit assignment methods have also been proposed. For instance, COMA (Foerster et al. 2018) utilizes a counterfactual advantage to learn the value function. Other methods use Shapley Value (Shapley) 2016) as the credit value of each agent. Shapley Value originates from cooperative game theory and is able to distribute benefits reasonably by estimating the contribution of participating agents. In these methods, SQDDPG (Wang et al.) 2020b) and Shapley (Li et al., 2021b) use Shapley Value to estimate the complex interactions between agents. However, these methods can only get approximated Shapley value as calculating the Shapley value involves exponential time complexity (Wang et al.) 2020b) and they are not designed to learn similar and distinct policies simultancously. In this work, we introduce an explicit credit assignment method using marginal contribution in Shapley value to learn a sequential execution policy that can represent the optimal policy in scenarios with a mixing of homogeneous and heterogeneous tasks.
13

---

Published as a conference paper at ICLR 2024
B SCENARIOS SETTINGS AND TRAINING DETAILS
In the Multi-XOR games, agents receive two types of rewards, as illustrated in Table I and Table displays the homogeneous reward, which exhibits a non-monotonic payoff. This poses challenge of relative overgeneralization for the learning process. Table 2 presents the heterogeneous reward, where agents are required to take distinct actions. Specifically, if two agents choose the joint actions C&C' to solve the task, the other two agents must choose L& L; otherwise, penalty will be imposed. However, all agents select L&L, the return will be zero.
In MAgent, each agent corresponds one grid and has a local observation that contains square view centered at the agent and a feature vector including coordinates, health point (HP) and ID of agents nearby, and the agent's 's last action. The discrete actions are moving, staying, and attacking. The global state of MAgent is a mini-map (6 x 6) of the global information. The opponent's 's policies used in experiments are randomly escaping policy in pursuit. We choose five different scenarios lift, heterogeneous _ift, paalii_argee__ji pursuit and bridge. There are detailed settings of these scenarios, shown in Table 3 We demonstrate the payoff matrix by showing the R the reward returned when cooperation is achieved, Pho as are penalty when taking cooperative action but failing achieve cooperation in homogeneous scenarios, and Phe as the penalty for taking the same action in heterogeneous scenarios.
L
C
+0.5
-0.3
L.
-0.3
0
Table I: Homogeneous payoff matrix of the Multi-XOR game.
C&C
L&L
C&C
-10
+0.5
L&L
+0.5
0
Table 2: Heterogeneous payoff matrix of the Multi-XOR game.
Lm
Heteroganoosl..
Lin
Bridge
Agent number
Object number
Map
Payoet
R- 0,0...
R-1.A
0.
100
R-0.5
4.2.A. - 20.40
R-0.S.A.
R-0..
Table 3: Settings of MAgent Scenarios. R is the reward, Pho is the penalty of mis-coordination of homogeneous behavior, Phe is the penalty of mis-coordination of heterogeneous behavior.
In the Overcooked environment, the objective is to perform series of tasks involving onions, dishes, and soups. The agents are required to place onions in pot, let them cook for timesteps, transfer the resulting soup into dish, and finally serve it, which rewards all players with are six possible actions available to the agents: up, down, left, right, noop (no operation), and interact. Notably, the action of picking up onions requires two agents to simultaneously take the "interact" action, otherwise a penalty of -0.1 is incurred. On the other hand, actions such as putting onions into the pots can be performed by a single agent. To evaluate the difficulty level of different scenarios, we have designed three maps with varying levels of complexity. The easy map consists of more onions and a smaller map size (5 (5)5), making relatively easier to solve. The medium map, on the other hand, contains a single onion and a smaller map size (5x5). Finally, the hard map poses a greater challenge with its larger map size ()) and single onion, making exploration more demanding for the agents.
of 20. There
We set the discount factor as 0.99 and use the RMSprop optimizer with learning rate of 5e-4 for policy and le-3 for the critic. The e-greedy is used for exploration with annealed linearly from 1.0 to 0.05 700k steps. The batch size is and updating the target network every 200 episodes. The length of each episode in MAgent is limited to 100 steps in bridge and 50 for others, except for Multi XOR which is a single-step game. The sample number M of our method 5 in all scenarios. We run all the experiments five times with different random seeds and plot the mean/std in all the
14

---

Published as a conference paper at ICLR 2024
Figure 7: The images of the map of Overcooked tasks. From left to right is easy, medium and hard.
figures. All experiments are carried out on the same computer, equipped with Intel(R) Xeon(R) Gold 5218R CPU 2.10GHz, 64GB RAM and NVIDIA RTX3090. The system Ubuntu 18.04 and the framework is PyTorch.
C DETAILS OF MODEL IMPLEMENTATION AND HYPERPARAMETERS
The network of all compared methods uses the same LSTM network, consisting of a recurrent layer comprised of a GRU with a 64-dimensional hidden state, with one fully-connected layer before and two after. All mixing networks use fully-connected layer with 32-dimensional hidden state. The network of our critic and policy uses two fully-com cully-connected layers with 04-dimensional hidden state and one fully cully-connected layers with 32-dimensional hidden state after.
D PROOF OF THE VALUE DECOMPOSITION OF CRITIC
First of all, according the decentralized execution setting, there exists reward decomposition, r'( a,))
Ttor(3 u) ri u) E
(12)
This is because if the task can be solved by decentralized execution. the observation of each agent must contain all the necessary information to identify the goals. Otherwise, agents will require density communication to receive information about others' observations to identify the goals, which not the setting that we discussed in our works. Then, we define the value decomposition Q which models each agent's 's individual utility. From Eq. 12). we have
Qior u) E EE roor (8, m]
Em Focamlo,, u7 (T,uTaa) a.) [ = E.= Q w).
(13)
In addition, we have
arg max (Qoor u)) arg ( u)) arg max
(14)
The first part is because the value a; is represented by item Q: and the reason for the second part that Q: is only related to agent well the actions of potential cooperative agents and all the necessary information is contained in (Te, u, .aa).
get the unbiased estimated value of Q' given (Ti, u, a.). Therefore, from Eq. 13 and Eq. [14] have
arg max max(Quoo(ss, u)) {arg max (Q. " a1)). .... arg max (Tns U an))).
(15)
An intuitive understanding of Eq. 15) that each agent takes action based on the perception of other potential cooperative agents' actions, they can take the corresponding cooperative action and the joint action is the optimal cooperative joint action.
E LIMITATIONS OF INDIVIDUAL UTILITY
E. HOMOGENEOUS SCENARIOS
First, for the homogeneous task, have the payoff matrix in Table Since, indicate that the
15

---

Published as a conference paper at ICLR 2024
B
A
+
-2
B
-Y2
0
Table 4: Example of a homogeneous payoff matrix.
A
B
A
T2
tri
B
tri
r2
Table 5: Example of heterogeneous payoff matrix.
individual utility (T dz), should viewed as a variable sampled from distribution (e up a.).
Following this conclusion, we have the loss of (T 04) should be
== =m= Ps (Q) u ..,) - Qi(T).
(16)
where Q means the ground true value function, u means of the combination of uy and pv: is the possibility of u.: occurred. Therefore, Qi(Ti, a;) learns the converged value by optimizing L, we have the converged Qi(T;, a,) when L, is minimized,
(T)))) Ek Pk: Q'(TT, ..))
(17)
For a simple demonstration, we take the example payoff into Eq. (17). The value of cooperative action of is
(.( = Pa Q7(T) .0]) + pb 2 (T ,
(18)
where Pa means the possibility of other agent taking cooperative actions nt=** (u,- A) and ps means the possibility of other agents taking the other actions uh- (uk- B). Additionally, we have
Pe + Pb
(19)
Similarly, we have the value of lazy action aj as
( o. Pa Q'(TT, u, a.)) + ps Vo((T, a7))))))
(20)
We know the policy represented by (T,, a;) fails when Qi(Ts, 0, larger than (T, (T), which
is
Qi(T,, - Q.(T., a3) Pa (Q)((T, u, 0, Ce(TT, u," aa)))))) +p- ( (T,, u7 a, (' up az)) >
(21)
We take the +r1 and -r2 into Eq. 21
(T( - QI(T,, = Pa (-r2 r1) + pb (0- (-r2)) = (pr - 1) (r2 + r1) + Pb T2 >> 0
(22)
This means the policy represented by (T as) will fail when
F1 (1 pb) (2pb 1) r2-
(23)
which equals to
206-1
(24)
F2 T-ps
E.2
HETEROGENEOUS SCENARIOS
First, for the heterogeneous task, have the payoff matrix in Table Similarly, agents with the policy represented by Qi(T,, a;) fails when QT 0, ) is larger than Q,(7i, az) in the heterogeneous scenario. However, there are multiple optimal joint actions (1=A,2=B), (1=B,2=A), which are different from the homogeneous scenarios. We first consider the (1=A,2=B) situation which
QT(T,,07) - Qi(T,, at) Pb (Q, "," ,a,)) - (. ",,"4"aa))) .af))
(25)
+p. (Q)((T, a, - Q'(TT, 2,,7,,,,,)) a()) > 0
16

---

Published as a conference paper at ICLR 2024
Taking the the +r1 and -r into Eq. 25
Qi(T,, (T 0.) = pb (-r2 Pa (ri (-r2))
(26)
Pb. (r2 + r1) + (1 pb) (r2 m1) > 0
which equals to We notice that the overall possibility of failure is
1 2pb >
(27)
Pb 1
(28)
For situation (I=B,2=A), we have similar conclusion,
Pa 3
(29)
Pj = P(pa < + P(ps < ( - P((1 ph) pb) < 1)) P(ps < ()) = P( < pb) + P(ps < 1.
(30)
Therefore, the policy represented by Qi a;) can never promise to solve the heterogeneous task. Furthermore, we can calculate the possibility of reaching cooperation,
P. P((1 B,2 A)) P((1 A, B)) pb Pa + Pa Pb 2 pb (1 (1-p))- (31)
The maximization of Eq. 311 is 0.5 when ps 0.5. The result demonstrated that decreasing ps when ps < 0.5 causes cooperation more difficult to be reached.
F ANALYSIS OF INDIVIDUAL UTILITY OF SEQUENTIAL EXECUTION POLICY
We have the IGM principal as arg max Qrar u)) (arg max (TII,(Q(T,, arg max (Qn (Tn an))).
(32)
For sequential execution method, the policy the form of
u { (arg max (T1 a1)), arg max(Q (T,, 01n- an))) on
(33)
#1
We take the payoff matrix in Table as an example, there are multiple optimal joint actions (1=A,2=B), (1=B,2=A), we take the optimal actions into Eq. (33).
(1 A,2 B) (arg max (T) a1)) arg max (T,, (,,)) 41
(34)
(1 = B, A) farg max
arg megmax((2 (' (T; B,a,))).
We notice that although the latter utility has the correct maximization of the utility, the former one has a conflict maximum result as it lacks the necessary information about other agents' actions.
17


Reviews:
[{"review_id": "97WHERlXOo", "reviewer": "Reviewer_CQwR", "summary": "The authors propose a general framework for solving both homogeneous and heterogeneous cooperative tasks, which they call Greedy Sequential Execution (GSE). The key idea behind GSE is to sequentially execute the actions of each agent, while taking into account the dependencies between agents measured by greedy marginal contribution.", "questions": "I have no further question.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The analysis in Sec 3.1 is valuable for readers to gain a deeper understanding of the performance of different policies in homogeneous and heterogeneous scenarios.", "weaknesses": "The authors claim that existing solutions have not been successful in **addressing both homogeneous and heterogeneous** scenarios simultaneously, and thus GSE is the first to propose for both scenarios, whose key idea is integrating **sequential execution** and **value decomposition** framework for better **credit assignment** and **cooperation**. However, [1] was published in 2022, which also proposed a general framework based on **sequential execution** for **cooperative games** with **both homogeneous and heterogeneous** agents, and leveraged **advantage value decomposition** for **credit assignment**. \n\nThere are too many overlaps in key ideas between these two works, while the main difference seems to be [1] implements these ideas with PPO and sequence model, i.e. transformer, and GSE implements these ideas in a QMIX-like pattern.\n\nHowever, I have not found any comparison, discussion, or citation to [1] in this paper, which should be compared thoroughly, or the contributions might be significantly weakened.\n\n[1] Wen, Muning, et al. \"Multi-agent reinforcement learning is a sequence modeling problem.\" Advances in Neural Information Processing Systems 35 (2022): 16509-16521.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N1ua7CJlpJ", "reviewer": "Reviewer_ia9o", "summary": "The paper presents a unified framework for learning policies for multiple agents where there are homogeneous and heterogeneous tasks, with the goal of addressing limitations of current methods that work with either homogeneous or heterogeneous tasks. Specifically, the paper proposes greedy sequential execution, with value decomposition including a utility that encodes also the interactions between agents and credit assignment calculated as marginal contribution of Shapley values. Simulation experiments considering different types of tasks are performed and results include comparison with other methods.", "questions": "Please comment on the trends of overcooked as mentioned in the \"Weaknesses\" box.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the paper addresses an open problem in MARL, where a general framework able to learn optimal policies for both homogeneous and heterogeneous tasks is still not fully present.\n\n- the paper presents a technically sound method, with the augmented utility, sampled considering the joint actions of other agents who might cooperate, and with the greedy marginal contribution \n\n- the paper includes a fairly comprehensive evaluation of the proposed method and compares with a good number of state-of-the-art approaches, with corresponding insights from the results, as well as ablation studies.\n\n- the paper has a structure that overall clearly show the gap, with specific examples, and motivates the proposed approach.", "weaknesses": "- a trend that should be discussed more in detail is in Overcooked, where there is a large standard deviation for both Easy and Medium, with Easy having a decreasing return past 900 episodes. It seems that it didn't converge.\n\nA few minor presentation comments: \n- Section V already introduces comparison methods that are presented in Section VI. It is better instead to introduce the comparison methods in Section V so that the reader doesn't have to guess what methods are they.\n- it is worth including graphically the map for the overcooked environment.\n- the references, when the authors name are not used in the sentence should be all in parentheses, e.g., \" experiences Sunehag et al. (2017); Rashid et al. (2018).\" -> \"experiences (Sunehag et al., 2017); (Rashid et al., 2018).\"\n- please ensure to include the correct venue for papers, instead of just including the arxiv version, e.g., the MAVEN paper was published in NeurIPS 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wEG0n7U2j1", "reviewer": "Reviewer_GHAQ", "summary": "The paper proposes a way of handling cooperative tasks with multi-agents when the tasks are not all homogeneous.\nThe approach proposed uses sequential execution policies, proposing the Greedy Sequential Execution (GSE), which learns the optimal policy for both cases (homogeneous and heterogeneous tasks). The GSE is evaluated empirically in multiple domains. The GSE  uses a value decomposition method that works for both homogeneous and heterogeneous tasks, and enables the agents to learn utilities that take into account the interactions with other agents. They also propose a credit assignment method that computes the marginal contributions of each agent. The marginal contribution avoids over-generalization, since it represents the optimal value of an action instead of the average value. A couple of theorems are proved in an appendix (not attached to the paper). The experiments use homogeneous scenarios, heterogeneous scenarios, and mixed scenarios. \nMultiple appendices are mentioned but they are not attached to the paper and are not accessible.", "questions": "1. The use of Monte Carlo method to estimate the optimal cooperative actions with previous agents to maximize the greedy marginal contribution is mentioned with no other details. How is the number of actions selected?\n2. In the Overcooked scenario, I understand why the size of the map affects the complexity, but there is no indication of how large the maps are. I believe the number of agents is fixed to two. Have you tried a larger number of agents?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written and easy to follow. The work presented addresses a known problem (over-generalization) that takes place when combining homogeneous and heterogeneous tasks and expands the applicability of agent-based approaches to situations where some tasks are homogeneous and some are heterogeneous. Having to deal with a mix of the two types of tasks might not be too common, but when mixes of tasks are used, the approach proposed here, even if greedy, becomes quite useful.", "weaknesses": "The paper is more appropriate for a journal than for a conference. The numerous appendices are not included in it for space reasons, but are important to understand the method more in depth.\nFigure 2 with the architecture is hard to read and not well explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mC8FEcsu8T", "reviewer": "Reviewer_CxDZ", "summary": "The authors incorporate sequential execution into a value-decomposition-based MARL algorithm, which can thus be applied to both homogeneous and heterogeneous tasks, while maintaining effective credit assignment. \nTwo approximations are involved: 1) using greedy marginal contribution as the assigned credit for each individual, and 2) using greedy actions (augmented by Monte Carlo samples) as the optimal actions taken by subsequent agents.\nThe experiments show the efficacy of this approach, demonstrating its ability to adapt to dynamically changing partners within homogeneous, heterogeneous, and mixing scenarios.", "questions": "- To generate a joint action $u$, each agent must calculate its action $a$ sequentially, which prevents parallel processing. Therefore, with each agent requiring $t$ time to produce its action, a single environment step requires $n*t$ units of time for $n$ agents. Compared with baseline algorithms like QMIX, does GSE require more wall-clock time for training and evaluation? If so, could you provide a rough estimate of the additional time required?\n- During training, is the execution sequence of all agents fixed, or do you shuffle the sequence?\n- What does 'training with a larger scale of agents' mean in Section 6.3 & Figure 6?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Originality. The proposed method addresses common problems in MARL algorithms, such as the relative overgeneralization and credit assignment, at the same time. This enhancement expands the scope of potential applications of value-decomposition-based MARL algorithms. \n- Clarity. The paper is basically clear and easy to follow.", "weaknesses": "- The algorithm is tested exclusively on specially designed tasks. There are no additional experiments conducted on common benchmarks.\n- The ablation study section fails to provide an in-depth discussion of the functions of the key components in the algorithm. I would appreciate a more detailed description of the ablated algorithms and a clearer explanation of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)