LPMARL: Linear Programming based Implicit Task Assignment for Hierarchical Multi-agent Reinforcement Learning
Authors: Kyuree Ahn
Jinkyoo Park
Venue: Submitted to ICLR 2023 (2023)
Keywords: Linear programming
Multi-agent reinforcement learning
Hierarchical multi-agent reinforcement learning
Implicit deep learning

Abstract: Training a multi-agent reinforcement learning (MARL) model with sparse reward is notoriously difficult because the terminal reward is induced by numerous interactions among agents. In this study, we propose linear programming-based hierarchical MARL (LPMARL) to learn effective coperative strategy among agents. LPMARL is composed of two hierarchical decision-making schemes: (1) solving an agent-task assignment problem and (2) solving a local cooperative game among agents that are assigned to the same task. For the first step, LPMARL formulates the agent-task assignment problem as linear programming (LP) using the state-dependent cost parameters generated by a graph neural network (GNN). Solving the LP can be considered as assigning tasks to agents, which decomposes the original problem into a set of task-dependent sub-problems. After solving the formulated LP, LPMARL employs a general MARL strategy to derive a lower-level policy to solve each sub-task in a cooperative manner. We train the LP-parameter generating GNN layer and the low-level MARL policy network, which are the essential components for making hierarchical decisions, in an end-to-end manner using the implicit function theorem. We empirically demonstrate that LPMARL learns an optimal agent-task allocation and the subsequent local cooperative control policy among agents in sub-groups for solving various mixed cooperative-competitive environments.

Under review as a conference paper at ICLR 2023
LPMARL: LINEAR PROGRAMMING-BASED IMPLICIT TASK ASSIGNMENT FOR HIERARCHICAL MULTI- AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Training multi-agent reinforcement learning (MARL) model with sparse reward is notoriously difficult as the terminal reward is induced by numerous interactions among agents. In this study, we propose linear programming (LP)-based hierar- chical MARL (LPMARL) to learn effective cooperative strategies among agents. LPMARL is composed of two hierarchical decision-malee schemes: (1) solving agent-task assignment LP using the deateddeenddnnt cost parameters generated by a graph neural network (GNN) and (2) solving low-level cooperative games among agents assigned to the same task. We train the LP GNN and the low-level MARL policy in an end-to-end manner using the implicit function theorem. We empirically demonstrate that LPMARL learns optimal agent-task allocation and the subsequent local cooperative policy for agents sub-groups for solving various mixed cooperative--ompettiive games.
INTRODUCTION
Multi-agent reinforcement learning (MARL) has recently drawn much attention due to its practical and potential applications in controlling complicated and distributed multi-agent systems. Despite its potential, training an MARL model with sparse reward is notoriously difficult as the final sparse reward induced by the complex long-term interactions among the agents (Liu et al. 202T). To overcome this challenge, one needs to develop an algorithm that can learn how the interactions among the agents over long-term episodes entail the outcome of the target tasks, delayed and sparse episodic reward, and deduce this understanding into effective sequential decision-making policy.
In this study, propose linear programming- hierarchical MARL (LPMARL), hicrar- chically structured decision-making scheme, to learn an effective coordination strategy among the agents. LPMARL conducts two hierarchical decision-making: (I) solving an agent-task assign- ment problem and (2) solving local cooperative games among agents that are assigned to the same task. For the first step, LPMARL formulates the agent-task assignment state-dependent cost coefficients generated by a graph neural network (GNN). The solution of the formulated LP serves as an agent-to-task assignment, which decomposes the original team game into a set of smaller team games among the agents that are assigned to the same task. LPMARL then employs a general MARL strategy solve each sub-task cooperatively in the second step. We train the L. P--paammetr-- generating GNN layer and the low-level MARI policy network in an end- to-end manner using the implicit function theorem. We validate the effectiveness of LPMARL using various cooperative games with constrained resource allocation.
an LP by using the
The technical contributions and novelties of the proposed method are follows:
Interpretability (Section 6.2.1). LPMARL can induce the designed behavior of the agents (i.e., behavior inductive biases) by using specific objective terms or constraints when for- mulating the LP. This structured framework helps one to interpret the decision-making procedure.
Transferability (Section 6.2.2). LPMARL learns to construct and solve the task assign- ment optimization problems. When constructing resource assignment LPP problem, I.P.

---

Under review as a conference paper at ICLR 2023
MARL uses GNN to produce the state-dependent cost coefficient that will be used in the objective function of the LP. Due to the size eeeeraaizatiio/ttasffraabil of GNN, the trained LPMARL policy can be used to solve general target problems with varying number of agents, tasks and constraints.
Amortization (Section 6.1 To execute LPMARL,, the agent must solve the LP so as to use the optimal solution as the high-level action. As this centralized execution may be impossible in the real world, we amortize the central solution folution-finding procedure using learned distributed task selection network. In the experiment, we demonstrate that the amortized high-level policy does not degrade the performance of the centralized version of LPMARL and outperforms existing hierarchical MARL algorithms.
2 BACKGROUND
2.1
HIBRARCHICAL MULTI-AGENT REINFORCEMENT LEARNING
Tang et al. 2018) introduced a hierarchical Dec-POMDP that is composed of high- and low-level actions, which run different time scales. This study introduced a temporal abstraction concept to integrate the two types of actions into the overall environmental dynamics. To be specific, each agent receives observation Oir and chooses high-level action af, E Af,, where A denotes a set of possible high-level actions. While the high-level actions may last for T timesteps, the low-level actions are executed until the current af, is terminated. After af, ends, the next high- level action af,++ is selected based on observation 0,,477- The agent receives a low-level reward (intrinsic reward) for reaching a sub-goal, denoted by r'(st, 0t, st+1la",e). depending to its own high-level action af The agent receives the high-level reward n² (s1, ae: 81+1) whenever the agent accomplishes the whole task, i.e., reaching the final success state ST+1.
2.2 IMPLICIT DEEP LEARNING
Implicit deep learning is a framework that incorporates implicit rules (e.g.. ordinary differential equation (Chen et al. 2018), fixed-point iterations (Bai et al. 2019), and optimization (Amos & Kolter, 2017)) into a feed-forward neural network. Specifically, differentiable optimization is a optimization problem into the layer. A differentiable optimization
framework that incorporates layer takes the problem specific pamameters x as an input, and finds optimal solution 2 (xx) such that 2" (x) arg min zen(n) I (2,xx), where f(2, x:) is the objective function constructed with given x.
The output of the layer, 2" (xx), then fed into the next layer to conduct various end tasks.
By using this approach, one can infuse the optimization inductive bias into the layers. OptNet (Amos) & Kolter 2017). for example, propose differentiable optimization layer, specifically for quadratic programming (QP). The backpropagation of this optimization layer requires the computation of the derivative of the QP solution with respect the input parameters. which derived by taking the matrix differentials of the KKT conditions of the QP. Ferber et al.) (2020) and Wilder et al. (2019) extended the idea of OptNet to general LP and mixed-integer LP (MILP). To compute the gradient of the optimal solution in combinatorial optimization easily, Vlastelica et al. (2019) suggests way to construct a continuous interpolation of the loss function.
RELATED WORK
Hierarchical MARL with pre-defined high-level action space. Some studies introduced hierar- chical policies with pre-defined goal-level actions in MARL to decompose the main problem into subproblems under a semi-MDP framework (Sutton et al. 1999). Tang et al. (2018) applied a tem- porally abstracted high-level policy to induce the agents to cooperate when selecting the sub-goals. Ahilan & Dayan (2019) also introduced a centralized sub-goal selection policy to assign the agents to tasks optimally. Liu et al. (2021) introduced an exploration policy, which acts high-level policy, to limit the explorable action space of the low-level policy. Although these methodologies leam to divide the agents into goal- deleddepnndnnt sub-groups cooperatively, the low-level policies of these algorithms are trained individually, making it difficult to induce cooperation among the agents within the sub-tasks.
2

