Non-Linear Coordination Graphs
Authors: Yipeng Kang
Tonghan Wang
Qianlan Yang
Xiaoran Wu
Chongjie Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Coordination graphs
Non-linear
Multi-agent reinforcement learning

Abstract: Value decomposition multi-agent reinforcement learning methods learn the global value function as a mixing of each agent's individual utility functions. Coordination graphs (CGs) represent a higher-order decomposition by incorporating pairwise payoff functions and thus is supposed to have a more powerful representational capacity. However, CGs decompose the global value function linearly over local value functions, severely limiting the complexity of the value function class that can be represented. In this paper, we propose the first non-linear coordination graph by extending CG value decomposition beyond the linear case. One major challenge is to conduct greedy action selections in this new function class to which commonly adopted DCOP algorithms are no longer applicable. We study how to solve this problem when mixing networks with LeakyReLU activation are used. An enumeration method with a global optimality guarantee is proposed and motivates an efficient iterative optimization method with a local optimality guarantee. We find that our method can achieve superior performance on challenging multi-agent coordination tasks like MACO.

Non-Linear Coordination Graphs
Yipeng Kang" Tsinghua University fr tringsoo@gmail.com
Tonghan Wang" Harvard University twang 0g harvard.edh
Qianlan Yang" UIUC gianlan2@11limois..em
Xiaoran Wu Tsinghua University
Chongjie Zhang Tsinghua University chongj iennggie@ttsnghuu... edugghuaaeeu.....
wux:17@tsinghua.c org.
Abstract
Value decomposition multi-agent reinforcement learning methods learn the global value function as a mixing of each agent's individual utility functions. Coordination graphs (CGs) represent a higher-order decomposition by incorporating pairwise payoff functions and thus is supposed to have a more powerful representational capacity. However, CGs decompose the global value function linearly over local value functions, severely limiting the complexity of the value function class that can be represented. In this paper, we propose the first non- non-linear coordination graph by extending CG value decomposition beyond the linear case. One major challenge is to conduct greedy action selections in this new function class to which commonly adopted DCOP algorithms are longer applicable. We study how to solve this problem when mixing networks with LeakyRel.U activation are used. An enumeration method with global optimality guarantee is proposed and motivates an efficient iterative optimization method with local optimality guarantee. We find that our method can achieve superior performance on challenging multi-agent coordination tasks like MACO.
Introduction
Cooperative multi-agent problems are ubiquitous in real-world applications, such as crewless aerial vehicles 20 35
and sensor networks (38). However, learning control policies for such systems remains a major challenge. Recently, value decomposition methods 226 significantly push forward the progress of multi-agent reinforcement learning [2 24
29 30 In these methods. a centralized action-value function is learned as a mixing of individual utility functions. The mixing function can be conditioned on global states [22] while individual utility functions are based local action- observation history. The advantage is that agents can utilize global information and avoid learning non-stationarity 27 via centralized training, while maintaining scalable decentralized execution.
28
Notably, the major focus of the value function decomposition research was on full decomposi- tion. where local utility functions based actions and observations of single agent. Full decomposition leads to several drawbacks, such as miscoordination problems in partially observable environments with stochastic transition functions 28 32 and game-theoretical pathology called
relative overgeneralization [18 4] Relative overgeneralization embodies that, due to the concurrent learning and exploration of other agents, the employed utility function may not be able express optimal decentralized policies and prefer suboptimal actions that give higher returns on average.
These authors contributed equally to this work.
Code is available at httppp///gg.aaiiccc////o/o/////p
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

VDN
QMIX
DCG
Ours
2
2
1
4
3
Σ
Qut
qi
each timestep. Qtot = fm (41, ,9n)
Qio
qu
Ocor fm (19(3)
1,1
Fully decomposed value functions
Coordination graphs
Figure 1: Different value decomposition methods. VDN 26 and QMIX [2] represent the global
Q-function as linear and monotonic combination of individual utility functions. Conventional coordination graphs (CGs) 4 learn linear decomposition pairwise payoff functions. Our work extends CGs by introducing non-linear combination of payoff functions.
Coordination graph (CG) learning 99] holds the promise to address these problems while preserving the advantages value decomposition methods. In a CG, each vertex represents an agent, and each (hyper-) edge stands for payoff function that is defined on the joint action-obserration space of the connected agents. The existence of payoff functions increases the granularity of decomposition, and connected agents explicitly coordinate with each other. As a result, a CG represents higher-order factorization of the global value function and represents a much larger value function class.
However, coordination graphs typically assume a linear decomposition of the value function among sub-groups of agents, which too simple to represent credit assignment complex tasks. this paper, we solve this long-standing problem and extend CG by introducing non-linear and learnable value decomposition. our best knowledge,
the first study on non-linear coordination graphs.
The major challenge against extending CGs beyond linear cases is the calculation of malue-maximizing actions. When linearly decomposed, DCOP algorithms [6] can find a globally greedy action message passing. However, when the mixing function is non-linear, DCOP algorithms are no longer applicable. To address this problem, we develop DCOP method for non- non-linear mixing functions represented as deep network with LeakyReLU (or ReLU) activation.
The core idea of are equivalent to piece-wise linear functions. For each linear piece, a value-maximizing action can be found by classic DCOP. However, this action may fall out of the domain of the linear piece and thus infeasible. We first prove that such a shifted action indicates a better solution in its domain. Based on this conclusion, we first show how find feasible joint action with the global optimal value, and then derive an iterative algorithm with local optimum convergence guarantee.
non-linear DCOP algorithm is to exploit the fact that these neural networks
We demonstrate the improved representational capacity of our Non-Linens Coordination Graphs (NL-CG) on a matrix game by comparing the learned Q functions to those learned by conventional coordination graphs. We then evaluate Benchmark [33) for its high requirements on close inter- agent coordination. The experimental results show the superior performance enabled by the non-linear value decomposition.
method on the Multi-Agent COordination (MACO)
Preliminaries
In this paper, we focus on fully cooperative multi-agent tasks that can be modelled as Dec- POMDP [17] consisting of tuple G= S. A, P. R. Ω, O, 7).
where is the finite set of n agents, y [0,1 1) is the discount factor, and s E S is the true state of the environment. each agent receives an observation
E Ω drawn according to the observation function (s. and selects an action a; E A. Individual actions form joint action a A", which leads to next state s' aacorrdin to the transition function P(s [s, a). reward r = R(s, a) shared by all agents. Each agent has local action-obserrattin history πi E = (Ω x A)" Q. Agents learn to collectively maximize the global return Qtoc(s,
E Exg... .0.000 Σ 2. 7 R(s e, a, ss0 = s, ag a).

---

Estimating Que is at the core of multi agent reinforcement learning (MARL) 26 24 14 34 [2]. The
complexity of calculating max Qut grows exponentially (IAl") with the number of agents 31) To solve this problem, value-based MARL decomposes the global action-value function into local utility functions qi and guarantees that the global maximizer can be obtained locally: arg max, Q (8, a) =
(arg max,, 91 (TT, a1)..... ..... arg max,, 4n (T=: an)) 'I' Value decomposition network (VDN) 126 satisfies this condition by learning the global value function as a summation of local utilities (Fig.)
left). QMIX [22] extends the function class of VDN by learning Qiot monotonic mixing of local
utilities. The mixing function is parameterized so that: (Qter(s.a)
(Ti(aa)))) 2 O.
2.1
Coordination Graphs
For fully decomposed value functions, local utility functions are conditioned on local action- observation history. Coordination Graphs (CGs) [9] increase the representational capacity of fully decomposed value functions by introducing higher-order payoff functions. Specifically, a coordi- nation graph is tuple of a vertex set and an edge set: g (V.E). Each vertex v E V represents an agent i, and (hyper-) edges in & represent coordination dependencies among agents. In previous work, the global value functions are decomposed linearly based the graph topology:
1 Qiot T, a)
[V] Σ (T. +
Σ (WJ)EE
9: (Ty a.z)),
(I)
E
where 4, and 4y is utility functions for individual agents and pairwise payoff functions, respectively.
Tay (T,, Ty) and a. (a,, .y) is the joint cetion-observation history and action of agent i and j.
Previous work studies different aspects of such coordination graphs. It is shown that higher-order factorization is important on tackling an exponential number of joint actions [5]. Sparse cooperative Q-learning 11 learns value functions for sparse coordination graphs with pre-defined and static topology. Zhang al. (38) propose learn minimized dynamic coordination sets for each agent. DCG [4] incorporates deep function approximation and parameter sharing into coordination graphs and scales to large state-action spaces. CASEC (33) and SOP-CG (36) studies how to build sparse deep coordination graphs that are adaptive to the dynamic coordination requirements. In all these works, the global value function is represented as summation of local value functions. To the best of our knowledge, this paper presents the fist CG learning method with non-linear value decomposition.
2.2 Message Passing
Within coordination graph, the greedy action selection required by Q-learning can not be completed by simply computing the maximum of individual utility and payoff functions. Instead, distributed constraint optimization (DCOP)
6 techniques are used. Max-Sum (55 is a popular implementation of DCOP. Max-Sum finds near-optimal actions on a CG G = (V,E) via multi-round message passing on bipartite graph Gm (Va. Vg. Em). Each node E Va represents an agent, and each node g E Vy represents a utility (q:) or payoff (g:)) function. Edges in &m connect g with the associated agent node(s). Message passing starts with sending messages from node i Va to node g E Vg:
mi-a (a:)
Σ mi-ii (a:) Cigs BEF
where F; is the of nodes in V/ connected to node i, and Cig is normalizing factor preventing the value of messages from growing arbitrarily large. Messages are then sent from node g to node i:
mg-+i (a:)
max (a,)) ag (04
Σ NEV,
ma-1 (ax)),
where Vo is the set of nodes in V4, connected to node g. ag fax h E Vg), ag aa fan h E V& Mi)). and q represents utility or payoff functions conditioned on ag. Eq. 2 and 3 make up an iter- ation of message passing. Each agent can find its local optimal action by calculating of = argmax,, a. Σ ma-si (a:) after several iterations of message passing. Notably, Max-Sum and other DCOP algorithms are only applicable to linearly decomposed value functions.
3

---

2.3 Piece-Wise Linear Neural Networks
Following the recent decade's success of deep neural networks (DNNs), analysis works have been done trying to explain the mechanism of the DNN black-boxes and assess their function approximation capabilities. One conclusion that a DNN with piece-wise linear (PWL) activation functions (e.g. ReI.U, LeakyReL.U, PReL.U) is equívalent to PWL. function. This kind of DNNs are called piece- wise linear neural networks (PLNNs) 7 Early papers 16 19 assess the expressivity of PINNS by the amount of linear pieces.
10] give more theoretically grounded results about the upper and lower bounds for the amount of pieces. In this sense, it is shown that increasing the depth of network can generally be exponentially more valuable than increasing the width 19 g 2 Chu et al. (7] propose OPENBOX to compute the mathematically equivalent set of linear pieces, which provides accurate and consistent interpretation of PLNNs. For neural networks with single layer of hidden nodes, the problem can be reduced to hyper-plane arrangement [7,, and linear functions and their domain can be enumerated efficiently [21
2
23
3 Method
Our method extends the representational capability of coordination graphs by introducing non-linear factorization of the global value function. Specifically, for a coordination graph G = (V,E) (we study complete coordination graphs in this paper). we decompose the global Q as:
(4) where qi is the vector of all individual utilities, and qıj is the vector of all pairwise payoffs for edges in &. Similar to DCG [4], we learn a shared utility function f", parameterized by 8", and get the individual utility g a:) = f (" [T: 0²). The payoffss are estimated by shared function f parameterized by 8% (Ty Tj, ai, ag) = f" ay/Ta, 8):
Qroe(s, a) = fn (q., 9:s)
Different from conventional CGs (Eq. D. our fn is non-linear mixing network whose parameters are generated by a hypernet f conditioned on the global state s and parameterized by th_ Our discussion is based on LeakyReLU networks with the slope coefficient a E [0, 1]. For efficiently calculating the maximizer of Qtot, we require the weights after the first layer of the mixing network to be non-negative. The reason for this non-negativity constraint will be discussed in Lemma T Such a mixing network is effectively type of input convex neural networks (ICNN (l). The
and 2 non-negativity constraint on parameters is somewhat constraint, but we can use the passthrough trick introduced in Proposition 1 of ( to maintain substantial representation power of the mixing network.
The whole framework, including the utility function f", the payoff function f", and the hypernet fd, is updated by minimizing the TD loss:
(TD( 00, 8h) = B(san)))) (Qtee a) - (r + max (so a )²)))²]
(5)
a'
where D is the replay buffer, and Qtoe is a target function whose parameters are periodically copied from the function Qtot-
The main challenge left, for both the training and execution phase of deep Q-learning, is to select actions that maximize the global Q value at each time step, arg max, (T, a). An exact solution to this problem is intractable. Though the mixing network is convex, optimizing its output is still very hard since the inputs are correlated variables, whose simple summation is already hard one to optimize. In the following sections, we first provide global optimal algorithm for this problem. The complexity of this algorithm grows polynomially with the number of hidden units in the mixing network. To reduce time complexity, we propose an iterative algorithm with local optimum convergence guarantee.
We use the following notations. The input to the mixing network is q= qqi [qg]] where [-]]-] means vector concatenation. We use q(a) to denote the utilities and payoffss corresponding to action a. The mixing network has L LeakyReLU linear layers. d = |V| + |E| is the input dimension. m,, W, and b, R. are the width, weights, and biases of the ith layer. The weights after the first layer are non-negative. The input to the activation units at ith layer is 2;, and the corresponding output is h, LeakyReLU(z:) = G; Oü, where e; is the value of LeakyReLU activation (c = a when z < 0 and = 1 when 2 0) and is the element- wise multiplication. We call e e= [nll...//c.. E (ax 1)m,, m = E, m,, a slope configuration of the mixing network. Subscripts of W., b, 2i, and h, means index. For example, Ziz is the jth element of 2,, and Way is the jth row of W.
4

---

3.1 Piece-Wiss Optimization
The general idea of our action selection algorithm is utilize the piece-wise linear property of the LeakyReLU network. Given a slope configuration c, the mixing network becomes linear, and we can run a DCOP algorithm to get the corresponding maximizer of Qrot. The question is that the obtained solution may be out of the domain of the linear piece. We show that, when the weights after the first layer are non-negative, we can ignore whether the obtained local optimal solution is in the piece's domain, and the global maximizer of Qto is the best of the local optima.
Formally, there are 2 slope configurations in Caul {clc E {a, 1)"", each of which makes the mixing network an aftine function in Pan (PI. P2m J. Each affine function Px has a corresponding cell Pk where q E Pk yields c* in the forward pass. For each ch E Call. by running DCOP, we obtain the local maximum qs and the corresponding joint action ag and utilitiesspayooffs qs- However, it is possible that qs falls out of Ps and indeed yields another slope configuration c** We first show that such shifted solution indicates
equal or better solution in its domain.
Lemma 1. Denote affine function pieces and their cells of a fully-comnected feedforward mixing f
network with LeakyReLU activation as Pail {ps " and (P, " For q in the cell of the rth piece, Py. and up, E Patt we have (q) 2 Pg(g).
Proof. We start with the first difference between cº and c². We denote it as Gi cj.. Because this the first difference, the input to this unit, 21j, is the same. Since q is in Pr, we have that di is 1 when 2ij is positive and is < 1 when 2ij is negative. Therefore, the output satisfies that
N3 =c 2 22 -hg.
(6)
follows that
+ W W h + b 2 WT. 1+1 h + bi+1 2
(7)
because W 2 0. Other differences the ith layer will lead the same conclusion. At layer i 1, we have
h = ch 2 2 c o 2 2 c/41 o x h
(8)
The first inequity is because q is the cell of pr- The second inequity is because of Eq, 7ndd that LeakyReLU is a monotonic increasing function. The proof can repeat for the following layers and thus holds for the last layer, i.e., (q) 2 (q)))
Based on Lemma D when the local optimal solution, ag. of piece k returned by DCOP actually falls in cell Pryk- we have pr- (r-(((ax)) 2 PI. (a.)).))). This indicates that, on piece r, we will get a solution at least good as the on piece k. Based on this conclusion, we now prove that the maximum of each piece's ' local optimum is the global optimum.
Lemma 2. Running DCOP algorithm for each linear piece in Pats then take the maximum value among these pieces, we can get the global optimizer of Qiot.
Proof. We have that maxq (a) = max, max Pp(g) ma maxg (p(g) (Jn is the mixing function, Eq. 4). which means the maximum of local optimal values the global optimal value. Suppose the global optimal value Qmax is found piece and the corresponding action is a,, the question is whether q(a,)) is feasible, i.e., ((a)) E P.. Assume that q ((a,)) falls in P Pagy- Then for piece s, a, is feasible solution with the value Qmaz (due to Lemma TT. This means the global optimal solution is always a feasible solution.
According to Lemma and then take the best of these results to get the global optimum. Detailed process can be found in Algorithm !
run message passing on each piece (Algorithm ?? in Appx. ??)
The problem of Algorithm I is time complexity. When m is small, we enumerate all 2 slope configurations. For a large m, we can use the hyperplane arrangement algorithm 7 to calculate exact linear pieces and their domains. Specifically, there are
d
Σ 1=
m
(9)
ddii)
d
pieces need enumerating, where is the input length. This number exponential to d. To reduce time complexity, we propose an iterative optimization method in the next section.
5

---

3.2 Iterative Optimization with Local Optimum Guarantee
When m large, enumerating either 2Th or Am. pieces can be costly. We thus propose an iterative algorithm with local optimum guarantee (Algorithm 2 to get approximate solutions. We begin with the slope configuration where all hidden units are activated (c = {1)m"). We run message passing on the current configuration Gp and get local optimum solution ap. If the real configuration Creat of ap is not Cp. we calculate the local optimum of Creat- The iteration continues until Creal = Cp-
Lemma D guarantees that the solution values in the iteration are monotonically increasing. Since there is finite number of configurations, our algorithm can converge to local optimum.
With a very low probability, loop would appear the iteration. The appearance of a loop means that the equity in Lemma holds. In this case, the solutions on the loop have the same value, thus can stop our iteration when encountering a slope configuration that has been searched.
Algorithm EENUERAATE-PPPIMIAAAAA
Algorithm 2 ITERATIVE ITERATIVE-OPTMMIZZZII OPTIMIZATION
Show the case for a two-layer mixing network, but can be easily extended to more layers.*/ */
/ Show the case for a two-layer mixing network, but can be easily extended to more layers.** */
Input: f E ERIVIA f E RRLEIXXXA Wo.
Input: fv RIIIXA, f E IXIXA Wo.
bo. W1. bj
bo. W1, Amazs
Jmax := -0;; mmax := [
9max -00, a 11 Cp = (1)m
Iniitialize the best found solution.*/
for E {l,..., Amaas do
for Cp {a, 1 do
Try one configuration at a time.*/
|*Calculate the equivalent weights and bi-
W = Wo (Cp o W1)
ases. */
bp (c,oW)
W1) b% +11
W Pr == -Wo (cp W1)
q. a
Ppp = =ccp W1) bg + bl
w- C--MAX-SUMÇ f W bp.)
q: a.
if > lmax then
W- ----AX--UUMM f W bp.)
0max
if q > Omax then
Imax f
Qmax
Greal The real LeakyReLU slope con-
9max f /RRemmbeer only the best actions.* */
figuration
end if
end if
if Creat # Cp then Cp +- Creat else with prob. break or continue with an unvisited Cp-
end for
return Gmux
end for return Omax
("Return the selected joint action amax */
To increase the possibility of finding a global optimum, we can introduce a simulated annealing mechanism. Each time we find better solution, with probability of c, we move to the corresponding piece, and with a probability of c, we jump to a random piece that has not been searched. decreases with the iteration number.
Discussion about loopy graph topology In this paper, we consider complete graphs when studying non-linear coordination graphs. A concern is that message passing algorithms like Max-Sum may not converge to the optimal solutions in loopy graphs and has an error rate of e. Lemma [ is not affected because it is property of LeakyReLU Networks. For Lemma 2 the maximum of solutions found by message passing in all slope configurations is the global optimum with a probability of 1 c. An error occurs when message passing cannot find the right solution the piece where the global optimum is located. Our iterative method may stop earlier when message passing returns a wrong solution located in the current cell. The probability of this situation is less than e. Thus have at least probability of (1 - e)" (n is the number of iterations) to find the piece where the local optimum is located, and the final probability of finding the local optimum is larger than (1 e)n+11
4 Representational Capability
In this section, we compare the representational capacity of our model against conventional coordina- tion graphs. The comparison is carried out on two-step cooperative matrix game with four players and two actions. At the first step. Agent I's action decides which of the two matrix games (Table.

---

to play in the next timestep. In the second step, the number of agents taking Action B determines the global reward received by the agent team (Table.
State 2A
State 2B
# Action B Reward 7 7
0
2
4
# Action Reward
2
7
7
0 -0.1
0.1
0.3
Table 1: Payoff matrices of the two-step game after Agent chooses the first action. Action A takes
the agents to State 2A, while action B takes them to State 2B. The team reward depends on the number of agents taking Action B.
We first theoretically prove that the representational capacity of conventional coordination graphs is unable represent the Q-function of this game. Since the reward is invariant to the identity of agents, i.e., R(a1, d2, 43, 04) Rip(a1, 02 03. 04)), where p is an arbitrary permutation, the learned action-value function should also be permutation invariant. Therefore actions in value functions. Now let's focus on State 2B (#28). Conventional coordination graphs need solve a linear system consisting of five unknowns and five equations. However, for this system, the rank of the augmented matrix (4) is greater than the rank of the coefficient matrix (3). Details can be
can ignore the order of
found in Appx. ??. Therefore, this system has no solution, and it is impossible for conventional CGs to learn a correct Q function.
We then empirically demonstrate our idea. We train NL-CG and DCG the task for 5000 episodes under full exploration (c = 1) and examine the learned value functions. Full exploration ensures that both methods explore all state-action pairs. In such case, the representational capacity of the action-value function approximator remains the only challenge of learning accurate Q functions. For algorithm, the utility and payoff function is fully connected networks with single hidden layer of 64 units with ReLU non-linearity. is 0,99, and the replay buffer stores the last 500 episodes, from which we uniformly sample batches of size 32 for training. The target network is updated every 100 episodes. The learning rate of RMSprop is set to 5 x 10-4. Agents receive the full state as observation, which is represented as an one-hot vector.
Table 2 and 3 show the learned Q by DCG and NL-CG. In line with our theoretical analysis, we can see that DCG learns sub-optimal strategy of selecting Action A in the first step. By contrast. our method learns the accurate value of Action B in State A and get the optimal strategy. Furthermore, the values for State 2B learned by NL-CG is more accurate than those learned by DCG. These results demonstrate that NL-CG's higher representational capacity allows it to accurately estimate the value function of this game whereas DCG cannot. We also note that such an example is common for task with few actions because there are typically more equations than unknowns.
State A
State 2B
Action
A
B
# Action B
0
2
3
4
6.91
5,85
1.32
-0.89
-0.77
1.41
5.89
Table 2: Q-functions learned by DCG for the matrix game.
State A
State 2B
Action
A
Action B
0
2
Q
6.92
7.95
Q
0.19
-0.12 0.20 0.63
8.02
Table 3: Q-functions learned by our method for the matrix game.
5 Experiments
In this section, we conduct experiments to show the effectiveness of our method on complex tasks. We benchmark our method the Multi-Agent COordination (MACO) benchmark (33, which covers various classic coordination tasks in the literature of multi-agent learning and increases their complexity better evaluate the performance of different algorithms. The MACO benchmark is characterized by high demand on the sophistication of agent coordination. For NL-CG, we use mixing network that has one hidden layer with different widths. Detailed hyperparameter settings of our method can be found in Appendix ??. For fair comparison, we run all our experiments with random seeds and show the mean performance with a 95% confidence interval.
7

---

NL-CG (embed- 3,enum)
DCG
NL-CG tembed-4.terrtive 4,iterative Ames 88)
QMIX (embed-322
Alcha
Semsor
Gather
trens meenn
Test scaned moon
13
10
0.2
T(mi)
T(mil))
T(mi))
Figure Performance comparison against baselines on the MACO benchmark.
NL-CG (embed=10.enum) NL-CG (embed=2,enum)
NL-GG (embed=3.enum)
NL-CG (embed=4.enum)
Akoha
Serser
Hallway
Test battle wan mean
Test trens meen
28
18
0003
1.30
Timil
Timil
Figure 3: Influence of the size of the mixing network. When the width of the hidden layer 10, enumerating all linear pieces is quite time-consuming. We thus stop training when we observe its performance reaching or surpassing the best performance achieved by other algorithms.
NL-CG (embed=11 10, iterative Amax = 16)
NL-CG lembed=4.enen
Noha
Sensor
Gather
25
Test trans meen
Test scaned mon
15
1.8
00200
5529
5879
5.300 315
11.00 0.00
0.5
Figure 4: Our iterative optimization method reduces NL-CG's time cost and thus can use a larger mixing network, leading to better performance when checking the same number of linear pieces.
IL-CG lemaed=3.
(embed=32)
NL-C6 (emoed-4.iter)
DCG
In Fig. we compare NL-CG against the ofate-of-the-ar coordination graph learning method (DCG (4) and fully decomposed methods (QMIX (2), DICG 13 ). For both DCG and method, all experiments in the paper. For NI.-GG, we (1) set the hidden width to 3 and enumerate all configurations and (2) set the hidden width to 4 and run our iterative method with 7maa=4. We stop iteration when Ryaar slope contig- urations are visited. The result shows that our algorithm can outperform conventional CGs significantly. More- over, our iterative optimization method has comparable performance with the enumeration method, showing effectiveness. QMIX struggles on these tasks, indicating that these tasks are beyond the representation capacity of fully decomposed function.
NL-CG (omoed=16,
DICG
Pursuit
Test pray caught mean
the complete graphs for
0.25
0.75
1.00
1.50
3.75
T(mil)
Figure 5: Performance on Pursuit.

---

We further investigate the the influence of the mixing network's width. Specifically, we test NL- CG with width of 2. 3, and 10 and compare their performance Fig. Bl It can be observed that, generally, more units (10) in the hidden layer lead to better or at least equal performance than other configurations. This result is in line with our motivation: a powerful non-linear mixing network increases the capability of CGs.
In Fig- 4 we compare our enumerative and iterative methods. These two methods check the same number (16) of linear pieces, but the iterative method can use a hidden layer of 10. As a result, the iterative method outperforms the enumerative method.
we compare NL-CG against DCG 44, QMIX [22] and DICG Pursuit. We find NL-CG generally outperforms previous methods.
Additionally, in Fig. [|
on
5.1 Analysis of the optimality and efficiency of the iterative optimization method
Ground Truth Oue Values (Aloha)
Que of Found Solutions (Alaha)
NL CG /embed=3, iterative, Ane 4]lAloha)
Une
yux
actions
haraative oprtintzttion iile
Other sear 10
22 25. N8-45 (embbed03 Dacatiee, Newr 4)
30
25 Ao Graand Truth Our Valaes
OG (ombcd-3..ccm orum!
Figure 6: Left: Ground-truth Q value comparisons show that NL-CG learns policy with higher value than DCG. Middle: Actions obtained by enumerative and iterative methods have similar values. Right: Qiot output of NL-CG against ground-truth Q value (averaged Monte Carlo returns).
Seaching Time Comper son (Aicha)
Seaching Time Compantto [Senter]
Seaching Time Compantoo (Grther
oprimicaaiin (fo -4)
ale
25
Enumerating pleces (ms)
Esumentting all pieces (ms)
Esumenting all pieces (mm)
Figure 7: Efficiency of the iterative method. x-axis: Time spent by enumerating all pieces. y-axis: Time spend by the iterative method. The farther down the line y = x, the faster the method is.
Although we have checked the performance of our iterative optimization method, learning curves can not fully reveal its optimality and efficiency. In this section, we provide optimality and efficiency analyses by checking the action selection results and time costs in detail.
In Fig. Vig---midee middle, we compare the Qtat value of our enumerative and iterative optimization methods. We can see that the iterative method is optr-aptimal after checking only 4 (embed=3) slope configura- tions: the Qaluus of its actions are very close to those selected by enumeration and are better than those selected by DCG, In Fig. left, we compare the ground truth Q estimates of DCG and NL-CG (embed=3, iterative, R'mar 4). The result shows that NL-CG learns policy with higher value. In Fig. right, we compare the Qiot values estimated by NL-CG (embed=3, iterative, Umaz = 4) against ground truth Q estimates. The estimation errors on all tested state-action pairs are less than 20%.
In Fig. 7 we compare the time spent by enumerative and iterative optimization methods. It can be found that the iterative method saves 50% to 65% of running time. We can thus conclude that the iterative optimization method provides good trade-off between complexity and optimality.

---

Conclusion
In this paper, we extend coordination graphs beyond linear decomposition by introducing non-linear mixing networks. Experiments manifest its superior representation power on complex tasks that conventional CGs are not able to solve. important research direction is the stability of non-linear CGs and to get rid of the non-negative constraint on weights of the mixing network. The authors do not see obvious negative societal impacts of our method.
References
[1] Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In International Conference on Machine Learning, pages 146-155, PMLR, 2017.
[2] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Represen- tations, 2018.
[3] David Avis and Komei Fukuda. Reverse search for enumeration. Discrete applied mathematics, 65(1-3):21-46, 1996.
[4] Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In Proceed- ings of the 37th International Conference on Machine Learning, 2020.
[5] Jacopo Castellini, Frans Oliehoek, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. arXiv preprint arXiv:1902.07499 2019.
[6] Shanjun Cheng. Coordinating decentralized learning and conflict resolution across agent boundaries. PhD thesis, The University of North Carolina at Charlotte, 2012.
[7] Lingyang Chu, Xia Hu, Juhua Hu, Lanjun Wang, and Jian Pei. Exact and consistent interpre- tation for piecewise linear neural networks: A closed form solution. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1244-1253, 2018.
[8] Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference learning theory, pages 907-940. PMLR, 2016.
[9] Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML., volume 2, pages 227-234. Citeseer, 2002.
[10] Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learning, pages
PMLR, 2019.
[11] Jelle Kok and Nikos Vlassis. Collaborative multiagent reinforcement learning by payoff propagation. Journal of Machine Learning Research, 7(Sep): 2006.
[12] Chenghao Li, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang Celebrating diversity shared multi-agent reinforcement learning. Advances in Neural Infor- mation Processing Systems, 34:3991 2021.
[13] Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit coordination graphs for multi-agent reinforcement learning. In Proceedings of the 20th International Conference Autonomous Agents and MultiAgent Systems, pages 764-772, 2021.
[14] Ryan Lowe, Yi Wu, Aviy Tamar. Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch, Multi- agent actor-critic for mixed cooperative-competiive environments. In Advances in Neural Information Processing Systems, pages 6390, 2017.
[15] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi- agent variational exploration. Advances in Neural Information Processing Systems, pages 7611-7622, 2019.
10

---

[16] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proceedings of the 27th International Conference on 2014.
Neural Information Processing Systems-Volume
Volume 2, pages
[17] Frans Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
[18] Liviu Panait, Sean Luke, and R Paul Wiegand. Biasing coevolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation, 10(6):629-666 645, 2006.
[19] Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise linear activations, arXiv preprint 2013.
[20] Huy Xuan Pham. Hung Manh La, David Feil-Seifer, and Aria Nefian. Cooperative and distributed reinforcement learning of drones for field coverage, 2018.
[21] Miroslav Rada and Michal Cerný, A new algorithm for enumeration of cells of hyperplane arrangements and a comparison with avis and fukuda's 's reverse search. SIAM Journal Discrete Mathematics, 32(1 11455-4735 2018.
[22] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4292 4301, 2018.
[23] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning. pages 4558 4566. PMLR, 2018.
[24] 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. In International Conference on Machine Learning, pages 5887-5896, 2019.
[25] Ruben Stranders, Alessandro Farinelli, Alex Rogers, and Nick Jennings. Decentralised coor- dination of mobile sensors using the max-sum algorithm. In Twenty-Fiie First International Joint Conference on Artificial Intelligence, 2009.
[26] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In Pro- ceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 2085-2087. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
[27] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceed- ings of the tenth international conference on machine learning, pages 330-337, 1993.
[28] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent gelarnnng. International Conference on Learning Representations (ICLR), 2021.
[29] Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforce- ment learning with emergent roles. Proceedings of the 37th International Conference on Machine Learning, 2020.
[30] Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang Rode: Learning roles to decompose multi-agent tasks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[31] Tonghan Wang, Jianhao Wang, Wu Yi, and Chongjie Zhang. Influence-based multi-agent exploration. Proceedings of the International Conference on Learning Representations (ICLR), 2020.
11

---

[32] Tonghan Wang, Jianhao Wang. Chongyi Zheng, and Chongjie Zhang. Learning nearly decom- posable value functions with communication minimization. In Proceedings of the International Conference Learning Representations (ICIR), 2020.
[33] Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang. Context-aware sparse deep coordination graphs. In Proceedings of the International Conference on Learning Representations (ICLR), 2022.
[34] Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Dop: Off-policy multi-agent decomposed policy gradients. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[35] Zhao Xu, Yang Lyu, Quan Pan, Jinwen Hu, Chunhui Zhao, and Shuai Liu. Multi-vehicle flocking control with deep deterministic policy gradient method. 2018 IEEE 14th International Conference on Control and Automation (ICCA), Jun 2018.
[36] Qianlan Yang, Weijun Dong, Zhizhou Ren, Jianhao Wang, Tonghan Wang, and Chongjie Zhang. Self-organized polynomial-time coordination graphs. In International Conference on Machine Learning, pages 24963-24979. PMLR, 2022.
[37] Thomas Zaslavsky. Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes: Face-count formulas for partitions of space by hyperplanes, volume 154. American Mathematical Soc., 1975.
[38] Chongjie Zhang and Victor Lesser. Coordinating multi-agent reinforcement learning with limited communication. In Proceedings of the 2013 international conference on Autonomous agents and multi-agen systems, pages 1101-1108, International Foundation for Autonomous Agents and Multiagent Systems, 2013.
12


Reviews:
[{"review_id": "axYDqevqpc5", "reviewer": "Reviewer_PvfL", "summary": "This paper addressed the problem of cooperative multi-agent reinforcement learning by proposing an improvement over value decomposition method. They extend the concept of coordination graph to non-linear combination of value functions. \n\nThe core of the method relies on coordination graph. In coordination graphs, an edge is drawn between two interacting agent and a joint value function is learned through reinforcement learning. Given such graph, a globally optimal joint action can be computed to maximize a combination of the edge value functions. Traditionally, those value functions are summed and we can use algorithms such as max-plus to find the joint action. The author extend this process to non-linear combinations with deep network using LeakyReLU activations.  \n\nThey extend the max-plus algorithm to this class of graphs by decomposing the problem as piecewise linear combinations. The first proposed algorithm has an exponential time complexity in the width of the mixing network due to enumerating all possible slope configuration but the authors propose an approximation which converge to a local optimum and rely on an annealing strategy to try to escape it. \n\nThe experiments compare the performance of the whole algorithm on the MACO benchmark against two baselines: QMIX and DCG. \nA second set of experiments compare the optimality of the action selection only between the two propose algorithm,  DCG and a random baseline.\n", "questions": "1. Is there an application that would lead to similar dynamics as the problem illustrated in section 4? It would be useful to provide an example to further motivate why we would need the extra complexity. \n2. The graph structure is barely discussed, in the original max-plus there are issues with graphs presenting cycles, how would your algorithm be affected? \n3. Why are the NL-CG method starting at higher position than the other methods in figure 2? \n4. The performance of QMIX is surprisingly low, why is that? It would have been useful to compare in another MARL where QMIX is not so bad e.g. starcraft. \n5. In figure 5, how can DCG be compared with the method since they should use different Qtot (linear vs non linear)? \n", "limitations": "The authors do not explicitly mention any limitations of their method. I believe it would be valuable to add a paragraph. An obvious limitation to this family of method is that they require the graph structure to be known. Discussing different type of graph structure or sparsity would have been useful. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem of cooperative multi-agent RL has many societal applications and there is still a lot of progress to be done in being able to solve it efficiently. This paper contributes towards this goal by extending state of the art techniques based on value decomposition methods. \n\nExtending CGs to non-linear combination does intuitively increase the representation capability of the global value function, similarly to QMIX vs VDN, I believe the idea is sound. The author demonstrates this through the use of an example in section 4 and further validate it empirically. \n\nOverall the paper is well written and quite easy to follow. The algorithms are sound and clearly explained.\n\nWhen extending the max-plus algorithm to piecewise linear combination, they clearly explain the results and the derivation seems correct. \n\nThe weighted max-sum could be moved to appendix. \n\nThe plots from figure 5 and 6 are quite hard to follow, and the axes are not clear at all. Even if the author try to explain their meaning in the caption, it would be wise to choose another type of representation that is more intuitive for the reader. Furthermore I believe there are some unclarity on the correctness of this experiment regarding the choice of Qtot (see questions). \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KO6QiPjGG_", "reviewer": "Reviewer_Gt8B", "summary": "The paper proposes to extend the coordination graph framework to allow for non-linear mixing of agent payoffs/pairwise utilities, in a way similar to how the QMIX algorithm extends VDN by mean of mixing network. The problem of being able to solve the subsequent decentralized constraint optimization required to compute the optimal joint action is tackled by resorting to piece-wise neural network analysis, and nothing that it suffices to solve a linear DCOP for each possible slope configuration in order to find such optimal action. Moreover, an iterative version of this algorithm is proposed, possibly trading off optimality of the selected joint action with a reduced number of DCOPs to solve.", "questions": "- [Castellini et al., 2021](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj92tifi634AhU6RPEDHUIuBXUQFnoECBoQAQ&url=https%3A%2F%2Fresearch.tudelft.nl%2Ffiles%2F94310595%2FCastellini2021_Article_AnalysingFactorizationsOfActio.pdf&usg=AOvVaw0pSTZXIivp-1y3apJsQhMH), is such an extremely relevant citation here, showing the benefits of higher-order factorizations on tackling an exponential number of joint actions over both centralized controllers and independent learners.\n- Your explanation of relative overgeneralization is a bit not-on-point (indeed, each agents is not supposed to know the actions of the others). Relative overgeneralization occurs when agents are pushed towards favouring a suboptimal behaviour because this gives, on average, a higher reward than the optimal coordinated behaviour. This happens because the concurrent learning process of the other agents shadows the optimal strategy with its exploration (equilibrium shadowing), rendering it less attractive than a suboptimal one.\n- It may not be immediately clear how you decompose LeakyReLU$(\\mathbf{o}_i)$ as $\\mathbf{c}_i\\circ \\mathbf{o}_i$, where $c_i$ is simply the multiplication coefficient of the LeakyReLU (so either $\\alpha$ or $1$). Therefore a reader may be a bit surprired of the definition of the slope configuration $\\mathbf{c}\\in\\{\\alpha,1\\}^m$. Please clarify what $\\mathbf{c}_i$ is and where do you get it.\n- What do you mean exactly by a joint action $\\mathbf{a}$ falling outside a given piece $\\rho_k$ on line 164? Perhaps you mean that the $q_i,q_{ij}$s generated by the joint action $\\mathbf{a}_k$ (I think these are $\\mathbf{q}_k$ in your notation) generates a different slope configuration $\\mathbf{c}^{m\\not=k}$? This should be better clarified.\n- What are the CG topologies for the different experiments for both your method and DCG? Why have you come up with such topologies?\n- In Figure 2, when using NL-CG with an embedding of 4 units, is there any evidence that the iterative algorithm is performing well because it is indeed a good approximation and not because it is simply solving the constraint at every possible slope configuration (thus reducing to the enumeration algorithm in practice)? This should be shown somewhere, possibly in an Appendix if the space constraints are too limiting (although I would prefer to see such a figure rather than the very lengthy Algorithms 1, 2 and 3, that are not really adding much to the method explanation, that is already quite clear).\n- In Figure 4, how do you guarantee that the iterative method is only solving the constrained problem for 16 slope configurations and not more?\n- In Figure 5, what $Q_{tot}$ are you using as a reference? Are you using the one from NL-CG with enumeration? Or perhaps you are computing some sort of ground-truth Q-function? That should be specified for a reader to clearly understand and appreciate the results.", "limitations": "The possible limitations of the proposed method are actually never discussed in depth. The authors should make an effort and address this, trying to identify possible situations in which the proposed method could not perform as expected, and the reasons for this being the case.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** Up to the best of reviewer's knowledge, the idea of using a non-linear function to combine components in a coordination graph is novel, and so it is the algorithm proposed to identify the optimal joint action in such a non-linear representation. \n\n**Quality:** The paper is in general technically sound, and the methodological claims are well supported by experimental results. The set of experiments and analysis proposed is good, and is really capable of addressing most of the concerns a reader may come up with. I only have some remarks for the authors, mainly concerning some more in-depth explanation of experimental details or to provide support of some claims. For example, it is never explained what CG topologies are used for the proposed experiments (also valid for the DCG baseline), while I think this is a relevant detail that should be reported. Or, where did you get the $Q_{tot}$ used in Figure 5? This is never explicitly explained, but is an important information to understand what the figure is representing.\n\nAlso, I have some small concerns about the performance of the iterative algorithm. For example, when using NL-CG with an embedding of 4 units in Figure 2, is there any evidence that the iterative algorithm is performing well because it is indeed a good approximation and not because it is simply solving the constraint at every possible slope configuration? This should be assessed before claiming that is is reducing the number of solved slope configurations as you are doing.\n\n**Clarity:** The work is in general clearly written, and given the reader all of the required information to correctly understand both the proposed methodology and the experimental results, with just some minor exceptions (see **Questions** below).\n\nPerhaps the explanation of the adaptation of Max-Sum to the non-linear DCOP setting may be a bit improved: what do you mean exactly by a joint action $\\mathbf{a}$ falling outside a given piece $\\rho_k$ on line 164? Perhaps you mean that the $q_i,q_{ij}$s generated by the joint action $\\mathbf{a}_k$ (I think these are $\\mathbf{q}_k$ in your notation) generates a different slope configuration $\\mathbf{c}^{m\\=k}$?\n\n**Significance:** The presented idea is indeed significant, and advances our understanding of the field. With the great interest that both value-decomposition methods (with a and growing impact of higher-order decompositions)  and non-linear mixing architectures are gaining, this is a valuable contribution and could possibly allow for even better application of mixing techniques to coordination graph learning (that has proved indeed useful in learning better representations [Castellini et al., 2021](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj92tifi634AhU6RPEDHUIuBXUQFnoECBoQAQ&url=https%3A%2F%2Fresearch.tudelft.nl%2Ffiles%2F94310595%2FCastellini2021_Article_AnalysingFactorizationsOfActio.pdf&usg=AOvVaw0pSTZXIivp-1y3apJsQhMH).", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FF0UzYZx5H", "reviewer": "Reviewer_1Zfb", "summary": "The paper introduces a convex mixing network, that is learned using a QMIX-style hyper-network, for coordination graphs. The authors prove that a maximum over the piecewise-linear parts of the mixing network corresponds to the global maximum and introduce an iterative optimization method for larger mixing networks that converges to a local maximum piecewise-linear solution. The resulting algorithms are compared with DCG on some MACO benchmark, and show impressive improvements on some. The authors also compared the enumeration over all parts with their iterative method in ablation studies.", "questions": "1) Is the wall-clock time of NL-CG simply DCG_time times num_iterations, or does the initialization with the optimal actions of previous iterations speed up the message passing?\n\n2) Did you follow all the design decisions of the DCG implementation, or did you leave out some things (e.g. the state-dependend bias)?\n\n3) Do you have an explanation why NL-CG performed so much better than DCG in Aloah and Sensor (but not in Gather)?\n", "limitations": "- A wallclock-time comparison to DCG would have been nice.\n- It is unclear how well the algorithm scales to realistic applicatons with large action spaces, like the StarCraft2 experiments in the DCG paper.\n", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The reviewer liked the paper a lot, especially the theoretical part. Although the authors should better distinguish between the domain of a function and the inputs that \"correspond\" to a function (see detailed comments), the reviewer has checked the proofs thoroughly and believes they are correct. The authors should mention that their restrictions on the mixing network is almost identical to input-convex neural nets (ICNN, Amos et al., 2016). ICNN are a bit more general, but the theoretical analysis should still hold. In particular Lemma 1 looks as if it could have useful applications in other fields using ICNN.\n\nSection 4 is not particularly illustrative, but the experimental experimental validation looks very well done and the results are very good on Aloha and Sensor. The biggest open question is scalability: a mixing network of size 10 might still be considered small. The authors could provide a better runtime comparison of their algorithm in comparison to DCG (see questions), and with number of network size and number of iterations of the approximate algorithm. \n\n**Detailed comments**\n\n- eq.4+5: as the mixing network $f_n$ depends on $s$, so must $Q_{tot}$\n- l.132: \"extended to other activation functions like ReLU\" -- ReLU is already a special case of LeakyReLU with $\\alpha=0$\n- l.150: the outputs $o_i$ can easily be confused with the observations $o_i$\n- l.162ff: you should differentiate between the domain of affine function $\\rho_k$, which is the entire input space (otherwise one could not compute the output), and the inputs $q$ that \"correspond\" to $\\rho_k$, that is, where the forward pass produces $c^k$. The two words are currently nowhere properly defined and used synonymous (e.g. Lemma 1 or l.172). Maybe define the set $q \\in Q_k$ in which the forward pass yields $c^k$ to be precise.\n- Lemma 1 is really interesting, but should be expressed more precisely: for which class of functions does it hold, and how the $\\rho$ functions are defined. This will allow easier transfer to other fields. You can also remove the $s\\neq r$ restriction, as for $s=r$ the inequality still holds.\n- l. 169: it took the reviewer some time to believe the claim $h^r_{ij} \\geq h^s_{ij}$. It would help to emphasize that the two slope configurations are identical, except for entry ${ij}$, and that the output $o_{ij}$ is therefore the same in both functions. A sentence about how the inequality holds might also help.\n- l.184: the word \"infeasible\" is unclear here; you need to establish the terminology as suggested above\n- l.200: as you mentioned later, using the condition $c_{real} = c_p$ can lead to loops. Why don't you just use $\\rho_{real}(q(a_{real})) = \\rho_p(q(a_p))$?\n- l.217: the \"reward is invariant to the identity\" only for the second decision\n- l.221ff: the example is very unclear. How do the 5 equations look like? Why do you set $q_i(s_{2B}, A)=0$ (doesn't this already used up the equation for 0 action B's)? All together the reviewer did not see a large benefit of Section 4. \n- l.252: why 4 slopes? Shouldn't it be 3^2=8 slope configurations?\n- l.252: it states that \"$n_{max}=4$\", but the Figure states $n_{max}=8$\n- l.272f: it is unclear how you compare NL-CG with DCG in Figure 5. How does DCG get different entries on the x-axis? \n \n**References**\n\nAmos et al., 2016: Input Convex Neural Networks; https://arxiv.org/abs/1609.07152", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "01OSMHkARYl", "reviewer": "Reviewer_W1Zi", "summary": "This paper investigates the problem of learning non-linear coordination graphs in multi-agent reinforcement learning. It proposes the first non-linear coordination graph by extending CG value decomposition beyond the linear case. It proposes the weighted max-sum algorithm to solve the greedy-action selection problem in the non-linear coordination graph.", "questions": "I have the following questions:\n\n1. In lines 112-113, why is a DNN with piece-wise linear (PWL) activation functions (e.g. ReLU, LeakyReLU, PReLU) is equivalent to a PWL function? Did it motivate you to investigate the problem of the non-linear coordination graph?\n\n2. In lines 141-142, when the mixing network is non-linear, maximizing Q_tot is NP-hard. Can you elaborate more? As far as I know, deep networks have capacities to learn good models.\n\n3. Can you highlight your contributions in Alg. 1, 2 and 3? \n", "limitations": "Please see the above comments.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThis paper investigates a very important problem in coordination graphs. Previous methods focus on the linear case, which has limited representation capacity on Q values. This paper proposes a novel method by using a mixing network, the active function is LeakyReLU.\n\n\nWeaknesses: \n\n1. Using a mixing network to represent the coordination graph is not new. Previous work [1] uses GNN, which can seem like a mixing network, and ReLU or LeakyReLU can also be used in GNN.\n\n2. The experiments are not strong, CASEC [2] is not compared.\n\n3. More scenarios should be tested. As this paper considers the representation capacity issue, more experiments in complex scenarios, for example, the predator-prey task and SMAC in [3], should be conducted to show the merit of the method.\n\n4. Some curves are not fully shown. For example, in Fig 3, the curves of NL-CG are not fully shown.\n\n5. This paper is hard for me to follow. The writing can be improved.\n\n[1] Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learning\n\n[2] CONTEXT-AWARE SPARSE COORDINATION GRAPHS\n\n[3] Deep Coordination Graphs\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept