Self-Organized Polynomial-time Coordination Graphs
Authors: Weijun Dong
Qianlan Yang
Zhizhou Ren
Jianhao Wang
Tonghan Wang
Chongjie Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: Multi-Agent Reinforcement Learning
Coordination Graphs
Polynomial-time DCOP

Abstract: Coordination graph is a promising approach to model agent collaboration in multi-agent reinforcement learning. It factorizes a large multi-agent system into a suite of overlapping groups that represent the underlying coordination dependencies. One critical challenge in this paradigm is the complexity of computing maximum-value actions for a graph-based value factorization. It refers to the decentralized constraint optimization problem (DCOP), which and whose constant-ratio approximation are NP-hard problems. To bypass this fundamental hardness, this paper proposes a novel method, named Self-Organized Polynomial-time Coordination Graphs (SOP-CG), which uses structured graph classes to guarantee the optimality of the induced DCOPs with sufficient function expressiveness. We extend the graph topology to be state-dependent, formulate the graph selection as an imaginary agent, and finally derive an end-to-end learning paradigm from the unified Bellman optimality equation. In experiments, we show that our approach learns interpretable graph topologies, induces effective coordination, and improves performance across a variety of cooperative multi-agent tasks.

Under review as a conference paper at ICLR 2022
SELF-ORGANIZED POLYNOMIAL- COORDINATION GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Coordination graph is a promising approach to model agent collaboration in multi- agent reinforcement learning. It factorizes large multi-agent system into a suite of overlapping groups that represent the underlying coordination dependencies. One critical challenge in this paradigm is the complexity of computing maximum- value actions for graph-based value factorization. It refers to the decentralized constraint optimization problem (DCOP), which and whose constant-ratio approx- imation are NP-hard problems. To bypass this fundamental hardness, this paper proposes novel method, named Self- Self-Organized Polynomial time Coordination Graphs (SOP-CG), which uses structured graph classes to guarantee the optimal- ity of the induced DCOPs with sufficient function expressiveness. We extend the graph topology to be state-dependent, formulate the graph selection as an imag- inary agent, and finally derive end-to-end learning paradigm from the unified Bellman optimality equation. In experiments, we show that our approach learns interpretable graph topologies, induces effective coordination, and improves per- formance across variety of cooperative multi-agent tasks.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) is a promising approach to a variety of real-world applications, such sensor networks (Zhang & Lesser 2011 Ye et al. 2015), traffic light control (Van der Pol & Oliehoek] (016), and multi-robot formation (Alonso-Mora et al. 2017). One of the long-lasting challenges cooperative MARL is how organize coordination for large multi-agent system. Coordination graph (Guestrin et al. (201) is a classical approach to represent coordination relations in the reinforcement learning framework. It decomposes multi-agent system into a suite of overlapping factors. Each factor is a hyper-edge covering subset of agents that may involve coordinated behaviors. More specifically, the joint value function of the multi-agent system is factorized to the summation of local value functions based on factors edges. Such graph structure a particular type of inductive bias that encodes task-specific coordination dependencies. It is known that conducting appropriate inductive bias both reduce the model complexity and improve the generalizability (Battaglia et al. 2018).
One fundamental problem for coordination graphs is the trade-off between the representational capacity of value functions and the computational complexity of policy exe- cution. To obtain value functions with high expressiveness, an advanced approach, deep coordination graphs (DCG) (Böhmer et al. 2020), considers a static complete graph connecting all pairs of agents. This graph structure has high representational capacity in terms of function expressive- ness but raises a challenge for computation the execu- tion phase. The greedy action selection over coordina- tion graph can be formalized to a decentralized constraint optimization problem (DCOP), finding the maximum-vee value joint actions (Guestrin et al. 2001 Zhang & Lesser 2013 Böhmer al., 2020)). Note that the DCOP and its any constant-ratio approximation are NP-hard problems, espe- cially for the complete graph used in DCG (Dagum & Luby
100 10% quanolee reletie error
100.09 0%
accuracy
20.0%
0%
relative error
Arcuracy
80.
30.0%,
15.0%
70.0%
10.0%
60.0%
5.0%
50.0%
10
14
16
Number of agents
Figure 1: A motivating example with the accuracy and the relative joint Q error of max-sum algorithm w.r.t. the number of agents.

---

Under review as a conference paper at ICLR 2022
State $1
State $1
State 51
Graph
Uiility
Graph
State $2
Learning
State S2
Learning
State &2
Graph Cless 5
Figure 2: Illustration of our basic idea. For ease viewing, we mark each edge with a unique color. Our algorithm conducts different coordination graphs for different environment states. For example, the selection of graph topologies on states 81 and $2 depends on the utility functions on corresponding states. These utility values updated through the learning procedure.
Park & Darwiche 2004). From the perspective of theoretical computer science, any scalable heuristic algorithm (e.g.. max-sum algorithm (Pearl) 1988)) for DCOP problem may have an un- predictable gap with the optimal solution. To visualize this phenomenon, we conduct a motivating example for generating a suite of complete-graph DCOPs with random edge-values. More detailed experiment setting are deferred to Appendix [A] We investigate the accuracy and the relative joint Q error of the max-sum algorithm in computing optimal joint actions, which is the default imple- mentation of MARL methods based on coordination graphs (Stranders al. 2009 [Zang & Lesser) 2013 Böhmer et al., 2020). The results are shown in Figure [ As the number of agents increases, accuracy greedy action selection consistently decreases, and the relative joint Q error between the selected and optimal joint actions increases accordingly. How to incorporating polynomial-time complexity guarantee into coordination graphs with sufficient function expressiveness remains an open problem in MARL.
1993
In this paper, we aim to overcome a dilemma coordination graphs, i.e., expressive graph struc- tures lead to computationally intractable DCOPs but concise graph structures are in lack of function expressiveness. To tackle this problem, we propose a novel graph-based MARL method for multi- agent coordination, named Self-Organized Polynomial-time Coordination Graphs (SOP-CG), that (1) utilizes structured graph topologies with polynomial-time guarantees for DCOPs and (2) extends their representation expressiveness through dynamic graph organization mechanism. These two characteristics open up new family of MARL algorithms. More specifically, we first construct graph classes guaranteeing polynomial-time DCOPs and then conduct state-dependent graph se- lection mechanism. Such dynamic factorization structure can be self-organized. We introduce an imaginary coordinator agent, whose action is to select a graph topology in given class at each time step. SOP-CG incorporates this imaginary agent into the Bellman optimality equation supporting end-to-end learning. Figure iillustrates the basic idea of SOP-CG. We integrate the search of graph structures into the MARL paradigm. The utilities of different graph topologies learned along with the RL objective. As the graph utilities are updated through agent- enveromnvirnm interactions, the coordination graph will evolve the topology characterizing the coordination dependencies.
We evaluate the performance of SOP-CG in both grid-world and simulated physical environments. Empirical results challenging tasks demonstrate that SOP-CG outperforms ofate-of-the-ar base- lines. By extensive ablation studies, we verify that harnessing specific structures with optimality guarantee of the induced DCOPs improves the sample quality and the accuracy of the one-step TD target. Furthermore, we show that SOP-CG can learn interpretable and context- context-dependent coordina- tion graphs, which induces effective and dynamic coordination among agents.
RELATED WORK
Multi- ageti reinforcement learning (OroojlooyJadid & Hajinezhad 2019) is challenged by the size of joint action space, which grows exponentially with the number of agents. Independent Q-learning
2

---

Under review as a conference paper at ICLR 2022
Tan 1993
Foerster et al. 2017) models agents independent learners, which makes the environ-
ment non statiiona in the perspective of each agent. An alternative paradigm called centralized training and decentralized execution (CTDE; Kraemer & Banerjee| 2016) is widely used in both policy-based and value-based methods. Policy-based multi-agent reinforcement learning methods use centralized critic to compute gradient for the local actors (Lowe et al. 2017 Foerster al.) 2018 Wen et al. 2019; Wang et al. (220dd). Value-based methods usually decompose the joint value function into individual value functions under the IGM (individual-global -lobbal--aa principle, which guarantees the consistency between local action selection and joint action optimization (Sunehag jt al.] 2018; Rashid al., 2020b) |Son et al.) 2019 Wang et al., [021aa] Rashid et al. (020aa) Other work also studies this problem from the perspective of agent roles and individuality (Wang et al.) 2020a by Diang Lu 202T) or communication learning (Singh et al. 2018 Das et al. 2019 Wang
et al. 2020c). Compared to these methods, our work is built upon graph-based value decomposition, which explicitly models the interaction among agents.
Coordination graphs are classical technique for planning in multi-agent systems (Guestrin et al. 2001] 2002b). They are combined with multi-agent deep reinforcement learning by recent work (Castellini et al., 2019; [ööhmer al. 2020; Li et al.] 2020 Wang et al., (021b). Joint action selection on coordination graphs can be modeled as a decentralized constraint optimization problem (DCOP), and previous methods compute approximate solutions by message passing among agents (Pearl 1988). As the work which is most closed to our method, (Zhang & Lesser (2013) presents an algorithm based on coordination graph searching. They define a measurement to quantify the potential loss of the lack of coordination between agents and search for a coordination structure to minimize the communication cost within restricted loss of utilities. However, their induced DCOPs still remain NP-hard. In contrast, minimizing communication is not our core motivation, and we aim to use a structured graph class to maintain sufficient function expressiveness when bypassing the computational hardness of large-scale DCOPs (Dagum & Luby 1993 Park & Darwiche 2004).
3 BACKGROUND
In this paper, we consider about fully cooperative multi-agent tasks that be modelled Dec- POMDP Olichook et al. 2016) defined as M = (D, S, ( {O")= {o'} R, h, by. 7), where D = .l...................... n is the set of n agents, S is a set of states, is the horizon of the environment, E 1) is the discount factor, and by E A(S) denotes the initial state distribution. At each stage f, each agent takes an action a; E A' and forms the joint action a (a1 "e1....aa,.) which leads to a next state s' according to the transition function T(s'|s, a) and an immediate reward R(s, a) shared by all agents. Each agent i observes the state only partially by drawing observations o E O', according to og. The joint history of agent i's observations oi, and actions di,, is denoted as T. (0..0,
01,1-1, 0,,1) E (O' x At)* x O
Deep Q-Learning. Q-Jearning algorithms is well-known algorithm to find the optimal joint action-value function ('(ssa) = r(s,, a) + [maxa Q* (s', a a²)) Deep Q-learning approximates the action-value function with a deep neural network with parameters 0. In Multi-agent Q-learning algorithms (Sunehag et al. 2018 Rashid et al. 2020b [on et al. 2019 Wang et al. 2021a). a replay memory is used to store the transition tuple (T, a, r, T'), where r is the immediate reward when taking action at joint place of Qs,, a; 0). because of partial observability. Hence, parameters 0 are learnt by minimizing the following expect TD error:
history with transition to r'. Q(T, a; 0) is used in
((0)= B(T.TTT [I+ VV -+:00)
(1)
where V(T':0-) = max,' Q(T', a': ) is the one-step expected future return of the TD target and 0- are the parameters of the target network, which will be periodically updated with O.
Coordination graphs. An undirect coordination graph (CG, Guestrin et al. (001 G (.E)
contains vertex v; E V for each agent 1 S í S n and a set of (hyper-)edee Jedges in 3 C 2n which represents coordination dependencies among agents. Prior work considers higher order coordination where the edges depend on actions of several agents (Guestrin et al., 2002a| Kok & Vlassis, 2006
Guesstrn al. 2002b). Such coordination graph induces a factorization of global Q function:
3

---

Under review as a conference paper at ICLR 2022
Quo((s,a) + VEV
Σ
f( a
(2)
where I represents the individual utility of agent and f specifies the payoff contribution for the actions of the agents connected by the (hyper-)edge e, so that the global optimal solution can be found through maximizing this joint value. The special case that & is an empty set yields VDN, but each additional edge enables the value representation of the joint actions of a pair of agents and can thus help to avoid relative-overe ciriiii--oeereeeealizatiioo (Böhmer et al. 2020). In many coordination graph learning works (Zhang & Lesser 2013 Böhmer et al. 2020; Wang et al. (021b), the hyper-edges are simplified into pairwise edges. The graph is usually considered to be specified before training. Guestrin et al. (2002b) and /Zhang & Lesser (2013) suggest that the graph could also depend on states, which means each state can have its own unique CG.
4 SELF-ORGANIZED POLYNOMIAL- TIME COORDINATION GRAPHS
A common method for multi-agent reinforcement learning is to decompose the joint value function into a linear combination of local value functions, each of which conditions on actions of subset of agents (Guestrin et al., 2001] Böhmer et al. 2020). With this paradigm, computing joint action with maximum value can be modeled as distributed constraint optimization problem (DCOP). General DCOP and any constant-ratio approximation have been proved to be NP-hard (Dagum & Luby 1993 Park & Darwiche 2004). Previous work adopts a variety heuristic algorithms for action selection (Kok & Vlassis 2006; Wang et al. 20211). The imperfection of heuristics may lead to two side effects: (a) collecting bad samples and (b) errors in constructing one-step TD target, which hurt the learning performance.
To address these issues, we investigate polynomial-time coordination graphs, in which the induced DCOPs can be solved in polynomial time. We present novel algorithm called Self- Peff-Organized Polynomial-time Coordination Graphs (SOP-CG), that utilizes a class of polynomial-time coordi- nation graphs construct dynamic and state-dependent topology. In Section 4.1 introduce our value factorization upon coordination graphs, which can hold the optimality guarantee of the induced DCOPs without significantly sacrificing the representational capacity by using bottom-up design. To enable efficient topology self-organization, in Section 4.2 we unify the graph selection into the Q-learning framework by formulating the graphs as actions of an imaginary coordinator agent, and depict the whole framework of our algorithm. In Section [43] we further propose two polynomial-time graph class instances and discuss their theoretical advantages SOP-CG.
4.1 VALUE FACTORIZATION ON POLYNOMIAL- TIME COORDINATION GRAPHI
To establish an algorithm with optimality guarantee in action selection, approach first models ordination relations upon the graph-based based value factorization specified by deep coordination graphs (DCG::Böhmer&
(DCG; Böhmer et al., 2020),, in which the joint value function of the multi-agent system is factorized to the summation of individual utility functions qi and pairwise payoff functions 4ij as follows:
(()()) a: G)
Σ (.(T sE(n]
a.)
( 7/00 ai, az,a;);
(3)
(L.)EG
where the coordination graph G is represented by a set of undirected edges. In our method, we focus on Polynomial-Timee Coordination Graph which is defined as follows:
Definition (Polynomial-Time Coordination Graph) Let Groty denote the set of graph topologies whose induced DCOP can be solved in Poly(n, {[A,] )ia) running time with arbitrary edge values.
In the literature of coordination graphs, we know that the set of undirected acyclic graphs Guac is subset of Graly (Fioretto et al. 2018). However, undirected acyclic graph can contain at most n - edges in an environment with n agents, which suffers from the lack of function expressiveness.
To alleviate this problem, approach allows the graph topology to dynamically evolve through the transitions of environment status. Given different environmental states, the joint values can be factorized with different coordination graphs chosen from a predefined graph class C Gune C Proly-
4

---

Under review as a conference paper at ICLR 2022
This design is based assumption that, although long-horte hong-horizon task cannot be characterized by a static sparse coordination graph, the coordination relations at each single-time time step are sparse and manageable. The employment of this graph class fills the lack of representational capacity well as maintains a polynomial complexity of the induced DCOPs.
4.2 LEARNING SELF-ORGANIZED TOPOLOGY WITH AN EXPLICIT COORDINATOR
Now we present novel framework render the self-organized coordination graph. We introduce an imaginary coordinator agent whose action space refers to the selection of graph topologies, aiming to select proper graph for minimizing the loss within restricted coordination. When using the graph-based value factorization stated in Eq. (3), the graph topology G can be regarded as an input of joint value function Q(+(+), a; G). The objective of the coordinator agent is to maximize the joint value function over the specific graph class, which dual problem for finding graph to minimize the loss within the different restricted coordination structures (Zhang & Lesser (2013). Under this interpretation, we can integrate the selection of graph topologies into the trial-and-error loop of reinforcement learning. We handle the imaginary coordinator as usual agent in multi-agent ap.
Q-lcarning framework and rewrite the joint action as acg = (a1, "n, G).
Execution. Formally, time step t, greedy action selection indicates the following joint action:
arg max Q(T(+),), ,a,, anni G). (a) ..
(4)
Hence the action of coordinator agent G is naturally the corresponding component in Eq.
( arg max
(max Q(T(") G)
GEg
After determining the graph topology G the agents can choose their individual actions to jointly maximize the value function Q(T(*), a; G(t) upon the selected topology.
Training. With the imaginary coordinator, we can re-formulate the Bellman optimality equation and maximizing the future value over the coordinator agent's 's action:
Q' (T = B rr max max Q" (T', a':
(6)
G
Since the graph selection is part of agent action, the associative value Q(T, a; G) of graph G' can be updated through temporal difference learning. The network parameters f can be updated by minimizing the standard Q-learning TD loss:
(Wig - Q(T, a; a;;;))
Leg ( (rr'),
E
where Veg = max ..) Q(T', a'; O is the one-step TD target and O are the parameters of target network. ( is regarded part of the transition and is stored in the replay buffer together with the realistic agent actions. We include more implementation details of temporal difference learning in Appendix C
The overall algorithm of our approach is summarized in Algorithm I The graph selection step at line is is the main characteristic of our method, which differs from the static graph representation used by prior work (Guestrin et al. al. [2002a] Kok & Vlassis 2006 Böhmer et al. 2020). To support the self-organization of coordination graphs, the graph selection step raises a new computation demand, i.e., we need to find the best candidate from the graph class G, which will be another non-trivial combinatorial optimization problem. We will show that, by designing proper graph class G, we can maintain both computational efficiency and function representational capacity in the next subsection.
4.3 HARNESSING STRUCTURED GRAPH CLASSES FOR EFFICIENT COORDINATION
To achieve the efficient graph search over the polynomial -ime class instances, we investigate the following structures for the graph class G, which are subsets of G
5

---

Under review as a conference paper at ICLR 2022
Algorithm Self-Organized Polynomial-Time Coordination Graphs
Require: Predefined graph class G
1: Initialize replay buffer D
2: Initialize network with random weights
3: for episode= 1, .... .M do
4: Receive imitial observation - (0)
5: for t 0,... do
6:
Choose coordination graph G E 9 according to Eq. 5
Section 4.3
7:
Select actions (*) w.r.t G(O) and an e-greedy exploration
8:
Execute actions (*) and receive reward p(t) and observation (f++))
9: Store transition (- (1)), aat), r(1), ((++)) in D
10: end for
11: Sample random minibatch of transitions from 'D
12: Perform a gradient descent step on loss defined in Eq.
end for
Pairwise grouping Gp. This class introduced by Castellini al. (2019). n agents are parti- tioned to [n/2] non-overlan non-overlapping pairwise groups. Only pairwise interactions are considered and two agents are connected with an edge they lie in the same group.
Hierarchical organization Gи- Overlapping edges are allowed in this class. In system with n agents, the graph is organized as a tree with n 1 edges so that all agents form connected component. Even if agents not directly connected by edge, their actions are implicitly coordinated through the path on the tree. This provides the potential to approximate complex joint value functions.
Ih is actually the set of maximal undirected acyclic graphs. It is noteworthy that do not further incorporate the smaller graphs into both classes, since their representational capacity are dominated by existing graphs in the classes. We summarize the hardness of computing these problems upon differ- ent graph class in Table [ Although the representational capacity of Gp is relatively weaker, selecting (+) from this class can be rigorously solved by polynomial-time al- gorithms (Edmonds) 1965). which highlights the key benefit of Gp. In comparison, select- design
Select graph ((t)
Select actions on a given graph
Graph Class
Gr
GH
Complete graph
N/A
Table Computational considerations in choos- ing graph class. A check mark "V" means that known algorithms for the problem are guaranteed to find the optimal solution in polynomial time. The mark " "_ denotes that these settings use the specific heuristic methods.
ing (()) from Gn is non-trivial, greedy algorithm to compute approximated solutions. Note that, although the graph selection of GH may imprecise, its represented values are formally optimized by temporal difference learning with accurate action selection. Thus, we will show in the experiment section, 9H can still work as a promising graph class in absence of rigorous graph selection. Please refer to Appendix [ for the implementation details of the induced combinatorial optimization for graph selection.
Remark. In this paper, SOP-CG trades off the representational capacity of value function with the computational complexity within the polynomial-time boundary. Compared to fully connected graph, our sparse graphs restrict the value function class to a smaller space. This polynomial- graph class enables SOP-CG to achieve accurate greedy action selection using limited message pass- ing along the edges and achieve effective learning the centralized training process. Moreover, these graph classes enough to express the coordination dependencies in multi-agent task, using such topologies will more sample-efficien by virtue of the concise function classes (Battaglia et al. 2018), which becomes another potential advantage of our algorithm.

---

Under review as a conference paper at ICLR 2022
(a) Online data callertion
(b) Offline data collection
[c] Online data collection
Teat
Test Rutumn
T
SCP-CG (s)
-20
(ee)
-20
SOP-CG IGe)
-20
DCG (lee)
SaN-C (64
DCG
DCG
DCG (star)
-40
0.0
0.1
0.2
0.3
0.4
0.5
-40
0.0
0.2
0.3
0.5
0.0
0.1
9.2
0.3
0.4
0.5
Trained
Figure 3: Ablation studies on Sensor-network: (a) comparison against DCG with online data collec-
tion; (b) comparison against DCG with offline dataset; (c) comparison with static topologies.
5 EXPERIMENTS
In this section, we conduct experiments to answer the following questions: (1) Does the class of
polynomial-time coordination graphs improve our performance (see Section 5.1 (2) How well
does SOP-CG perform on complex cooperative multi-agent tasks (see Fig. ? (3) Can SOP-CG extract interpretable dynamic coordination structures (see Fig. 6)?
5.1 DIDACTIC EXAMPLE
We first study a didactic example to demonstrate two main con- tributions of this paper: (a) harnessing polynomial-time coordina- tion graphs to obtain optimality guarantee of the induced DCOPs; (b) maintaining function expressiveness by incorporating a class of structured graphs into the Q-learning framework. We conduct ab- lation studies on Sensor-network,, which is a classic task for test- ing multi-agent coordination (Lesser et al.,) 2003) [Zhang & Lesser 2011). We adopt the same task configuration as Wang el al. (2021b). As illustrated in Fig. 4 15 sensor agents are arranged as a x 5 ma-
10
Sensor
Target
Scan
Figure 4: Sensor-network.
trix while three targets randomly walk in the same grid space. At each timestep, an agent can choose to scan one of the eight nearby positions (inducing cost) or perform no operation. If two more agents scan the target simultaneously, the target is captured and produces a positive joint reward. We compare our algorithm with DCG (Böhmer et al., 2020) on this game. The default implementation of DCG uses fully connected coordination graph. In addition, DCG provides alternative imple- mentations on two static graphs Line (agent is connected with agent i - and i i+ 1) and Star (agent 1 is linked with others), which are two special instances of GH. SOP-CG (G#) has absolutely higher function expressiveness than DCG (line) and DCG (star).
For the first contribution, verify that the optimality guarantec of the induced DCOP in our al- gorithm improve the performance. We test these algorithms in both online (Fig. 31) and offline learning (Fig. BD) settings. For fair evaluation, we train DCG (line) and collect 15K experienced episodes throughout the training process to set up the diverse offline dataset. As shown in 3 b), SOP-CG outperforms DCG in both settings. In the offline setting, as the dataset is fixed for both algorithms, the main difference between SOP-CG and DCG lies in the construction of one-step TD target. Our algorithm is guaranteed to find the optimal solution of the induced DCOPs, which must play an important role in reducing the errors in computing TD target. We also observe that DCG sticks bad local optimum with online data collection, but its performance is improved in the offline setting. This result indicates that the hardness of greedy action selection causes DCG to collect low-quality samples in the online setting, which may hurt the final performance. In contrast, method converges to the same superior value in both settings, highlighting the effectiveness of polynomial-tine coordination graphs.
For the second contribution, show the importance of learning a state-dependent structure. As illustrated in Fig. B.. the performance SOP-CG is much better than both DCG (line) and DCG (star) with online data collection. A static sparse topology usually cannot express the coordina- tion dependencies in all steps, so these methods could not work well even if they are built upon polynomial-time coordination graphs.
7

---

Under review as a conference paper at ICLR 2022
SOP-CG (Ge)
SOP-CG (Ge)
DCG
CASEC
VON
QMIX
NDQ
Optimal Return
Pursult
Chase
Postman
12.5
250
200
7.5
150
5.0
100
2.5-
0.5
2.5
3.0
0.5
2.5
2.0
3.0
Figure 5: Learning curves on Pursuit, Chasing and Postman. The optimal return is demonstrated if it is available.
5.2 PERFORMANCE COMPARISON
To further demonstrate the effectiveness our algorithm and discuss the difference among the graph classes, we evaluate SOP-CG on three large-scale complex tasks with highly dynamic coordination requirements and partial observation: Pursuit, Chase and Postman.
Pursuit. This environment is also called predator-and-prey, which is widely used in recent work (Son et al.) 2019 Böhmer et al., 2020 Wang et al.] [02Tb). 20 agents and 10 random walking prey interact on a 10 x 10 grid-world. Based on a limited sight range, an agent can move on the map or catch adjacent prey. One prey is captured only if at least two adjacent agents catch it simultaneously, inducing joint reward of 1. After that, both agents and the captured prey are removed from the game, If only one agent tries catch the prey, will fail and receive punishment -1.
Chase. This is challenging task on the particle world with trained adversaries instead of built-in AIs created by Lowe et al. (2017). On the map with randomly generated obstacles, 10 slower agents chase 3 faster adversaries. For each collision between agent and an ad- versary, the agents receive a reward while the adversaries are punished. An agent or adversary can observe the units in a restricted circular area that is centered at its position. We train the agents by a specific algorithm, and the adversaries are concurrently trained by VDN.
Postman. 12 postmen work in vast community to deliver letters from residents to the post office. With the post office located the northwest of the community, the whole community is separated into three parts according to the distance to the post office, and each postman will only work in one region. Postmen need to pick randomly generated letters in the community. While two postmen meet each other, any they can collaborate in order to deliver the letters to the post office. A postman can observe the information of other postmen and the letters in sight range.
of them can offer its letters to another one, so
We compare our method with the state-of of- the-art coordination graph learning methods (DCG (Böhmer et al. 2020), CASEC (Wang et al. 2021b)), fully decomposed value-based meth- ods (VDN (Sunehag et al. 2018)), QMIX (Rashid et al. 2020bb) and communication--asel method (NDQ (Wang et al., )020c)). The implementation details and hyperparameter settings are included in Appendix D As presented in Fig. SOP-CG outperforms the baselines in all three environments.
Using smaller graph class will be more efficient if such a concise graph class is sufficient to express the coordination dependency in the task of interest. Taking the task Chase an example, DCG and CASEC performs as poorly as the fully-decomposed methods, as their graph classes are too large and complex to learn. However, our method significantly outperforms coordination graph learning algorithms with smaller graph class, which strongly confirms our statement. Furthermore, SOP- CG (Gr)) has better performance than SOP-CG (Gr) on this task, which may be due to the lack of representational capacity of Gp. On the contrary. Pursuit mainly involves pairwise cooperation, so SOP-CG (Gp) achieves better sample efficiency than SOP-CG (GH).
We will show that reducing the error of DCOP can also improve performance. On task Pursuit with 20 agents, our method achieves almost the optimal of this task while DCG has over two times larger gap with the optimal value than ours. The reason is that Pursuit requires precise collaborations. If only one agent tries to catch the prey, it will fail and induce a large punishment. When facing grow- ing scales, DCG and CASEC have a poor accuracy on DCOP,
showed before, which may lead
8

---

Under review as a conference paper at ICLR 2022
Group
Group
Sight agent
Opportunityl
agent and its id
adversary and its moving dircction
odge in the chosen graph
Figure 6: Various coordination graphs learned by our algorithm on Chase: (a) Self-organized group- ing at initialization; (b) Connecting to agent with rich observation for better information sharing; (c) Concentrated collaboration structure around an enclosed adversary.
to inaccurate greedy action selection, impeding DCG to better performance. the super hard task Postman, which requires agents to collaborate during long horizon, method also outperforms other methods.
5.3 VISUALIZATION OF DELF-ORGANIZED COORDINATION
A major strength of method is that SOP-CG can organize different coordination graphs adapt to different situations. Such an adaptive organization mechanism can improve the efficiency of multi-agent collaboration. To illustrate the coordination relations organized by SOP-CG, we vi- sualize the learned graph structures Chase. In Fig. 6 we take three snapshots chronologically from one episode. This episode is collected by SOP-CG (Gn) using the tree-based graph class. shows that SOP-CG can produce interpretable graph structures that characterize the ground-truth coordination dependencies. The learned coordination behaviors are interpreted as follows:
1. Fig. 64 presents the initial status of the game, where agents and adversaries are generated randomly on the map. As the three adversaries distribute in separate positions, the agents naturally form three groups to chase different adversaries.
2. After several time steps, in Fig, 60, two adversaries gather at the bottom left of the map- Note that, in this game, each agent can only observe objects within small circular range. Only agent can observe the two adversaries simultaneously, which makes it connect to the majority the rest of the agents and helps them recognize the position of the adversaries.
Finally, as illustrated by Fig. 6 the bottom adversary is surrounded by multiple agents, yield- ing an opportunity for the agents to win considerable rewards, which makes the collaboration structure concentrate around the adversary.
As presented above, the graph structures learned by SOP-CG can learn effective coordination pat- terns in Chase, which can be explained by the oracle collaboration strategy of human experts. demonstrates the ability of our approach to organizing coordination relations.
CONCLUSION
This paper introduces SOP-CG, novel multi-agent graph-based method that guarantees the polynomial-time greedy policy execution with expressive function representation of structured graph class. To enable end-to-end learning, SOP-CG introduces an imaginary agent to dynamically select the state-dependent graph and incorporates it into a unified Bellman optimality equation. We demonstrate that SOP-CG can learn interpretable graph topologies and outperform state-of-the-aar baselines on several challenging tasks. Although the graph class is exponentially large, we conduct two specific polynomial-time graph class instances to achieve impressive performance. Designing effective graph exploration methods to deal with larger graph classes will an interesting future direction.

---

Under review as a conference paper at ICLR 2022
ETHICS AND REPRODUCIBILITY STATEMENTS
The main contribution of our work locates on the research of a foundation theoretical problem in optimality theory and try to improve the problem with our method. Our work does have a bad social impact. The source code of our method for all the experiments is attached in supplementary material, and the settings and parameters for all models and algorithms mentioned in the experiment section please refer to Appendix
REFERENCES
Javier Alonso-Moo Mora, Stuart Baker, and Daniela Rus. Multi-robot formation control and object trans- port in dynamic environments via constrained optimization. The International Journal of Robotics Research, 36(9):1000-1022 2017.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1rXXiv1806..1222 2018.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991. PMLR, 2020.
Jacopo Castellini, Frans A Oliehock, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In AAMAS 2019: The 18th International Conference Autonomous Agents and MultiAgent Systems, pp. 1862-188 1864. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2019.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Hol- ger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv: 2014.
Paul Dagum and Michael Luby. Approximating probabilistic inference in bayesian belief networks is np-hane up-hard. Artificial intelligence, 60(1):141-153, 1993.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In International Conference on Machine Learning, pp. 1538-1546, 2019.
Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17:449-467, 1965.
Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. Distributed constraint optimization prob- lems and applications: survey. Journal of Artificial Intelligence Research, 61:623-698, 2018.
Jakob Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip HS Torr, Pushmeet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforcement learning. International conference on machine learning, pp. 1146-1 155. PMLR, 2017.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In NIPS, volume 1, pp. 1523-1530, 2001.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML, volume 2, pp. 227-234, Citeseer, 2002a.
Carlos Guestrin, Shobha Venkataraman, and Daphne Koller. Context-specific multiagent coordina- tion and planning with factored mdps. In AAAI/IAAI, pp. 253-259, 2002b.
Hado Hasselt. Double q-learning. Advances in neural information processing systems, 23:2613- 2010.
10

---

Under review as a conference paper at ICLR 2022
Jiechuan Jiang and Zongqing Lu. The emergence of individuality. In International Conference Machine Learning, pp. 4992-5001. PMLR, 2021.
Jelle Kok and Nikos Vlassis. Sparse cooperative q-learning. In Proceedings of the twenty-first international conference on Machine learning. pp. 61, 2004.
Jelle R Kok and Nikos Vlassis. Collaborative multiagent reinforcement learning by payoff propaga-
tion. Journal of Machine Learning Research, 111178991828, 2006.
Landon Kraemer and Bikramjjt Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
Victor Lesser, Charles L Ortiz Jr, and Milind Tambe. Distributed sensor networks: A multiagent perspective, volume Springer Science & Business Media, 2003.
Sheng Li, Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit coordination graphs for multi-agent reinforcement learning. arXiv preprint arXiv:2006./ 1438, 2020.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compeinn environments. Neural Information Processing Systems (NIPS), 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. Advances in Neural Information Processing Systems, pp. 761 1-6222, 2019.
Frans A Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Afshin OroojlooyJadid and Davood Hajinezhad. A review of cooperative multi-agent deep rein- forcement learning. arXiv preprint arXiv:1908.0300 2019.
James D Park and Adnan Darwiche. Complexity results and approximation strategies for map planations. Journal of Artificial Intelligence Research, 21:101-113, 2004.
Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Mor- gan Kaufmann, 1988.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, 2020a.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint (XXi::2003.08839 2020b.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philiph H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. CORR, abs/1102 04004, 2019.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when communicate at scale in multiagent cooperative and competitive tasks. arXiv preprint arXiv: / 812009755 2018.
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 Interna- tional Conference on Machine Learning, pp. 5887-5896, 2019.
Ruben Stranders, Alessandro Farinelli, Alex Rogers, and Nicholas R Jennings. Decentralised co- ordination of mobile sensors using the max-sum algorithm. Twenty- First International Joint Conference Artificial Intelligence, 2009.
11

---

Under review as a conference paper at ICLR 2022
Peter Sunehag, Guy Lever, Audrumas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. caoopsseconooottionn networks for cooperative multi-agent learning based team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgen Systems, pp. 2085-2087, 2018.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning. pp. 330-337, 1993.
Elise Van der Pol and Frans A Olichoek. Coordinated deep reinforcement learners for traffic light control. Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS 20/6),
2016.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yu Yang, and Chongjie Zhang. Qplex: Duplex ducling multi-agent q-learning. In International Conference on Learning Representations, 2021a.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Multi-agent reinforcement learning with emergent roles. In International Conference Machine Learning, 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.01553, 2020b.
Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decompos- able value functions via communication minimization. In International Conference on Learning Representations, 2020c.
Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang. Context- aware sparse deep coordination graphs. arXiv preprint 1eXiv:2006002880 2021b.
Yihan Wang, Beining Han, Tonghan Wang. Heng Dong. and Chongjie Zhang. Off-policy multi- agent decomposed policy gradients. arXiv preprint arXi::2007 2020d.
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforvement learning, arXiv preprint WxXv::901.09907. 2019.
Dayong Ye, Minjie Zhang, and Yun Yang. A multi-agent framework for packet routing in wireless sensor networks. Sensors, 10026-177744 2015.
Se-eun Yoon, Hyungseok Song, Kijung Shin, and Yung Yi. How much and when do we need higher- order information in hypergraphs? a study hyperedge prediction. In Proceedings of The Web Conference 2020, pp. 2627-26333 2020.
Chongjie Zhang and Victor Lesser. Coordinated multi-agent reinforcement learning in networked distributed pomdps. In Twenty-Fithh AAAI Conference on Artificial Intelligence, 2011.
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-agent systems, pp. 1101-1108, 2013.
12

---

Under review as a conference paper at ICLR 2022
A EXPERIMENTAL DETAILS OF THE MOTIVATING EXAMPLE
Algorithms. To get the correct result of DCOP, we use a brute force with complexity O[ while we choose Max-sum algorithm (has an alternative implementation called Max-plus) (Pearl 1988). which is commonly used by most of the coordination graph learning methods (Zhang & Lesser 2013 Böhmer et al. 2020; Wang et al. 2021b) test the accuracy and relative error. The details of the algorithm are presented below (Zhang & Lesser 2013).
Max-sum constructs bipartite graph 9m (Va. Vg.. Em, according the coordination graph (V, E). Each node v E V,, represents an agent who needs to do action selection, and each node u V. represents (hyper-Jedge function. Edges in &m connect with the corresponding agent nodes. Max-sum algorithm will do multi-round message passing on this graph. The number of iterations is usually set smaller than 10 in previous work, while we set 100 in this experiment.
Message passing on this bipartite graph starts with sending messages from node Va to node Vg:
Mo--u(as) = Σ mh-o((a) + Cou
(8)
hEF
where F, represents the node connected and Cou is the normalizing factor preventing the value of messages from growing arbitrarily large. The message from node u to v is:
(a) max au \ov
f(aw)+ + Σ manru(an)
(9)
NEV. V0
where Vn, is the set of nodes connected node a. {ax l VuJ. On \a, = {aalh E Vu Vu))), and ʃ represents the value function of the (hyper-)edge. After iterations of message passing, each agent v can find its optimal action by calculating a argmax,, ΣneF, Mi++o (av).
Test data. We take 1, 000 random seeds to test the problem. We fix the number of actions 3 and move the number of agents from 2 18. For each setting, generate fully connected graph with each value a uniformly random number in {, 1, along with a noise drawn from the normal distribution.
B COMPUTATIONS WITH CLASSES 9P AND 9H
Here present the details of algorithms we used select graph (1)) from the graph class G.
When g = Gr, pairwise grouping. In this case, n agents are pairwise matched by [n/2] edges. One agent will be isolated if an odd number. With such coordination graph, each agent coordinates with exactly one agent, except for the isolated one.
If node i is matched with node j. it will contribute qi+,j qi(T,, a,) + qo [T), az) + goy(Ta, Ty Qi, ag) to the total value when choosing action which only contains the single utility function and one pairwise function. Thus the pair (i.j) can contribute at most
max [g: (Tr, a.) (T(T), a,) + 4ig (T Tj a, a;)] G,.0,
(10)
to the joint value without effect the action selection of other agents.
Hence, construct undirected weighted graph G (V, Ew), where V is the vertex set, and
Ewr = { (1.) (.jj,((i))) = imax/q/(Ta) a..a,
(T) + qh (T 7, (s a,)))) Mi.5) e (11)
A matching on such graph is function mate(v) where mate(mate(()) most one satisfies that mate(v) = v. The weight of the matching is defined as Σ. w(v, mate(v)). Our goal is to find the maximum weighted matching this graph.
for all V with
13

---

Under review as a conference paper at ICLR 2022
This problem can be solved by the blossom algorithm (Edmonds) 1965) in (n time. The brief steps of this algorithm are to iteratively find augmentation paths on the graph and contract the odd- eycle, which is called blossom in this algorithm.
When 9 = GH hierarchical organization. In this case, the graph is an acyclic graph with n edges, and all agents form connected component. The distributed constraint optimization problem (DCOP) on such graph can always be solved in the polynomial time (Fioretto et al. 2018
Choosing the best graph G in GFr is non-trivial. Therefore, we present greedy algorithm to select the graph from the graph class. The high level idea is to add edges greedily until all agents are connected. At each iteration, we add an edge across two different connected components to the coordination graph, which optimizes the increment of the maximal joint value. For edge set E S &, we define the value of set f(E) to be the result of DCOP on graph (V, E). Initially we have E' an empty We do the iteration
times. In each iteration, find arg max EEE(EL(() is acyelic
e=
(EEU{e))
(12)
and add this edge the current graph, i.e., E t fef Once graph from Gn is selected, the joint action selection can be computed via dynamic programming.
Time complexity. We summarize the time complexity (in worst case) of each component in Ta- 2 For SOP-CG (G=), we use pruning techniques in our implementation, so the real-time cost of selecting graph G(O) is usually much smaller than the complexity reported Table The detailed training time of SOP-CG and DCG can be found in Appendix
Algorithm
Select graph G
Select actions on a given graph
SOP-CG (Gr)
( O A?) (heuristic)
(nnA22)
SOP-CG (9n)
(nnA2))
DCG
N/A
O(kn² 2 A?) (heuristic)
Table Time complexity of SOP-CG and DCG. the number of agents and U A1). For DCG, & is the number of iterations in max-sum.
C GRAPH RELABELING TECHNIQUE
As studied by Hasselt (010)), vanilla Q-Jearning already has a tendency to overestimate, since the TD target takes max operator over set of estimated action-values. Notice that our framework introduces an additional max operator over graphs in class G. which will probably induce extra upward bias. To attenuate this problem, of overestimation errors. In our implementation, we modify the vanilla TD loss defined in Eq. (7) to the following form:
graph relabeling technique to control the effects
(Veg max Q(T, a(T,a::G:0))
Leg (0)
E (T.a,1,7') D-
(13)
where Yeg is the one-step TD target defined in Section 4.2 and the current value no longer takes the graph which is stored in the replay buffer with this transition. As G the graph with largest estimated value, this loss achieves a soft constraint for the following target:
YG, Q(T, a; G: S Yeg
(14)
which helps our method avoid overestimation.
We conduct ablation studies on the tasks Pursuit, Chase and Postman to demonstrate the necessity of this component. The results illustrated in Figure 7 SOP-CG (GH) w/o graph relabeling is more likely to stick in suboptimal strategies and may even collapse on Pursuit. As analyzed before, these phenomenons due to the dramatic overestimation caused by the additional max operator graphs. By contrast, the performance of SOP-CG (g is significantly improved, highlighting the effectiveness of graph relabeling.
14

---

Under review as a conference paper at ICLR 2022
SOP-CG (Gr)
SOP-CG (Gr) w/o graph relabeling
Opti mal Return
Pursult
Chase
Postman
12.5
250
Text Test.euum
10.0
200
7.5
1.5
0
1.00
-5
1.0
2.5
0.5
2.0
3.0
[mill
[(ml)
Figure 7: Ablation studies about the graph relabeling technique.
D IMPLEMENTATION DETAILS AND EXPERIMENT SETTINGS
shared GRU (Cho et al. 2014) is used to process sequential inputs and then output the encoded observation history for each agent. following cully-connccted layer converts the observation his- tories to the individual utility function of each agent. The pairwise payoff function is computed by another multi-layer perceptron, which takes the concatenation of two agents' observation histories as input. Agents share parameters of the network for computing individual utility, and the parameters of the payoff network are also shared among different agent pairs.
All tasks in this paper use discount factor 0.99. We use e-greedy exploration, and anneals linearly from 1.0 to 0.05 over 50000 time-steps. We use an RMSProp optimizer with a learning rate of 5 x 10-3 to train our network. A first-in-firstouut (FIFO) replay buffer stores the experiences of at most 5000 episodes, and batch of 32 episodes are sampled from the buffer during the training phase. The target network is periodically updated every 200 episodes.
Our method and all the baselines involved this paper are implemented based on the open-sourced codebase PyMARL (Samvelyan et al., 2019), which ensures the fairness of comparison. For the baselines (VDN (Sunehag et al.J (2118). QMIX (Rashid et al.) 2020b). DCG (Böhmer et al.) (2020), CASEC (Wang al. ()2 we adopt the default hyperparameter settings provided by the authors. For evaluation, all learning curves in this paper are smoothed over 5 random seeds.
The experiments finished NVIDIA RTX 2080TI GPU. The training time of SOP-CG and DCG are listed in Table D SOP-CG is much faster than DCG.
Pursuit
Chase (5M timesteps)
Postman (3M timesteps)
(3M timesteps)
Environmental time cost
6h
32h
17h
SOP-CG (Gp)
19h
46h
31h
SOP-CG (GH)
24h
48h
33h
DCG
25h
62h
48h
Table 3: Training time (hours) of SOP-CG and DCG. Environmental time cost denotes the total time taken by the environment simulator and the training of the adversaries.
E STARCRAFT II MICROMANAGEMENT BENCHMARK
In this section, we compare SOP-CG against DCG Böhmer et al. 2020) and CASEC (Wang et al. 2021b) on StarCraft II micromanagement benchmark (Sanvelyan al. 2019). The pairwise payoff function has A output head, where A = I A'I. DCG and CASEC adopt different techniques (e.g. low-rank approximation or learning action representations) to improve the learning efficiency of the payoff functions in environments with large action space. These techniques can also be applied to our algorithm. For fair evaluation, we test the vanilla versions of the algorithms without applying extra techniques on payoff networks. The results are shown in Fig. SOP-CG outperforms DCG and CASEC on of the scenarios and achieves comparable performance on the other scenarios. coordination graphs is large enough to
This finding indicates that the class of polynomial-tim press coordinated policies in these tasks, and the accurate action selection further helps SOP-CG achieve higher peak performance than DCG and CASEC on the four maps.
15

---

Under review as a conference paper at ICLR 2022
SOP-CG (G+)
SOP-CG (Gr)
DCG
CASEC
5m,
10m, vs
100
Text Min %
50
50
25
25
0.5
1.0
2.0
0.0
1.0
1,5
0.5
1.5
2.0
(mil)
T Imil
1c3s5z
3x52 vs, 3563
MMM2
100
100
100
75
75
25
0
(mil)
mml
Figure 8: Learning curves on StarCraft micromanagement tasks.
SOP-CG (6)
SOP-CG (Qu)
DCG
CASEC
NDQ
1c100 vs 1r
12z 2ul
30
50
220
10
mm0
(m8)
Figure 9: Learning curves on lo10b_vs_Il and 12z_vs_ 2ull.
F SC2 TASKS RESTRICTED OBSERVABILITY
In poordination-graph--aee -base methods, agents communicate to optimize joint action selection. As an alternative way, previous work studies multi-agent communication learning message embedding (inghh et al., 2018; Das et al. 2019; Wang et al.] 2020c). We compare our algorithm against the state-of-the-ar communication learning method NDQ (Wang et al., (020c) on StarCraft II tasks: 1o10b. .vs.lr 1r and 12z.vs 2ul. These tasks are modified from the challenging maps introduced by the NDQ paper. The sight range of agents reduced from 2, which enforces the agents to coordinate their actions by communication. To enable effective communication, we further augment the observation of each agent by its position on the map.
lol0b_vs_Ir Banelings spawn randomly on a map full of cliffs and need to kill an enemy Roach. An allied Overseer detects the Roach and they spawn at the same random point. Therefore, the Banelings can get the position the Roach from the allied Overseer.
12z_vs_2ul: 12 Zealots try to kill 2 powerful Ultralisk. All units spawn randomly on the map. The agents need to communicate the positions enemies well coordinate the attack timing to reach high win rate.
The learning curves are shown in Figure On the map lo10b vs Ir, simple but effective com- munication strategy is to the Overseer coordinate with all allied Banelings to guide their moving direction. We observe that it's not hard for NDQ to learn this mechanism and NDQ has similar performance as SOP-CG (GH) on this map. However, the performance of NDQ is worse than the methods based on coordination graphs on 12z_vs_20 22ll. As all units spawn randomly agents need to learn more complex coordinated strategies to kill both of the enemies. This finding suggests that directly coordinating actions based on coordination graphs may be more efficient than learning encoded messages. Notably, SOP-CG (G also outperforms DCG and CASEC on both tasks, highlighting the effectiveness of our method in complex scenarios.
this map, the
16

---

Under review as a conference paper at ICLR 2022
G METRICS OF TASK COMPLEXITY
To illustrate the algorithmic properties of SOP-CG, we propose two measures of task complexity and conduct analysis between SOP-CG and DCG according to these measures. Furthermore, we design new didactic example to empirically demonstrate our theoretical implications answering the following questions: when does SOP-CG work better and when does DCG work better?
We will introduce the two measures of task complexity as follows:
Problem size in general Dec-POMDDs. Solving a general single-agent MDP with state space S and action space A requires the polynomial-time complexity of [S] x |A| (i.e., its problem size), as shown in Sutton et al. (Sutton & Barto 2018). In MARL tasks, A = A,, whose problem size extended [S] x |A,"", exponential of the number of agents and the size of local action space, respectively. To analyze the effect of problem size on SOP-CG and CG, we find that the time complexity of exact greedy action selection (solving DCOPs) is exponential-time for DCG (i.e., with complete graph), and which is polynomial-timee complexity for SOP-CG (i.e., with a class of polynomial-time graphs).
Structural complexity of coordination within agents. This measure used to represent how much function expressiveness of coordination graph (i.e., which types of graph) is needed to solve a specific task. Note that the function capacity of DCG (line or star), SOP-CG, and DCG (complete graph) forms a hierarchy. i.e., QDCG (linc or star) C @sOP-CG C QDeG (cumplete graph), where Q indicates the class of value function which can be represented by each algorithm. Thus, formally design the structural complexity of coordination as the necessary and sufficient function capacity induced by each specific task. Along with this structural complexity increases, larger function capacity of algorithms is required. Moreover, we hypothesize that in the realistic tasks, the coordination structure is sparse (Kok & Vlassis 2004 Zhang & Lesser 2013) and the function class of SOP-CG would be sufficient for an exiensive set of situations.
Using these two measures of task complexity, we compare SOP-CG with DCG in four cases that either these complexities are high low.
Both two complexities are low. Both SOP-CG and DCG (complete graph) can easily address this case.
The problem size is large but the structural complexity is relatively low, which is a common case in real-worid tasks (Kok & Vlassis 2004] Zhang & Lesser (013). SOP- CG can significantly outperform DCG (complete graph) because of efficient computation of exact greedy action selection without sacrificing its expressiveness in this case. The major strength of SOP-CG is its ability to model the value function using self-organized polynomial-time coordination graphs. Solving the DCOPs induced by SOP-CG is com- putationally efficient but which is expensive for DCG (complete graph) and the approxi- mation of its induced DCOPs. We find that SOP-CG is not sensitive to the problem size, such as the number of agents and individual actions. In comparison, it is NP-hard to find a constant-ratio approximation of the DCOPs induced by complete graphs (i.e., the default implementation of DCG).
The problem size is small but the structural complexity is very high. In this case, DCG (complete graph) may outperform SOP-CG as it is possible for DCG to compute nearly optimal joint action selection. However, as we hypothesized that this case may not usual in the realistic tasks since multi-agent systems are often large and the sparse coordination structure commonly exists in such systems.
Both two complexities are high. SOP-CG and DCG (complete graph) may perform com- parably in this case because they both introduce some approximation in learning. SOP- CG introduces approximation in value function expressiveness while DCG has inaccurate greedy action selection. This case is super hard and would be studied as an important future direction of coordination graph methods.
To investigate the metrics of task complexity and our performance relative to the metrics, we design series of tasks. The tasks consist x k agents separated into groups with each group k agents.
17

---

Under review as a conference paper at ICLR 2022
SOP-CG (Gx)
DCG
DCG (line)
DCG (star)
m=1,
m=1,
m=1,
bormal
bor Hormul
100
11
2. km2
m= k-3
m- 2. kw4
m- kw5
Normazadd D4tum.
3.0
sermatodddo teaum.
1181 3, k-2
16
10
3, k-3
m-
m-3,
Romnsere Puturm
Nomalzzd
5 C
16
76
16)
1.00
11
m=4,k K-2
m-4. k-3
K-4
m-4, km5
2.7
2.0
Wrnwitedd Rib
00
T1k1
[61
14
m. k-2
m-5. k-3
m- km4
m-5, k-5
10
20
10
20
30
30
25 35
Tiki
14
Figure 10: Learning curves on series of toy games.
Each agent has to choose an action from the action space A, and one group wins if and only if all its members perform & distinct actions. The global reward is the proportion of winning groups
In this task the number of agents in one group measures the representation complexity that each agent has to cooperate with other agents within the same group, while the number of groups indicates the scale of the problem. When the size of group grows, the coordination relationship becomes dense. If the number of groups increases and the size of group is fixed, the coordination complexity of the task will remain the same, but the scale of the task can be larger.
Results illustrated in Figure show that our method can work very well when the group size of not so large (i.e., & < 3), being less sensitive to the number of groups. While DCG (line) or DCG (star) cannot work when the total number of agents to the fact that the representation capacity of them is restricted below our method. In contrast, the performance of our method decreases when the group size grows larger, while DCG performs better when & grows and m remains small. The result also suggests that when keeps small, both SOP-CG and DCG have enough representation capacity to solve the problem. As the scale of the problem grows, the complexity of solving DCOPs of DCG becomes higher, so SOP-CG can significantly outperform DCG.
k exceeds small threshold, which corresponds
18

---

Under review as a conference paper at ICLR 2022
H SOME DETAIL DISCUSSIONS ABOUT TRADE-OFF IN SOP-CG
H.1 CONNECTION TO A RECENT WORK ON HYPER-GRAPHH
We note that recent work on the expressiveness of hyper-graphs Yoon et al. 2020 is relevant to our work. The connections (i.e., the differences and relevance) between Yoon et al. (020)) and our paper summarized as follows:
Different metric of expressiveness. Yoon et al. (2020) investigates the functionality of graph expressiveness in terms of the order of hyper-edges. By contrast, our paper focuses on the expressiveness of different graph topologies.
Similar motivation. Both Yoon et al. and our paper aim study the trade-off between the graph expressiveness and the complexity of solving downstream tasks. In our paper, the downstream task specifically refer the DCOPs induced by graph-based value factoriza-
tion.
Different work flow and contributions. Yoon et al. (2020) establish systematic periment study to provide an empirical guideline on how to trade off between the graph expressiveness and downstream costs. In comparison, our work proposes an algorithm to break this trade-off for improving MARL performance. Our algorithm is able to improve the function expressiveness without largely increasing the time complexity of downstream DCOPs.
Despite the expressiveness metric being different, several conclusions reached by Yoon et al. (2020)
can be observed in our experiments. More specifically, the key findings of Yoon et al. (2020)
(namely, three points, i.e, Diminishing returns, Troubleshooter, and Irreducibility) correspond to the following observations in our paper:
Diminishing returns. When the task coordination structure is simple, concise graph topology (e.g., pairwise matching) can achieve comparable performance with topologies using larger edge sets. As presented in Figure SOP-CG (Gp) performs better than SOP- CG (Grr) and DCG in Pursuit, since pairwise matching is sufficient to express the underly- ing coordination relations in this task. (Recall that GP uses pairwise matching and GH uses tree-based topology.)
Troubleshooter and Irreducibility. When the task requires complicated coordination structure, the graph topology needs to have higher function expressiveness. This finding can also be seen in Figure SOP-CG (Gn) significantly outperforms SOP-CG (Gr) in Chase where pairwise matching cannot express the underlying coordination relations.
H.2 POSITION OF SOP-CG
The trade-off line from DCG with fixed polynomial graphs (i.e., line or star) to SOP-CG to DCG with complete graph (i.e,, the default configuration) is similar to the MON-QMIX-QTRAN methods, though SOP-CG lies in the coordination graph line of MARL (rather than the value factorization line). In this analogy hicrarchy. SOP-CG corresponds to QMIX where SOP-CG has much larger function expressiveness than DCG with line or star graph (which corresponds to VDN), and can derive the exact greedy action selection compared to DCG (complete graph) (which corresponds to QTRAN). Note that different from VDN which has achieved excellent performance on StarCraft II benchmark (Samvelyan et al. 2019). DCG with line star graph performs poorly due its limited function capacity, which is mentioned in its original paper and in our evaluation (Appendix G). Sim- ilar to discussions in Mahajan al. 2019) and Wang al. (2021a) that QTRAN may suffer from its approximate greedy action selection, DCG may also suffer non-optimal action selection, while SOP-CG also considers the advantage of exact greedy selection (i.e., the property of polynomial- time graph proved by |Fireetoo et al. (2018) and empirically achieves significant outperformance than DCG (Figure and Appendix and In comparison of function expressiveness, DCG (com- plete graph) achieves larger value function capacity than SOP-CG, but we hypothesize that in the realistic tasks, the coordination structure could be sparse (Kok & Vlassis 2004, Zhang & Lesser 2013) and the function class of SOP-CG will be sufficient address large suite of challenging tasks, e.g., StarCraft II, in Appendix E and F Therefore, from the perspective of "VDN -MIX- QTRAN" line in coordination graphs, SOP-CG has a clear and important position in the literature.
19

---

Under review as a conference paper at ICLR 2022
I COMMUNICATION MECHANISM OF SOP-CG
SOP-CG runs in the paradigm of centralized training and decentralized execution with communi- cation. We will discuss the communication mechanism in SOP-CG and its advantage comparing to the CTDE works as follows.
The communication mechanism of SOP-CG is consistent with DCG (Böhmer al. 2020) and CASEC (Wang et al., 2021b). Two metrics are commonly used to measure the cost of multi-agent communication models: communication bandwidth and frequency. In SOP-CG, agents communi- cate the q-values to jointly decide the graph structure and induced actions, while DCG and CASEC use the message passing algorithms to optimize joint actions. This will require limited communica- tion bandwidth as only few real numbers are passed through each channel. We could further reduce the communication cost of SOP-CG by reducing the frequency of graph selection (i.e., changing the coordination graph via fixed length of timesteps) if we assume the temporal consistency of coor- dination graph of the multi-agent system. This will be an interesting future direction for dynamic coordination graph in MARL.
Compared with the fully decentralized execution methods, the most important characteristic of co- ordination graph is the direct modeling of interactions between agent actions (i.e. pairwise payoff functions). The DCG paper (Böhmer et al.) 2020) conducts comprehensive discussions to demon- strate the necessity of this design tasks with relative overgeneralization pathology. Furthermore, it provides a straightforward objective for agent communication (i.e. maximizing the sum of individ- ual utilities and pairwise payoffs), and the induced communication will promote agent cooperation especially in environments with partial observability (Wang et al., 2020c).
20


Reviews:
[{"review_id": "qfZH63yEJkY", "reviewer": "Reviewer_xmMA", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "**Strengths**\n1. To determine state-dependent coordination graph is interesting.\n2. Incorporating graph selection into TD learning is desirable. \n\n**Concerns/Questions**\n1. State-dependent coordination graph needs to be determined at each time step in both training and execution,  which means SOP-CG is a centralized method. Thus, a baseline of single-agent RL is desired for comparison in experiments. \n2. It is not clear how $q_i$ and $q_{ij}$ are learned. Are they parameter-sharing for agents?\n3. The operation $\\arg\\max$ in equation 4 takes $O(n^3)$ for $\\mathcal{G}_P $. It may be too costly for both training and execution. One evidence is that each run of SOP-CG  takes up to 2.5 days in these simple experimental tasks. \n4. Since both DCG and CASEC include SMAC experiments, it would be better to also include it here to show the performance of SOP-CG in complex environments. \n\nIn summary, it is currently hard to see the benefit of determining the coordination graph in a centralized way. Moreover, the proposed method is not verified in complex environments. \n\n\n\n**Minor Comments**\n1. As claimed in Appendix C, a graph relabeling technique is used to solve the extra overestimation error introduced by additional max operator over graphs.  However, this paper is currently missing an ablation to validate this point.\n\n\n\n", "summary_of_the_paper": "This paper proposes an extension of deep coordination graph, called Self-Organized Polynomial-time Coordination Graphs (SOP-CG). Instead of pre-specified graph topology used in DCG, their method allows graph topology to be state-dependent, which is achieved by a coordinator agent, and the optimization of this agent is incorporated in a modified temporal difference learning paradigm. Two pre-specified undirected acyclic graph classes are used to ensure polynomial-time graph selection and accurate greedy action selection. The result on sensor network, grid world and MPE shows that such a trade-off between the representational capacity of graph topology and the computational accuracy can improve the performance of MARL and learn meaningful graph topology.", "summary_of_the_review": "State-dependent coordination graph is important. However, the paper currently has several weaknesses as mentioned above. It seems clearly below the bar of ICLR.  ", "strength_and_weaknesses": "", "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": "LTVTWMDEFp", "reviewer": "Reviewer_Jx51", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The main strength of the paper lies in its algorithm being of polynomial-time nature, and that characteristic needs much more emphasis in both text and figures. Does SOP-CG reach peak performance faster? Is its peak performance higher? could be some guideline questions when structuring the paper contents around the polynomial-time algorithm.\n\nQ1. I would appreciate if the authors would discuss the relevance of a WWW 2020 paper: How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction by Yoon et al. I think it could also provide some useful insights as to how high of an order the hyperedges need to be, to save some function expressiveness (i.e., representational capacity) at the cost of time complexity.\n\nQ2. How did the authors go about designing the didactic examples? How simple of a task is the \"sweet spot\" for SOP-CG? As task complexity is altered, when does SOP-CG begin losing its simplicity advantage? When do other models take over? Which measures would you say most greatly determine the task complexity, which in turn, compromises SOP-CG's performance?\n\nQ3. How would you position SOP-CG in the MARL research? Since the graph selector agent is there at both training at execution times, would SOP-CG be a centralized training centralized execution work? If it is, comparison against CTDE works such as VDN and QMIX would not be fair. It is as though a \"free\" centralized coordinator is helping out the SOP-CG agents at execution time as well. It may be a good idea to compare against some communication-enabled MARL works.\n\nQ4. Despite starting out strong, the paper seems to fall off rather dramatically, especially when it comes to the didactic nature of the examples, tied in with the page 6 remark that SOP-CG would perform best (given its tradeoff) in tasks where the restricted graph classes are enough to express the coordination dependencies. This remark really sounds like going back on the VDN-QMIX-QTRAN line of research, whose focus was about covering a richer class of joint action-value functions. Going back on that trend now only to pursue the polynomial-time nature of the running algorithm would in my opinion require far more diverse evaluation examples, backed by a stronger motivation highlighting real-world threats of all the other MARL algorithms taking longer than polynomial time. As is, SOP-CG does not contend amazingly against other MARL algorithms that chose the \"NP-hard? Curse of dimensionality? Fine. We'll approximate, approximate, approximate.\" path rather than the \"Polynomial time is our topmost priority; function expressiveness can wait.\" path. That leads me back to the question of why pursue polynomial time at the cost of losing both the function expressiveness and the peak performance in the apparent trilemma.", "summary_of_the_paper": "Authors present an imaginary coordinator agent that executes graph selection as its action based on possible combinations of pairwise edges and the underlying individual and pairwise utilities. The results show some effectiveness of the presented method, SOP-CG, in simple examples.", "summary_of_the_review": "My biggest concern is the \"imaginary\" agent freely collecting information, making decisions, and delivering those decisions to all the agents at both the training and execution times. Comparison against the chosen baselines is not fair, even when the chosen evaluation task is a simple enough one, in which SOP-CG's limited representational capacity would not appear that pronounced.", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "95O6OnyD2W6", "reviewer": "Reviewer_h3B4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The detailed comments regarding the quality of this paper are listed as follows:\n1. In the Introduction section, one of the biggest concerns is that this paper cannot tell the novelty of the proposed SOP-CG compared with the methods in peer researches. Besides, the illustration of experimental results is not convincible to prove the advantages of the proposed SOP-CG in this section.\n2. Somewhere in the paper, the authors' presentation is unclear and is worth being improved. For example, in the Background section, the meanings of some symbols in the model are not clear. Furthermore, the authors should give the purposes of introducing formula (2).\n3. What is the intuition behind the process of investigating polynomial-time coordination graphs in the Section 4? Or, is there any intuition at all? How did you come up with that idea? Have you borrowed this idea from somewhere else? It is better to give a detailed explanation about polynomial-time coordination graphs.\n4. In page 6, the authors proposed Self-Organized Polynomial-Time Coordination Graphs. Whatever techniques are used in the manuscript, there is a need to tabulate computational cost of the proposed algorithm in this paper. \n5. In the Experiments Sections, the authors claimed that the graph structures learned by SOP-CG definitely match the ground-truth demands for effective collaboration. However, it is not clear to us why the method can be used in demonstrating the ability of the proposed approach to organizing coordination relations. Therefore, the authors should provide a detailed explanation about the above issue. \n", "summary_of_the_paper": "This paper introduced a novel method called Self-Organized Polynomial-time Coordination Graphs (SOP-CG), aiming to handle the decentralized constraint optimization problem (DCOP). This paper is well organized and the experiments are explicitly presented. Therefore, I think the work of this paper is very interesting and the contributions are sufficient. \n", "summary_of_the_review": "The work presented is indeed interesting and relevant to the real scenarios. I recommend that this paper could be accepted.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Description of paper content:

The paper studies the problem of achieving coordination among a group of agents in a cooperative, multi-agent task. Coordination graphs reduce the computational complexity of this problem by reducing the joint value function to a sum of local value functions depending on only subsets of agents. In particular, the Q-function of the entire system is “expanded” up to second-order in agent interactions: Q = \sum_{i \in [n]} q_i + \sum_{(i,j) \in G} q_{ij}, where the q_i is function of the i-th agent’s history and current action, and q_{ij} is a function of two agents’ histories and current actions. As G does not include higher-order (third and above) terms, the algorithm does not have exponential dependence on the number of agents. If G includes only a subset of pairs of agents, then the computational complexity is reduced to less than quadratic. Since the coordination problem is cooperative, the authors propose a meta-agent (“coordinator”) that selects the graph G in a dynamic (state-by-state) fashion in order to maximize return. The optimization problems of the meta-agent and the sub-agents are performed by deep Q-learning.

Summary of paper discussion:

The critical comment made by one reviewer was: “Going back on that trend now only to pursue the polynomial-time nature of the running algorithm would in my opinion require far more diverse evaluation examples, backed by a stronger motivation highlighting real-world threats of all the other MARL algorithms taking longer than polynomial time. As is, SOP-CG does not contend amazingly against other MARL algorithms that chose the "NP-hard? Curse of dimensionality? Fine. We'll approximate, approximate, approximate." path rather than the "Polynomial time is our topmost priority; function expressiveness can wait." path. That leads me back to the question of why pursue polynomial time at the cost of losing both the function expressiveness and the peak performance….”

Comments from Area Chair:

Looking at the experiments, the number of agents in the empirical problems is not large. For example, there are 15 agents in "Sensor." Any focus on computational complexity at this scale is hard to justify, especially with algorithms that are approximate. It seems favorable at this small scale to use function approximators that can take in all the agents' histories and actions. This obvious baseline is not included in comparisons. It is hard to justify inclusion of this paper in the conference.
Decision: Reject