---

Under review as a conference paper at ICLR 2023
4.1. Constructing agent-task score
4.2. Solving agent-task assignment
4.3. Seleeting low-level action
Graph emioodding
** A0
LPMARL
max Ryjy k.t. Ry Zise Ry S
sulve
** (er)
State
agent
task
Coefficient, Gyon
Assignment problem
Solution, Zisst
Low-level cooperation
Dec-LPMARL
**
Oeservation
emboodding
++00 aefter
== D(#*,
Ohservation (0:)--101
ngent
task
High level policy,
Low-level cooperation
Figure 1: Overall decision-making framework of LPMARL
Hierarchical MARL without pre-detined high-level action space. Some studies employed a bi- level learning structure MARL learn the latent goals without pre-defining high-level action set. Wang et al. (2020a) proposes to learn the latent goal of the agents by using the mutual information between the goals and the trajectories. Wang et al. (2020b) proposes learn the latent representation of the action to cluster the joint action into the role action space. Yang et al. (2019) defines the low-level reward as a combination of team reward and intrinsic reward to balance the learning of
the cooperation and individual skills. These methods indirectly limit the state space of the agents because the agents learn the policy that is conditioned on the latent embedding. Training the latent goal typically requires lot of training loops with dense-reward signal.
Optimization-bann based agent-task decomposition. Our work draws inspiration from Carion et al. (019)), centralized optimization-basse decomposition approach. In this paper, the high-level agent-task allocation problem formulated into LP, where the optimization parameters are dynam- ically constructed depending on the state. By learning the state-dependent objective coefficient and constraint coefficient, the agents can be allocated optimally into tasks from a centralized point of view. However, they the agents may not behave cooperatively in the decomposed subproblem. Also, the optimization problems and low-level policy training are not end-to-end differentiable when trying to train two policies together. Our study is different from this in that we train the high- and low-level policies in an end-to-end manner while backpropagating the MARL loss through the LP optimization layer by using the implicit function theorem. In addition, we amortize the central LP-solving procedure with a decentralized task allocating policy, which allows each agent to choose the sub-goal cooperatively in distributed manner, without having to solve the LP in the execution phase.
rule-based low-level policy to train the high-level allocation policy,
4 METHDOLOGY
At every step, LPMARL conducts three forward steps: (1) constructing an agent-task score matrix using GNN, (2) solving agent-task assignment LP problem, and (3) solving local cooperative games among agents that are assigned to the same sub-task in parallel. Figure shows the overall decision-making framework of LPMARL.
4.1 CONSTRUCTING AGENT-TASK SCORE MATRIX
We generate a state-dependent cost coefficient matrix C' E NxM for the LP problem. First, given the global state 8 {sy E N M) with s5. being the features node k, we construct directed graph g = (V, E) to describe the relationship between the agents and tasks explicitly, The graph nodes are composed of agent nodes N and task nodes M, i.e., V = A' U.U. M. The agent node embedding and task node embedding are initialized as the local state of the agent and task, respectively. Two sets of edges are defined; agent-agent edges, ENN = ((i.j) (i.3) e N N),, and agent-task edges, ENIM= {(i,)) (i.j) EN x M).
3

---

Under review as a conference paper at ICLR 2023
We use message- paassigg GNN (Battggiaa et al. 2018) to encode 9 (V,E): [88, 85i MM (1, ENM
my [10, 893 0g NNN (1,5)
ENN; my
(1)
h4 t f(1 E malll E miyllss): 0²)) vi Vs
(2)
(L.))EEM
(1.)EEXN
where ONN and M are the parameters for the agent-agent and agent-task edge update functions, respectively; and 6) is parameter of the node update function. We denote the GNN-related param- eters as 0g = (ov 2 {hr hev for agents and (hr HjEM for tasks constructs an encoded graph, G' (V',E")
" BNM .0'). After the graph encoding process, the updated node embeddings
Using the encoded graph node embeddings V", we can compute a coefficient matrix as follows.
Cij = (G)) f(h," hyg 0.)
where 0g are the parameters of the network computing the agent-task scores, and the coefficient cit the allocation score for agent i finish task The constructed cost coefficients will then be used to construct the objective function of the agent-task allocation LP problem as shown in Eq.
4.2 HIGH-LEVEL. POLICY: SOLVING AGENT-TASK ALLOCATION OPTIMIZATION
Centralized high-level policy. We formulate the high-level agent-task assignment problem into an LP, especially for the resource-constrained allocation problem, as follows:
maximize
Σ 1
Cij Fij
(4)
s.t.
Σ Zij S kj
VjEM
(5)
Σ Fij =
ViEN
(6)
8
0 S 25 I 1
MEN,EEM
where (ZyJNeNN is the decision variable that is to be optimized in a central way. Eq. is the objective function that we want to maximize, Eq. [S] the capacity constraint that restricts the maximal number of agents that can be assigned to each task, Eq. 7 are the constraints that ensures that the assignment probability of each agent is properly defined.
The optimal solution of the LP, 2 = (ZiyheN.EEM. can be considered as the output (assignments)
of the high-level policy, i.e., T";:0n) : 7" where =iy the probability that agent i is assigned
to task j. Agent i then selects an action at using this probability, i.e., T² ra(aa = j] = =.y. Once every agent is assigned which are composed of agents assigned to the same task. Formally, we denote the optimal solution Z" = Z (Co (G')) function of the input coefficients Co. (g') XM produced by graph g'.
one of the tasks, the agents are decomposed into sub-groups, each of
Decentralized high-level policy. LPMARL has a centralized task assignment scheme as LP should be solved during both the training and execution phase. As the centralized execution may not be fea- sible during the execution level, we propose Dec-LPMLARL. a decentralized version LPMARL, assign each agent a task in decentralized manner without solving LP centrally.
To this end, in Dec-LPMARL, each agent's decentralized policy amortizes the optimum task al- location of LPMARL as # jlo:) - where a!! is the GNN-based prediction function that maps the local observation to the action selection probability & of agent i. Note that this imitation policy still considers the relationships among tasks and agents captured by the local obser- vation (s). We use the shared decentralized policy a = +
# = A and 4 is trained minimize the cross entropy between Z and 2". Figure shows how each agent makes its high-level assignment action and coordinates with other agents in a decentralized manner with Dec-LPPMAARL.
4

---

Under review as a conference paper at ICLR 2023
4.3 LOW-LEVEL POLICY: SELECTING LOW-LEVEL ACTION
Once the global problem is decomposed into sub-tasks, the agent-task assignment is maintained for multiple timesteps until one of subtasks is finished. While the high-level action is fixed, each agent executes the low-level action in a decentralized manner every timestep to accomplish the assigned task cooperatively. For example, given the node embedding he of agent and the embedding h of the selected high level task af. agent selects the low level action af as:
of ~ T' (+lo,, ) f(h,". N: 01).
where O2 is the parameters of the low-level policy.
5 TRAINING
We train the parameters 8n of the high-level policy and the parameters 8 of the lower-level policy the same time by using the weighted sum of the high-level objective [On) and the lower-level objective (0:):
= J(0,) (1 w) J(OO,)
We observed that high-level policies are harder to train than low-level policies at the beginning of the training because high-level rewards are more sparse than low-level rewards. Thus, stabilize the training procedure, we schedule the varying of w. We set = 0.9 initially and decayed linearly to w 0.1. Ways for computing Ve, [(%) and V [O:) is as following.
5.1 ACTOR AND CRITIC FOR THE HIGH-LEVEL POLICY
Critic. The high-level critic (b)) is trained minimize the the loss L(dn), defined as:
[
) (10)
[(6x) = (s. (ts.af.rh,s/00 a
r
max Er
of δn) Q*L4T, Q" (st. ai, (n))
where on is the target parameter. Since the same high-level action can be maintained for multiple timesteps, the target of the high-level critie discounted proportionally to the duration when the high-level action remains the same.
Policy Gradient. The gradient of the high-level policy, Vo, (On). can be expressed as:
00 [(0)) Be n o/)
Σ (st, (i)) Vo, log म
(aa, (ale 0n)
(11)
Σ E ("r. σn) Ve, log Lla (s: Bx)
(12)
The combined procedures of (1) computing the node embedding, (2) constructing the agent-task score matrix C, and (3) solving the agent-task allocation problem can serve as the high-level policy. This decision-making pipeline constructs the following forward propagation chain:
7 (:; 8t
On
solver 2" loss T
(13)
Then, Ve, ((hh) can be computed as the following chain rule:
0J
(C*
0C
Vo (On)
(14)
07*
aC
00,
In our optimization problem, there exists some extreme points generated only by the boundary con- straints in Eq. 7 Thus, the optimal solution (C(C') can be an integer value at these extreme points (please refer to Appendix A for detailed description). In this case, the derivative (2" can be in the form of the piecewise constant, making it difficult to estimate the gradient. Mastelica et al. (2099) proposed approximate the differentiation of integer programming layer to obtain
5

---

Under review as a conference paper at ICLR 2023
meaningful gradient. The partial gradient 0j (2) 0y is approximated by the solution gap ac
between solution Z" of the original LP and solution ž of the perturbed LP:
0J ac ~ -2X
(15)
The perturbed optimal solution 7 is constructed by injecting the perturbed cost into the objective function of the LP (Eq. 4 This equation can be interpreted as an approximation of the tangent of non-differentiable function using the slope between two discrete points. Please refer to Appendix B for more details on the backward computation of the optimization layer.
5.2 ACTOR AND CRITIC FOR THE LOWER LEVEL POLICY
Critic. The objective of the low-level policy is to maximize the sum of the individual low-level rewards assigned same task. Using the value function factorization (Sunehag al. 2017) the low-level critic Q' (:; 0r) is trained to minimize the loss [()r), defined as:
[(di) Bg Ba
Σ JEM
max ('s'', - Σ s,a==j
(16)
of
where r is team reward of sub-group y. and oi is the target parameter.
Policy gradient. The low-level policy x r-(1s,,aa) = S(, May 01) is then trained with the policy gradient objective
Vo, [(,)( B (a
('s Vo, log 1o
(17)
EXPERIMENT
In this section, we conduct several experiments to answer the following questions: (1) can LPMARL. learn cooperative agent-task allocation, (2) is LPMARL transferable different problem sizes, and (3) can Dec-LPMARL amortize the centralized task allocation optimization procedure using de- centralized imitation policy.
We compare LPMARL with the following baseline algorithms: (1) Cooperative MARL algo-
rithms: Qmix (Rashid et al.
(Lowe al. 2017). and MAAC (Igbal & Sha 2019)
(2) Hierarchical MARL: HSD YYag et al. 2019). RODE Wang et al. 2020b) and CMA 2021
al.
In addition, we consider the two ablations of LPMARL: (1) Dec-LPMARL to check the feasibility
of decentralizing LPMARL, (2) No-LP observe the effectiveness of using LP as the high-level policy. The network architecture of No-LP and Dec-LPMARL are the same as LPMARL.
6.1 COOPERATIVE NAVIGATION
The first environment is cooperative navigation, whose objective is to learn one-to-one mapping of the agent-landmart (high-lews level action) as well as a navigation action (low-level action) to occupy all the landmarks (Lowe et al.] 2017). We consider both dense- and sparse-reward settings. In the dense-reward setting, reward is determined by the distance between the agent and the landmarks, the collision between agents, and the number of occupied landmarks. In the sparse-reward setting, an agent is rewarded only when the agent occupies the assigned landmark (+1). In both reward settings, the agents receive high-level reward when the agents occupy all the landmarks (+1).
Although CMAE does not use policies with hierarchical level. it trains an exploration policy on the shrunk region of the full state space, which resembles the decomposition procedure by high-level policy of the hierarchical MARI..

---

Under review as a conference paper at ICLR 2023
The environment rewards are provided differently to the algorithms. For the hierarchical MARL algorithms and LPMARL, each level of reward described above is used to train each policy level accordingly. For the non non-hierarchical MARL algorithms, a weighted sum of the high- and low-level rewards is used to train the policy. Additional experimental details are described on Appendix C.1
Table 1: Success ratio (%) of cooperative navigation. The mean and standard deviation of 100 evaluation episodes are reported.
Ours
Non-bicrarchical MARL
Hierarchical MARL
Scenario
LPMARL
Doc- LPMARL
No-LP
Qmix
MADDPG
MAAC
HSD
RODE
CMAE
Dense-3
99.7
89.1+-11
78.3+1.
8244-15
85.7+1.1
89.1=3.1
98.9
99.1+008
98.2+11.4
D
98.3+:15
84.5+12
44.5#53
62.0414
21.34522
74.5=46
9.
9.
84.2
Dense-7
97,9++1.4
85.74-211
56.24499
49.14:52
5.7+0.1
65.7=4.7
96.9++1.
95.8++2.00
Sparse 1
90.0++:.11
82 12.1
61.0#32
31.5+32
11881.1
49.1=49
85.5+33.
89.5
64.9-477 49.0=248
Sparse-5
89.11339
74.921
49.2:145
32.4143
8.0113
39.5=4.8
80.9+339
16.12
Spanse-
86.5-1334
72.412.1
42.0:149
12.81224
6.2110
22.1=4.1
72.1:-488
70.6:::46
impossible train CMAE N 7 due the memory allocation problems, CMAE considers joint observation space of all agents (|O,1* dimensional) when training the exploration policy.
Table shows the average performance metric of the different algorithms where Dense-N and Sparse-N refer to the dense and sparse settings with N agents, respectively. Non-hierarchical MARL algorithms fail even in simple scenarios for both the dense and sparse reward settings. In the sparse reward setting, the success ratio of non-hierarchical algorithms is less than 50%. This shows that the general MARL algorithm cannot learn cooperation only with goal-oriented and sparse reward.
Hierarchical MARL algorithms succeed in every dense-rewarded setting. However, for the sparse- reward setting, the performance of hierarchical MARL methods degrades when N increases. Unlike the other hierarchical MARL algorithms, LPMARL shows the smallest performance degradation when N increases. If LPMARL. successfully allocate task without conflict, can solve the lower- level problem easily because the complexity of the decomposed sub-problem is the same as the complexity of the single-agent navigation problem.
No-LP has 20~~0%% lower performance than LPMARL on average, which indicates the effectiveness of the L.P-based bigh-level task allocation. On the other hand, DeRRL has a slightly lower performance than LPMARL but has considerably higher performance than No-LP, which verifies the potential of amortizing the central task allocation with a decentralized task allocation policy.
6.2 CONSTRAINED COOPERATIVE NAVIGATION
To further investigate the high-level assignment of LPMARL, we produced a modified version of the cooperative navigation environment, namely the constrained cooperative navigation. In this environment, N agents aim to occupy M (M < N) landmarks, where each landmark has its own capacity limit to accommodate the agents. In this environment, the agents receive success reward only in the case when the agents occupy the landmarks while satisfying the capacity constraint. Additional experimental details are described on Appendix 2
Table 2: Normalized high- and low-level reward of constrained cooperative navigation. The reported
reward is the mean over all the agents over five runs.
Scenario
Ours
Non-hienacchiall MARI.
Hiemrchical MARI.
LPMARL
Dec-LPMARL
No-LP
Qmix
MADDPG
MAAC
HSD
RODE
CMAE
(M, N) = (3,5)
0.86
0.73
0.33
0.37
0.21
0.27
0.49
0.43
0.35
L
0.88
0.76
0.58
0.70
0.57
0.77
0.81
0.71
0.52
(M, (5
H
0.82
0.65
0.28
0.33
0.15
0.19
0.44
0.43
0.29
0.89
0.66
0.47
0.73
0.52
0.78
0.82
0.62
0.59
Table 2 shows the normalized high- and low-level reward when the algorithm is trained with (M, N) = {(335) 5), 7)). The low-level reward can be interpreted as how close the agents are to the nearest landmark on average. Note that achieving maximum low-level reward does not im- ply that the algorithm has achieved success. For example, if the agents learn to navigate toward the landmark, they will get low-level rewards even if it is not an optimal landmark. The high-level reward can be interpreted as the success or failure of the algorithm. The figure shows that none of the baseline algorithms have learned to divide the agents into M groups without violating the con-
7

---

Under review as a conference paper at ICLR 2023
straints. On the other hand, LPMARL learned optimal allocation policy and navigation policy, obtaining a 90% success ratio in the training environment. Additional experimental results including the training curves are reported on Appendix D.I
6.2.1 INTERPRETATION OF IIGHI-LEVEL POLICY
0.5
0.
Agent Lencmank
LPMARL
D stannce
Optimal solut
Figure 2: (a) Visualization of the learned coefficient of LPMARL. (b) Visualization of the agent-task distance matrix. (c) Optimal solution of LP with both input coefficients.
To interpret the learned optimization coefficient of LPMARL, we compare LPMARL with LP- distance, which uses the distance matrix when solving the upper-level assignment problem. Figure shows the learned coefficient LPMARL and distance for a single problem instance. By comparing Figure (a)-(b),
observe that the cost coefficient generating function Co. (-) generate cost coefficients that resembles the distance matrix. Although the learned coefficient function is sharper than the distance function, the optimal solution of LPMARL and theLP-distance is the same, as shown in Figure (c). This experiment demonstrates how LPMARL performs task assignments by reflecting the relationship between agents and tasks. Although this task be solved simply with distance matrices, LPMARL can work well while considering more complex relationships other than distance. Additional ablation study on high-level policy can be found in Appendix D.1.2
6.2.2 ZERO-SHOT POLICY TRANSFER
To the size transferability of the LPMARL, tested the algorithm in constrained cooperative navigation environment with different sizes. However, since the input dimension of the baseline algorithm consider in Section(6.2haas be fixed, the trained baseline model cannot be transferred to a different problem with different number of agents. Therefore, we compared the performance only with our ablation model.
Before salving
T=12
T-24
Landmark
Figure 3: Visualization of transfer policy learned from N = 5, MM = 3 to task of N 10, M = 4. The agent-landmark with the same color represents the result of the high-level assignment.
Table Success ratio (%) of the transferring policy learned on N, M E [3, 10). The gray and blue shaded cell represents the in-training distribution and out-of-training distribution respectively.
LPMARL
DPMARL
M
3
10
15
20
3
10
15
20
5
10
15
20
3
98.4
96.5
85.2
72.2
66.2
93.5
88.1
68.1
40.7
32.1
51.2
30.9
9.2
0.0
0.0
5
98.2
82.1
70.3
62.8
79.5
54.8
41.0
29.2
35.2
5.8
0.0
0.0
10
79.5
65.2
49.1
54.0
22.5
11.5
3.2
0.0
15
53.2
20
48.0
8

---

Under review as a conference paper at ICLR 2023
The cost coefficient function and low-level policy, which are constructed based on GNN, can be used to solve games with different number of agents/tasks. To test its transferability, we transferred the policy learned from N, M [3, (M NN to problem with bigger size. Figure 3 shows an example behavior of LPMARI agent on N = 10, M = 4, (k1, k2, ks. ka) = (1, 2, 3, 4). The text on the landmark indicates the capacity limit of each landmark. The leftmost subfigure in Figure the initial state of the environment, where the circles represent the agents and the cross marks represent the landmarks. In the second subfigure, the high-level policy assigns each agent a landmark with the same color. After high-level assignment, the agents navigate toward the assigned landmark, resulting in the cesstraint-saissfinn success state.
Table 3 shows the performance of the policy learned from N. M E [3, 10] that is tested on N, M E [3, 20 without further training. LPMARI. still has over 50% success rate on out-of-training distri- bution. The LPMARL policy can transfer to a bigger scenario, showing its zero-shot transferabilityy
6.3 STARCRAFT2 MICROMANAGEMENT
The last environment we consider is the StarCraft Multi-Agent Challenge (SMAC, (Samvelyan et al.) 2019). In this environment, we can verify the dynamic goal assignment of the algorithms as the number of agents/enemies may change within the episode. The baselines we consider for SMAC are CMAE (Liu et al. 2021) and SEAC (Christianos et al.) 2020), the MARL algorithms that are designed to solve cooperative tasks with sparse rewards. Note that other than CMAE and SEAC, there are no MARL algorithms that consider SMAC with sparse reward.
Table 4: Success ratio (%) Starcraft Micromanagement environment. The mean and standard deviation over 100 evaluation episodes are reported.
Map
I.PMARL.
Dec-IPMARRI
No-I.P
Qmix
CMAF
SEAC
RODE
3m1.3n (dense)
98.4+14
97.1+112
85.1+5.3
100.0-0.0
98.74:
88.94277
99.1-20.7
2m 12 (dense)
99.72:055
99.1
92.4-09
99.8
98.2
875528
99,8
35_5z (dense)
61.1139
45.6:1:2
30.2:111
63.9133.
51.3137
40.8::43
68.9
8m_Smn (dense)
92.24114
80.4-123
72.5:13.1
95.21:177
84.2:119
90
3m (sparse)
44.21:3.7
31.61200
8.41:333
10.42:30
42.2:148
8.34188
18.6222.1
2m (sparse)
44.3-1-499
21.4:1:.0
5.4:::066
13.4::333
17.24338
3:.5
35.1
(sparse)
0.0=0.0
0.0::00
0.1-0.0
0.0:0000
0.3+:00
8m Anz (sparse)
9.5+005
6.1=0.5
0.0
3.1
10.3::09
2.6
Table 4 shows the final success ratio SMAC tasks. In the dense-reward setting, LPMARL achieved at least similar or better performance than other baselines. Note that in 2m_lz, LPMARL does not conduct the high-level action since there is only a single task; nevertheless, LPMARL shows good performances, possibly due to the effective state representation module constructed based on GNN.
In the spwrre-reward setting, SEAC and RODE cannot learn cooperative policy using only sparse rewards. On the other hand, SEAC and LPMARL achieve meaningful success ratios in 3m and 2m./z. Note that LPMARL has a lower variance of success ratio than SEAC. In addition, although it is very low, LPMARL occasionally achieves a win for the difficult task 3s_5z. Although it has slightly lower success rate than its centralized version, Dec-LPMARL, it still has competitive performance compared to other baselines. On the other hand, No-LP fails to learn cooperative policy without using LP high-level policy. Additional results are reported on Appendix D.2
CONCLUSION AND LIMITATION
We proposed LPMARL to effectively solve cooperative/competiive game with sparse reward while optimally allocating agents to tasks. We demonstrated that LPMARL can decompose the agents into sub-tasks various environments with the sparse-reward. Although LPMARL learns an effective allocation policy using the optimization layer, the training speed may be slower than conventional MARL algorithms with a feed-forward network because the batch computation of the optimization layer is impossible. Although layer, we demonstrated that the central optimization of task allocation can be amortized so that task allocation can be done in decentralized manner.
method has limitations in batched-trainin training of the optimization

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sanjeevan Ahilan and Peter Dayan. Feudal multi-agent hierarchies for cooperative reinforcement learning, arXiv preprint arXiv:1901.08499 2019.
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization a layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Shaojie Bai, J Zico Kolter, and Vladlen Koltun. arXiv:1909.01377 2019.
Deep equilibrium models. arXiv preprint
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sonzaez- Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806. 01261, 2018.
Nicolas Carion, Nicolas Usumier, Gabriel Synnaeve, and Alessandro Lazaric. A structured predic- tion approach for generalization in cooperative multi-agent reinforcement learning. Advances in neural information processing systems, 32:8130-22 130-81400 2019.
Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differ- ential equations. arXiv preprint arXiv: 0011110000076666 2018.
Filippos Christianos, Lukas Schäfer, and Stefano Albrecht. Shared experience actor-critic for multi-agent reinforcement learning, arXiv preprint arXiv:2006.07716 2020.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddde modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1504-1511, 2020.
Shariq Iqbal and Fei Sha. Actor-attention-critie for multi-agent reinforcement learning. In Interna- lional Conference on Machine Learning, pp. 2961-2970. PMLR, 2019.
Jou-Jen Liu, Unnat Jain, Raymond A Yeh, and Alexander Schwing. Cooperative exploration for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pp- 6826-6836. PMLR, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-competttee environments. arXiv preprint weXiv:/706.0220 2017.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In International Conference on Machine Learning, pp. 4295-4306 PMLR, 2018.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi aueti-agent challenge. arXiv preprint arXiv:1902.04004 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv: / 1706055296 2017.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211, 1999.
Hongyao Tang, Jianye Hao, Tangjic Lv, Yingfeng Chen, Zongzhang Zhang, Hangtian Jia, Chunxu Ren, Yan Zheng, Zhaopeng Meng, Changjie Fan, et al. Hierarchical deep multiagent reinforce- ment learning with temporal abstraction. arXiv preprint arXiv: /809 000..09099000.... 2018.
Marin Vlastelica, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. arXiv preprint arXiv: 191.0219/2.02175 2019.
10

---

Under review as a conference paper at ICLR 2023
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforcement learning with emergent roles. arXiv preprint arXiv:2003.08003,, 2020a.
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang.
Rode: Learning roles to decompose multi-agent tasks. arXiv preprint arXiv:2010.01523 2020b.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1658- 1688,666.111 2019.
Jiachen Yang, Igor Borovikov, and Hongyuan Zha. Hicrarchical cooperative multi-agent reinforce- ment learning with skill discovery. arXiv preprint arXiv: /9// 19/2.0358, 2019.

---

Under review as a conference paper at ICLR 2023
A VISUALIZATION OF EXTREME POINT OF LP
abective fanctionn (Gu-))9))
Ottic collas pouts
seoeraed bonndery cooditouseeg 7)
Figure 4: Visual description of extreme points
Figure iillustrates the extreme points of the linear programming in 3-dimensional case, where the decision variables are (21, 22, 23) E R The boundary constraints are illustrated as the surface of the eube, and additional constraints other than boundary constraints are illustrated the surface generated by blue lines. In Figure 4 (left), extreme points corresponding only to the boundary constraints are marked the black dots, and the other extreme points are marked as the blue dots.
The objective of the optimization is to maximize f(z) = c1 + C222 + C323. The objective coef- ficients (c1, c3) determine the slope of the plane of the objective function, as illustrated by the red arrow on Figure 4 In Figure 4 we consider two possible optimization outcomes. For case (I), the optimal solution boundary points, and for case (2): z" occurs on the other extreme points. In case (I), the optimal solution 2" is integer-valuce
(zi 22, 23) occurs only on the extreme points that are generated by the
In our LP formulation, we have N x M boundary constraints and N M additional constraints. Thus, depending on the value of the objective coefficient and con- straint coefficients, there may exist some integer-valued solution. In addition, the solution of the LP hanges discontinuously on the continuous change the slope of the objective plane. For this reason, we need continuous interpolation the gradient of the discontinuous surface 27 8C
B POLICY GRADIENT APPROXIMATION FOR LP LAYER
The gradient of the high-level policy Vo, [(p)) be computed as the following chain rule:
(0xa))
aJ
(C) ac
ac
(18)
80,
az
a0,
We can compute the gradient (C)
(C)
ac by differentiating the equality the KKT 00
70
OC
conditions. Previous works (Wilder et al., 2019 Ferber et al.) 2020) proposed to add additional
quadratic regularization term >||=|| in the objective function (Eq. 4 to make LP smooth QP, and
induce non- non-singular Jacobian matrix to differentiate through the equality of the KKT conditions as in Amos & Kolter (2017).
However, although our high-level optimization problem is formulated as an LP, there exist extreme points generated only by the boundary constraints (Eq. [ Thus, the optimal solution may be integer-valued on this extreme point as described in Appendix [ In this case, the optimal solution induce abrupt change in the objective value. Thus, the (Z)(C) be in the form of the piecewise constant, making difficult ac to estimate the gradient. To solve this issue, Vlastelica et al. (2019) presented piecewise linear surrogate loss surface that can approximate the original piecewise constant surface 30 binatorial optimization layer. To obtain meaningful differential value for this integer-solution, the 27 87 az" az"(C)
may not vary continuously with respect the input; small change
0. of the com-
3C approximated by using the solution gap between the original solution of the optimization problem and the solution of the perturbed optimization problem, as:
gradient .C 32
0J
~
-2 2
(19)
ac
12

---

Under review as a conference paper at ICLR 2023
where Z and C' are the optimal solution and coefficient used in the forward pass, respectively. the approximate solution computed as:
Z3
= - (CK).
(20)
Here, C is the perturbed cost coefficient computed as
C= dJ dz (2*)
(21)
where À is the hyperparemeter that scales the amount of perturbation while considering the gradient
with respect to the solution Z 22 (Z*) is the gradient of J with respect to solver output Z given point Z* The amount of solution gap between the original solution and perturbed solution Z Z
is the slope of the piecewise linear function that will replace 05 evaluated at C. One can guarantee
ac
that the modified loss function piecewise affine and similar the original loss function (we refer as 02 a2*
to Vlastelica et al. 2019 for more detail). In the backward pass, Eq. replaaees
a2"(C) (C) in Eq. ac
14
C HYPERAPAREMETERS AND EXPERIMENTAL DETAILS
The hyperparameters of LPMARL used in the experiment are summarized in Table 5 We used an CVXPY solver (Diamond & Boyd 2016) to solve the linear programming in Section
Table 5: Hyperparemeters of LPMARL
Hyperparemter
Values
MLP units for GNN, [[; (1:00) I(; (,MMM, [(:07)
[32,32]
MLP units for coefficient matrix, (()
[64,64]
MLP units for policy network, f(:;0,,, f(;
[64,64]
MLP units for critic network f(: f(:
[64,64]
Nonlinear activation
LeakyReLU, negative slope=0.01
learning rate
10-3
Discount rate,
0.99
40
Optimizer
Adam
For other baselines algorithms, we used a two-layer feed-forward fully-connected network with a 64-dimensional hidden layer and ReLU activation. Batches of 32 episodes sampled from the replay buffer. The optimizer, learning rate, and discounting rate ? of the other algorithms are set to be the same in Table Experiments carried out NVIDIA RTX A6000 GPU.
C.1 COOPERATIVE NAVIGATION
We used 50,000 episodes where the maximum timestep of the each episode is 50. For every algo- rithm, we the size of the replay buffer as 5,000 with batch size of 100 train. For LPMARL, we set h;, the capacity constraint coefficient of Eq. 5 as 1 at every scenario. The initial location of the agents and landmarks are randomly spawn on 1, x [-1, 1, and [-0.8, 0.8] [-0.8, 0.8). respectively. The reward conditions of the experiment is specified in Table 6
C.2 CONSTRAINED COOPERATIVE NAVIGATION
We used 50,000 episodes where the maximum timestep the each episode is 50. For LPMARL, set k; the capacity constraint coefficient of Eq. 5 be the same as the landmark capacity. The initial location of the agents and landmarks are randomly spawn on |-1, 1]x [-1, and 000.,0.8) --08, 0.8), respectively.
13

---

Under review as a conference paper at ICLR 2023
Roward setting
Hierarchical MARL, LPMARL
Non-hierarchical MARL
High-level reward
when all reaches landmark
High reward
setting
-0.5 Loww-leve reward
agent reaches landmark
Low level reward
distance and collision-relant reward
High ligh-llevel reward
when all reaches landmark
ligh level reward +0.5 Low-level reward
Sparse setting
Low-level roward
agent reaches landmark
Table 6: Reward setup of cooperative navigation environment.
We set the capacity of the landmarks as an integer partition of N into M groups, i... ΣØ= k2 = N where ky is the number of agents that can be accommodated by landmark j. The capacity of the landmark randomly determined the beginning of each episode. Agents can observe the capacity and the position of each landmark within the observation range.
C.3 STARCRAFT MULTI-AGENT CHALLENGE
We train all models over 100,000 episodes. For every algorithm, we set the size of the replay buffer 5,000 with batch size of 100 train. For LPMARL, set k; the capacity constraint coefficient at every scenario.
of Eq. 5 as [
We consider the following SMAC scenarios:
3m: marines (N 3) versus 3 marines (M 3). The episode limit is 60 timesteps.
2m Iz: 2 marines (N 2) versus zealot (M 1). The episode limit is 150 timesteps.
3s_5z: stalker (N 3) versus 5 zealots (M 5). The episode limit is 150 timesteps.
8m: marines (N 8) versus 8 marines (M 8). The episode limit is 150 timesteps.
Difficulty levels of the scenarios are all set to be harder (6).
D ADDITIONAL EXPERIMENT RESULTS
D.1 COOPERATIVE NAVIGATION
D.1.1 TRAINING CURVE
Training curve constrained cooperative navigation is shown in Figure 5 Figure 5 shows the high- and low-level reward curve over the episodes when the algorithm is trained when N and M
Inaleaal reweee
1.0
CacuINANL
1005
Tewstrr 2371
Figure 5: Low-level (left) and high-level (right) reward curve. The reported reward is the mean over all the agents over the timestep per episode.
D.1.2 EFFECTIVENESS OF LP LAYER
We consider the following ablations of high-level policy to examine the effectiveness using LP as high-level policy. I.P-distance assigns agent goal using the distance matrix as the objective
14

---

Under review as a conference paper at ICLR 2023
Cooperative Navigation
Constarined Cooperative Nevigation
540C 1850
0.6
0.6
0.4
LPWARL
0.4
DeC-L
No-LP
Thaining timestep (cle5)
timestep (cle5)
Figure 6: Training curve of ablations of high-level policy on cooperative navigation (left) and con- strained cooperative navigation (right)
coefficient of LP. Therefore, agents are assigned to landmarks that minimize the sum of the distance of all the agents. Greedy is a greedy assignment, where each agent chooses the closest landmark individually. The network structure for low-level policies is identical for all the high-level ablations.
Figure shows the results of ablation studies. LP-distance uses hand-designed features induce good coordination for tasks where proximity plays essential roles, such as cooperative navigation. However, devising hand-defined rule for complex task is challenging. In such cases, the proposed algorithm that constructs the cost matrix considering the global state can play an important role in deriving an effective policy. By comparing LPMARL and No-LP, we can see that the LP layer plays vital role in allocating agents to tasks to increase the success rate.
D.1.3 EFFECT OF SPARSE REWARD HELP FOR TRAINING NON- HIEHHRCRRRACCAL MARL
In cooperative navigation, although non-hierarchical MARL can be trained only with dense reward (distance and collision-related reward), we use weighted sum of the high-level (sparse) and low- level reward to compare the performance fairly. only dense reward used for non-hierarchical MARL, their performance degrades. Table compaaes the success ratio of using only dense reward for non-hierarchical MARL algorithms on cooperative navigation environment.
Qaix
MADDPG
MAAC
T+B
T+B
E
T+E
E
Dense-3
82.4
87.0
85.7
82.1
89.1
85.5
D
74.5
Dense-7 7
49.1
43.0
5.7
12.2
65.7
52.0
Table 7: Success ratio when cooperative MARL algorithms are only trained with environment
ward. (T+E) indicates task-dependent reward + environmental reward, and (E) indicates environ- mental reward.
D.2 SMAC ENVIRONMENT
Figure visualizes the high-level assignment of LPMARL on 8m environment. We divided the enemy units into two groups, with three and five units, to clearly see how LPMARI. allocates agents to enemies. Each sub-figure of Figure 7 shows the high-level assignment result on timestep when the event (when or N changes) occurs. The agent-task with the same color represents the result of the high-level assignment.
In the figure, we can observe that the LPMARL agent sequentially kills all the enemies by focusing fire from the nearest enemy (task). Also, LPMARL does not always assign only the closest enemy to the ally but assigns agents to the enemy with the lowest health level (N M = 4). Further visualization videos can be found the following link
15

---

Under review as a conference paper at ICLR 2023
N-8, M-8
N-7 M-7
N-7,M-6
N-5, M-5
N-5, M-4
N-4, M-4
N-4, M-3
N-4, M-2
N-3,
N-2, M-2
N-2 M-1
Figure 7: Visualization of high-level assignment on StarCraft environment (8m).
E
CODES
The code repository will be available after the decision.
16


Reviews:
[{"review_id": "OdZZZ8zdfI", "reviewer": "Reviewer_VRWi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces the LPMARL framework to address the sparse reward challenge in MARL. Specifically, LPMARL consists of two hierarchical decision-making parts: 1) the high-level part solves the agent-task assignment as the LP problem, and 2) the low-level part solves local games among agents with the same task. To enable decentralized execution, the paper also develops Dec-LPMARL by amortizing the task allocation of LPMARL. Empirical evaluations in cooperative navigation and SMAC domains show the effectiveness of the proposed approach. ", "summary_of_the_review": "I would like to initially vote for 5 due to the concerns above. After the authors' response to my concerns and questions, I will make a final decision on the recommendation.", "strength_and_weaknesses": "**Strengths:** \n1. Formulating the high-level agent-task allocation problem as LP is novel. \n2. The interpretability and transferability are beneficial properties of LPMARL. \n\n**Weaknesses and Concerns:**\n1. My biggest concern is possible unfair comparisons against baselines. In particular, LPMARL is centralized training & centralized execution approach, and the baselines are centralized training & decentralized execution approach. Therefore, comparing Dec-LPMARL (centralized training & decentralized execution) against the baselines for fairness, it is unclear whether Dec-LPMARL is a clear winner (e.g., HSD performs better than Dec-LPMARL in Table 1). \n2. The clarity of the paper generally needs improvement. For example, this paper uses (hierarchical) Dec-POMDP as the base framework, so each agent receives observation $o_{i,t}$ not the state $s_t$. However, LPMARL uses the state information (see Figure 1, where the input is the state) to construct the agent-task score, and it is unclear how the state can be constructed based on observations. Similarly, the paper uses $s_i$, but it should be $o_{i}$. Lastly, Equation 8 uses the state to decide the low-level action, but it should be $o_i$. \n3. Regarding the non-hierarchical MARL baselines, it is unclear why the weighted sum of the high- and low-level rewards is used to train them. Wouldn't it be fairer to train them with the environment rewards only?\n\n**Minor:**  \n1. In Figure 1, instead of \"ag\", \"agent\" can improve readability. \n2. Typo: \"Dec-LPMLARL\" to \"Dec-LPMARL\"\n3. Could you clarify what high-level action space is in the cooperative navigation domain? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GgKRh1R9SZ", "reviewer": "Reviewer_fFLH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "multi-agent RL problem can be generally solved in 3 stages: 1) given the current state, a centralized planning problem is formulated, the problem is about which agent should do what (on a high level). 2) the planning problem is solved, allocating each agent with their respective high-level goal. 3) the agents individually carry out the high level goal using low-level controls.\n\nthis paper takes these 3 stages, and 1) make them end-to-end and 2) make it decentralized. the result is a model architecture and a training method with an inductive bias towards planning. the authors demonstrate that when agents are trained this way they often do better than the baselines.", "summary_of_the_review": "overall, the paper is technically sound (as far as I could tell), and the quantitative results are comparable with baseline algorithms.\n\nhowever, the qualitative claim on interpretation is bit of a stretch, as their notion of interpretability is essentially \"the authors themselves looked at the resulting multi-agent strategy, and decided that 'yep, it made sense'\". A 3rd party judgement would be good, extending the analysis on interpretability to starcraft would be good.", "strength_and_weaknesses": "strength : the technique is sound on a cursory glance (of the math), and the evaluation is thorough, showing (for the most part) good performance when compared with baseline algorithms.\n\nweakness: I think the aspects of interpretability and transferability should be further explored. here's some comments:\n\n1) on interpretability, the author only looked at a simple navigation environment where the interpretation is rather intuitive (or \"obvious\") -- distance is useful. I would like to see if a similar kind of intuition can be seen in the starcraft environment. The interpretability aspect is also not vetted against 3rd party users (i.e. crowd-workers) but rather the authors themselves, which lowers the validity of the \"interpretability\" claim. One could imagine a small survey on a crowd-worker setting where behaviours of several different algorithms were demonstrated, and the workers asked to describe them. Then, one can measure whether the descriptions agree with each-other as a proxy for interpretability. also, what about a video? I used to play a lot of starcraft and I'm actually in a good position to judge if the agents are behaving in a predictable way if only I can see a few videos, but all I get is success ratio, which hides away a lot of the details (did they succeed without taking any damage? did they do it fast or really dragged it out? did they focus fire? did they pull back the unit that was hurt? did they reposition themselves to a favorable flank before engaging? did protoss learn to abuse the fact that shields regenerate while HP do not?) these are the kind of \"interpretation\" that I would like to see. \n\nDoes the LP problem, invented by the neural network from end-to-end training, reflect these interpretable strategies? You can imagine an intervention, where the end-user is allowed to control these LP problems with some instrumentation, which should result in behavioural changes to the agents. This is similar in spirit to giving the user a slide-bar on some latent disentagled vector representation and have them slide it over. Can a similar experiment be constructed?\n\n2) on transferability. what about 20m_vs_20m? what about 12 stalkers vs 24 zealots? there's actually quite a bit of combinatorial space of match ups, and presumeably fairly easy to set-up and run. You might discover the agents need to adopt different strategies after a certain \"critical points\" -- for instance, 2 stalkers can probably brute-force kill 2 zealots, but against 4 you really need to kite.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "85YYjMhCb11", "reviewer": "Reviewer_LMn4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This introduces a hierarchical framework for multi-agent reinforcement learning. It formulates agent-task assignments as a linear programming problem. With the solution of LP, it generates a low-level policy to solve each sub-task in a cooperative manner. Some empirical experiments are performed to demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "This paper is a resubmission of their work from last year.  Compared with last year's submission, the contribution and novelty are marginal.", "strength_and_weaknesses": "Strength\n\n• The idea of leveraging techniques for differentiation of black box combinatorial solvers for MARL is unique and interesting.\n\n• Experiments are extensive. Fig.1 and Fig.3 are the good visualizing explanation.\n\nWeakness\nmain comments:\n• what is the advantage of using a differentiable LP layer (GNN and a LP solver) as a high-level policy, shown in Eq. 10?\n\n– compare it to [1] that considers the LP optimization layer as a meta-environment?\n\n– compare it to an explicit task assignment protocol (e.g. not implicit).\n\nE.g. a high-level policy that directly outputs task weightings instead of the intermediary C matrix?\n\n• How does this method address sparse reward problems in a better way? From the experiments, this does not support well. in practice, the proposed method requires sub-task-specific rewards to be specified, which would be similar to providing a dense reward signal that includes rewards for reaching sub-goals. If given the sum of low-level reward as the global reward, will the other methods (Qmix) solve the sparse-reward tasks as well?\n\nminor comments:\n• It is hard to determine whether the solution to the matching problem (learned agent-task score matrix C) optimized by LP is achieving global perspective over the learning process.\n\n• When the lower-level policies are also trained online, the learning could be unstable. Details on how to solve the instability in hierarchical learning are missing.\n\n• What is the effect of the use of hand-defined tasks on performance? what is the effect of the algorithm itself? maybe do an ablation\nstudy.\n\n• Section 5.2 ”training low-level actor-critic” should be put in the main text.\n\n[1] Carion N, Usunier N, Synnaeve G, et al. A structured prediction approach for generalization in cooperative multi-agent reinforcement learning[J]. Advances in neural information processing systems, 2019, 32: 8130-8140.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2ivGkWelsKS", "reviewer": "Reviewer_vJe1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers training a multi-agent reinforcement learning (MARL) model with sparse reward. It proposes a linear programming-based hierarchical MARL for the considered problem. It claims that the proposed approach learns an optimal agent-task allocation and also a local cooperative policy for agents in sub-groups. ", "summary_of_the_review": "The motivation of this paper is not clear to me. The problem definition, challenge, and background needs to be discussed in more detail. The proposed LP-based approach is novel and the paper provides a complete end-to-end training diagram for the proposed approach. However, it lacks theoretical justification of why it works as desired.", "strength_and_weaknesses": "Strength: \n1. The proposed LP-based approach for agent-task allocation is novel to me. The paper discusses how the LP formulation can be generated using GNN and how to train it in an end-to-end manner with implicit function theorem. \n2. The mathematical formulation in this paper is clearly written.\n\nWeakness:\n1. The motivation of this work is not clear to me. The problem definition, challenges, and background are not discussed in a clear manner.\n2. It does not contain theoretical justification of why the proposed approach works as desired.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject