PCRL: Priority Convention Reinforcement Learning for Microscopically Sequencable Multi-agent Problems
Authors: Xing Zhou
Hao Gao
Xin Xu
Xinglong Zhang
Hongda Jia
Dongzi Wang
Venue: NeurIPS 2022 Submitted (2022)
Keywords: reinforcement learning
social convention
priority
large discrete action space
multi-agent
cooperation

Abstract: Reinforcement learning (RL) has played an important role in tackling the decision problems emerging from agent fields. However, RL still has challenges in tackling multi-agent large-discrete-action-space (LDAS) problems, possibly resulting from large agent numbers. At each decision step, a multi-agent LDAS problem is often faced with an unaffordable number of candidate actions. Existing work has mainly tackled these challenges utilizing indirect approaches such as continuation relaxation and sub-sampling, which may lack solution quality guarantees from continuation to discretization. In this work, we propose to embed agreed priority conventions into reinforcement learning (PCRL) to directly tackle the microscopically sequenceable multi-agent LDAS problems. Priority conventions include position-based agent priority to break symmetries and prescribed action priority to break ties. In a microscopically sequenceable multi-agent problem, the centralized planner, at each decision step of the whole system, generates an action vector (each component of the vector is for an agent and is generated in a micro-step) by considering the conventions. The action vector is generated sequentially when microscopically viewed, and such generation will not miss the optimal action vector, and can help RL's exploitation around the lexicographic-smallest optimal action vector. Proper learning schemes and action-selection schemes have been designed to make the embedding reality. The effectiveness and superiority of PCRL have been validated by experiments on multi-agent applications, including the multi-agent complete coverage planning application (involving up to $4^{18}>6.8\times 10^{10}$ candidate actions at each decision step) and the cooperative pong game (state-based and pixel-based, respectively), showing PCRL's LDAS dealing ability and high optimality-finding ability than the joint-action RL methods and heuristic algorithms. 

PCRL: Reinforcement Learning Based on Priority Conventions for Microscopically Sequenceable Multi-agent Problems
Anonymous Author(s)
Affiliation
Address
email
Abstract
Reinforcement learning (RL) has played an important role in tackling the decision problems emerging from agent fields. However, RI. still challenges tack- ling multi-agent page-discrete-action--pee
(LDAS) problems, possibly resulting from large agent numbers. At each decision step, a multi-agent LDAS problem is often faced with unaffordable number of candidate actions. Existing work has mainly tackled these challenges utilizing indirect approaches such as contin- uation relaxation and sub-sampling, which may lack solution quality guarantees from continuation to discretization. In this work, we propose to embed agreed priority conventions into reinforcement learning (PCRL) to directly tackle the microscopically sequenceable multi-agent LDAS problems. Priority conventions include position-based agent priority break symmetries and prescribed action priority to break ties. a microscopically sequenceable multi-agent problem, the centralized planner, at each decision step of the whole system, generates action vector (each component the vector for an agent and generated in a micro-step) by considering the conventions. The action vector generated sequen- tially when microscopically viewed, and such generation will not miss the optimal action vector, and can help RL's exploitation around the lexicographic-smalle optimal action vector. Proper learning schemes and action-selection schemes have been designed to make the embedding reality. The effectiveness and superiority of PCRL have been validated by experiments on multi-agent applications, in- cluding the multi-agent complete coverage planning application (involving up 418 > 6.8 10'0 candidate actions at each decision step) and the cooperative pong game istate-based and pixel-based, respectively), showing PCRL's LDAS dealing ability and high optimality- ability than the joint-action RL methods and heuristic algorithms.
10
12
14
15
16
18
19
20
21
22
23
24
25
Introduction
26
Backgrounds Multi-agent systems have been applied to various civil (see Fig, military and entertainment applications 21] With the applications becoming broader and deeper, the agent number in multi-agent system has become larger and larger 4. which results in the large discrete action space (LDAS) problem. multi-agent problem with even a dozen of agents is hard to be solved by reinforcement learning (RL) for its explosive joint-action combinations [6]
28
30
31
32 To tackle the multi agent LDAS problems, some researchers resorted independent reinforcement learning regardless of other agents, but that may form loose cooperation and yield unstable or sub- optimal solutions; some researchers resorted to distributed reinforcement learning and communication to cooperate, but that lacks global knowledge and is hard to design cooperation mechanisms 7
34
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

50 Motivations Some multi-agent problems are microscopically sequenceable, i.e., an optimal joint drt -R
Pp-
64)
Figure 1: Examples of microscopically sequenceable multi-agen applications: (a)~(()) for multi-agent complete coverage path planning (CCPP), where the cleaning agents cooperate visit the shaded cells in the fewest steps (min-max); and (d) for cooperative pong (CP). (a) smaller-scale situation needs least steps for the two-agent system to cover uncovered cells. The action vectors (i.c., joint-actions) (left,up) and (ep,left) for Ri, Rs will be tie optimal at current state, but (up,left) is the smallest lexicographic optimal action vector according to our priority conventions. (b) The priorities (can be -laiive-position determined) for the agents from high low, at this state, are Ra < R2 R: R3. The state representation includes map state and agent state, and can be "101011 100010100020" where the '2' means 2 agents. (c) At this decision step, the system has |= > 6.8 x 10tH fcasible action vectors ([AA is the action set size for one agent and N is the number of agents), where the solid and dashed arrows are two tic optimal action vectors among many others. The PCRL will learn to select specific optimal action vector regarding priority conventions. (d) Cooperative Pong (detailed descriptions see the experiment section). CP can be established microscopically sequenceable problem.
36 many other researchers 8 9 turned to centralized RL for high performance. For centralized RL
37 method, a trivial joint-action representation (Fig. a)) can be applied to a small-scale multi-agent system. However, when the agent number increases
dozen, it becomes unaffordable because the 39 action space is exponential to the number of agents (see Fig. [C)~())). Previous centralized RL (8) has tried relaxing large discrete action space to continuous action space and generating few discrete
41 samples near the optimal continuous action vector to find the locally optimal discrete action vector. Nevertheless, this subspace may miss the optimal discrete action vector thus leading to sub-optimal; Moreover, the relaxing methods lack solution quality guarantees from continuation to discretization.
43
44 Therefore, it remains challenging for centralized RL to directly, effectively and efficiently tackle the multi-agent LDAS problems, difficult in representing the actions and finding the optimal action from -0 more candidate action vectors. Moreover, multi-agent LDAS problem often has many tie
45
46
47 optimal actions; see Fig. for an example. With multiple ties, RL for LDAS also difficult train because multiple metrrm-mximum peak landscapes may impact the convergence and exploitation of RL, so new action selection and training schemes are required.
49
51 action can be selected out one component by one component in micro-steps according to the conven-
52 tions, besides of being selected out simultaneously, i.e., the "microscopically sequenceable" defined in
53 RL language is that the joint action x (s) (01. 42 .... an) where each component can be produced
54 as 01 = n (s). 02 Tī [a]]),, a3 (s|o2)) ... and π, functions are related. For example, in
55 Fig. [b). the planner (can be set to the smallest id agent Ri, without loss of generalization) selects action for R4, say "right"; then, the planner selects the action for R2 by referring to Ra "right", and selects out "up": Then selects out R1 to "up" and R3 to "left". After the planner decides the action
56
57
58 for each agent, the planner sends the action to corresponding agents and these agents simultancously exccute the joint action.
80 The decision flow at a decision step has been shown in Fig, 2[c) and can be expressed by natural language (formal description in later paragraphs) order of agents. (2yThe planner decides one action (from A) for the highest priority agent that the planner believes to produce the largest Q value for the whole system, with the following agents fully supporting the highest priority agent. And if the first prioritized agent has tie actions, the action priority will be obeyed. (3) The planner refers to the first prioritized agent's 's action decision and then decides the action for the second prioritized agent, also aiming for the largest Q value for the whole system. The procedure continues until the last agents.
61
follows: (1) The planner makes clear the
62
63
64
86

---

Moce
la for lightst priatly spess siually pruied, culll ias Mouura (930
Delivee
Endrormet
(iets Bixarr, Dans
Nanwork
Flaacr
Genten
MAY
BM
BM
ttt auderal pitice aottr
MAP State
AP, AAg:Art
Agrnbs
Agands
Decidion
stpp
lopa
arrniretionpens 0J
The diagram explanation of methods. (a) trivial joint-action RL for multi-agent LDAS problems, the length of Q will be | (b) macroscopic view of PCRL. The planner maps the current state (including map state agent state)
Figure 2:
optimal action vector whose first component for the highest priority agent, etc. (c) microscopic view PCRL: at this decision step (c.g., Decision step t), the planner outputs in micro-steps the best action for the highest priority agent and then sequentially for other agents. The length of Q; is [A].
Priority conventions The agreed priority conventions for specific multi-agent problem are pre- 69 scribed by humans before the learning starts, and can be problem-specific designed. The priority conventions usually consist of (1) Agent priority convention: This is for determining the order 71 of agents to decide action and breaking symmetries: Dynamically, at each decision step of the centralized system, the agents' priorities are determined by current states, say, the relative positions 73 of agents. For example, in Fig. [c), the agents' priorities can be determined from left to right and the priorities (deciding order) of agents 75 x < means v has a higher priority than y. If the priority is not position based but ID based, then the state space will have many mirror states. (2) Agent ID convention: This is for coinciding agents and breaking symmetries. Statically assign each agent a unique ID before learning to identify itself from others. When least two agents coincide in the same position during the application, the smaller id agent has a higher priority.
upper to lower position,
R1 < Rg... K R16- Here,
78
77
78
79
(3) Action priority convention: This is for breaking ties 80 of equally optimal actions. The actions of an agent have prescribed priority, say, up action -leftt <right action, to break action ties if two actions both will bring about optimality. 82 and to converge to one minimum lexicographic action vector. Hereafter, we define that two action vector - 3 (or called "ä is lexicographic smaller than 3") if and only 3i [1, a < 3, and Vj E [1, 1], 0j- By.
81 action <down
83
85
The contribution of this paper lies in (1) Priority conventions and proofs: this paper proposes the concept of "microscopically sequenceable" to tackle LDAS multi-agent problems without missing the optimality, and can help exploitation around the lexicographic-smalle schemes: it proposes new learning schemes that fully exploit the agreed conventions, such as auxiliary equality constraint, and neural network action selection schemes for PCRL. (3) Proof-of-concept practices: applying PCRL. to tackle seemingly different problems, including 10 magnitude LDAS multi-agent path planning problems and the pixel cooperative task, and achieves 20% fewer steps and competitive performance.
86
87
optimal action vector. (2) New
88
89
90
91
2
Related Work
Nowadays, deep reinforcement learning has been successful in large state problems [5] 10) However, 95 is still very challenging to deal with the LDAS problems, especially in the action representation and selection.
97
2.1 Action representation
For the action representation, previous work has followed several lines to circumvent the large- 98
39
discrete-action-spaaee obstructions:
100
One line is to parameterize actions into continuous spaces and then to find discrete actions near the optimal continuous action [ because continuous actions differentiable. For example, [8]
3

---

102
exploited the Ehearest-neighheer to find the optimal policy X (s) ~
arg max
Q(s, a) in
aEtops(le-dlp)
discrete subspace near the optimal continuous actions à. It has been validated in discrete cartpole problems, recommending systems and multi-agent systems. One step further, work [12] exploitedly utilized the action space structure and without assuming the structure is provided a priori. This line will likely miss the optimal discrete solutions for inappropriate continuation and will lead to suboptimality. Also, lacks quality guarantee from continuation to discretization, which also has
104
105
106
107
108
been encountered and studied in the randomized rounding theory of integer programming [33]
Another line is to factor eliminate action spaces [64 using binary coding and coarse coding to eliminate actions that are not optimal with high probability. However, the elimination probability is hard model and eliminations are not always possible. Some researchers employed new factor and combination methods [0] for action representation and selection, when the problem satisfies Individual-Global Maximization (IGM) Constraint or monotonic properties.
110
112
113
114
2.2
Action selection
115
Action selection usually has deep entanglement with action representation.
21223 uses DQN for
116
action selection and has achieved success in Atari games and human-level control. 24 applied recurrent neural network (RNN) to select actions for POMDP. [25] used bidirectional RNN to represent the actions and select actions, successfully dealing with the continuous
117
118
and have achieved success in SC2 problem and other problems. Some work resorted to social conventions for selecting actions but not for I.DAS problems, for example, 26 27 And some work relied on sophisticated communications for exchanging selected action 28 30 which may be vulnerable to be impacted by unstable communication practical cooperation/ccorrdiattoo.
120
122
123
Our way of action selection resembles Stackelberg model and the sequence-to-seqeene paradigm (for example image-to-caption (3I) 32 also proposed seq-to-seq and on-policy policy gradient
124
125
to tackle LDAS problems, along with others (33 but we offer large agent number off- off-policy and
126
optimality- pressrrvd one. Meanfield reinforcement learning 4 also has LDAS dealing ability. It
127
iteratively learns each agent's 's best response to the mean effect from its neighbors and is proved to
128
converge to Nash Q-value. However, the Nash Q-value not always the global optimal value in scenarios like the prisoner's dilemma.
3
Methodology
130
131
This section introduces the basics of PCRL, then the mathematics and details of how to learn the agreed priority conventions in PCRL.
132
PCRL algorithm Our concern problems are markovian when macroscopically viewed and can be established as a classic MDP M = (S, A, P, R, 7), where the letters are as usually defined while A A where N is the agent number and A is the action set of agent 1 (the studied agents homogeneous and the action set of each agent is the same as agent 1). PCRL aims to learn the optimal policies maximize the accumulated discounted return of an MDP.
134
136
138
Without losing generality, we suppose agents R1, Re,..., Ry are priority-ordered according to the agreed conventions, where N is the number of agent. Corresponding to the above basics and Fig. 2 the overall pseudocode of PCRL in Algorithm in appendix. modified from the DQN [T. differing in aspects of action schemes.
140
neural network architecture and learning
142
143
State representation
When macroscopically viewed in Fig. bb. the planner maps current state 8 (consisting of features of current physical map state and agent state) to an action vector:
144
T = (*x),
145 where f is a trainable RNN-based function and is to be optimized. For cleanness, we will omit the
146 subscription of / for the current state hereafter.
147 The state can convoluted features or simply the concatenation of raw map state and agent state, i.c., st concot(M AP,, Using the CCPP (in Fig. [b) an example,

---

149
Sgrid map Sagent_postinn positions: where "I" means concatenation; grid map can be binary vector indi- cating whether each grid has been covered (i.e.. visited), and agent _ositiooo are an integer vector with length equal to grid_map map indicating the agent number upon each cell.
150
152
For simplicity, the state 8 will be supplied the initial hidden state (other usages are also possible), i.., the h and c, of the RNN of the planner.
153
Action representation and selection If the action space is not large enough, then joint-action representation and selection will work. However, large action brings in intractabilityy The action in PCRL is represented using recurrent neural networks. When generating ā (a1, a2 ..... d,), PCRL resembles the image-to-caption [1 technology in that when given a state 8, PCRL learns to optimize and produces sequence of (;; [1, N] with an assigned the highest priority agent and this sequence aims to bring about the maximum return. Mathematically, the action for the highest priority agent (i.e., the a1) generated as below:
155
157
158
159
180
co). _ argmax Ti
01 = argmax
(2)
where hg = Co is the feature of state s, and supplied as the initial state of the RNN. Ö is the input of the RNN in this micro-step and means no agent has been decided an action (can refer to Fig. (c). cargmax (stands for consistent argmax) function means selecting the action for the highest priority agent, i.e., R₁ according to the agreed action priority convention if ties exist. RNN() function is one-step forward function of the RNN, which is with only |A| output entries. If ties exist in output entries, argmax should consistently select the smallest optimal action according to action priority, so
181
163
165
166
167
hereafter we write argmax as cargmax. For the cargmax function, say. if J&N N() outputs a value vector of [5.1, 5.32, 5.2, 5.32), then we consistently select the first "5.32" (index=1) in case of ties whereas trivial argmax in pytorch may return unguaranteed and inconsistent index.
168
189
Remark I: Better comprehended with CCPP in Fig. Db.. Ti means the expected Q value for the
170
whole system when agent selects each action from A, so Qibil. j E |A| tries to approximate
171
max 82X E Q(8, (a1 = actionn, 02 ... ,NN)) 2 d....
(3)
172
This approximation is possible since contains all information of the current state including the total number of agents, and the following agents refer to and fully cooperate a actiony. (Eq. 2
173
can also be viewed from state mapping, i.e., Q1: (grid states, agent state, total=N, priority=/ (or highest)) - real values - one index. This mapping can be learned by reinforcement learning.
174
175
178
Similarly, for the remaining agents, the planner conditions at previous agents' actions and the priority conventions as well, so
177
a cargmax RN RNN ((1;-1, (a;hot(a;1))..
(4)
178
where onchot function maps an integer into a 0-1 input in which there is only one in index Q;-1-
Remark 2: Assume now = 2, then now this RNN()) 12tuututss A entries and approximates
max oo EAN- Q(s, (a1, 02 = action,, az...........................a .aN)) 2 Qyii.
(5)
180
where a1 has been determined at previous micro-step and conditioned at this micro-step.
181
The approximation in each micro-step has physical meaning: If sufficiently trained, then
शे A RNN* (s, 0), len (Q1) = |A]
(6)
(*(8)= max Q1- E
(7)
RNN (s, (cargmax@()),, len Len(@))) = |Al
(8)
(s) = max Q
(9)
aAEA
(10)
max 2 max Q max Q
(11)
5

---

182
where function len is the number of output entries. The physical meaning can be comprehended as that the RNN is to approximate the optimal value of the monothetic system. The last line is important because (s) links all the Q and can be exploited to achieve better learning.
183
184
185
The reward at each step is the total reward that all agents earn. The total reward is beneficial for learning and regards the system as a monolithic system. In Fig. [c), the reward the number of uncovered grids that the whole system visits at this step. An uncovered grid will give reward of only for the first time it was visited. If Rt Rıs executed the solid arrow action, the reward would be 16. Sometimes, step penalty is added to the step reward so that the hypothesis reward [34] in RL holds so that, maximizing the return of the MDP ++ minimizing the step cover
Reward
188
187
188
189
190
all shaded cells.
192
Training As Fig. and Algorithm depict, the training strategy needs specially designation. When in state s and takes action a, the MDP will transfer to some s' and get reward r, then ((s, a) should converge to the target Q target,
193
194
Qtarget = + max Q(s',a')
(12)
195
where a' can be selected out on the target network according to (Eq. to (Eq. rather than enumerating all A action combinations. The ((s, a)) = (s,, (a1, 02,..., ..., uN) can be calculated by feeding 0. (nehot(a1)...... onchot((N-))) to the RNN in the N micro-steps and gathering the av entry in QN (see Fig. c)).
196
197
199
Moreover, considering the uniqueness of our PCRL decision flow and (Eq. we can use an
auxiliary loss to accelerate and smoothen the training. The auxiliary loss is equalities among agents'
201
Qi values (as explained in (Eq. TT and that paragraph), i.e.,
Tranz (88, ud, PT, 88) (max (ss,, 0) Qtarges) )² + (max Q(ss, (Ō, (aa))(a(())))) Qtarget) )² (max (sss, (Ō, onehot (.., onehottaaaa 1}})) Qtarget) )2 (13)
202
where 88 and ad are batch data from the experience replay buffer. Laue guides the mean-squared еπrо of Qs of each agents to converge to target Qtarget. Other type of (Eq, 13) is also possible.
203
We propose the following, and the proofs are in the appendix.
Theorem 1.
The action representation scheme and selection process will not lose the optimality of the action space and can select out the texicographic-smede -mallles optimal action vector.
206
207
Theorem 2. The action selection process breaks the exponential action space into linearly expressible space complexity.
Experiments and Discussions
209
210
We evaluate the performance PCRL on two seemingly different but both can be viewed as microscopically sequenceable multi-agent applications: multi-agent complete coverage path planning (CCPP) problem and Cooperative Pong (CP). We compared our method with joint-action RL or heuristics their efficacy and efficiency. All experiments were carried out computer of amd ryzen 9 5950x, with a single 3090 RTX GPU. Every method has run 10 times with different random seeds each experiment setting and reports the averages and the standard deviations (STD), to gain the reliability of the evaluation. The hyperparameters are listed in the appendix, also in the source code that is supplemented.
212
214
216
218
Our experiments consist of (1) The PCRL's LDAS dealing ability and optimality- ability on CCPP, compared to joint-action DQN. (2) the PCRL's optimality-fnddin ability CCPP, compared to the heuristic algorithm. (3) the PCRL's optimality- finding and end-to-end ability on CP, compared
220
to joint-action DQN.

---

222
4.1
Multi-agent complete coverage planning
PCRL illustration and consistent argmax d the sufficiently trained (for hour) and 223
converged results of the two-agent complete coverage path planning example on the 3 x 3 gridworld. The first column is the current state, where "1" stands for shaded grid cell and stands for agent.
225
226
The agents are homogeneous and the priorities are position-determinest so we ignore the ID of them.
227
The second column shows the outputs of the RNN (i.e., the Q values of RI.) in two miero-steps.
The first micro-step has the Q value for the highest priority agent. It is the expectation for the first agent to decide an action and the following agent to decide a corresponding action And the second mtero-step is the second agent's Q value referring to the first agent's is action and fully supporting the first agent. As can be seen, the bolded values are near, which is almost the (*(s) (The ground
228
231
232
truth (s) each current state be easily caleulated). We can see that the total return received
233
in the first state is six, which is eight plus the penalty multiply minimal steps. The third column is
234
the optimal action for each agent, obeying to the priority. The fourth column is the reward for the
235
whole two-agent system. The last line column is some explanation for data interpretation. Due to the
236
cargmax function, this RNN has converged to the smallest lexicographic action vector each state,
237
and in training stage helped exploitation.
Table 1: CCPP illustration of PCRL and consistent argmax
Cumonnt watz
Ualle TAO mhpo-
Omterggt
Booward
Explanation
111
111
E5.0000 5.5337 BAN9 5.1314]. [4.032, 5 1386 5.000, SU878]]
inf
tnurite sewry covored odls plaa the step pasalty
Ze: 5
Laiital actives (ap left). sciecs leicognatic undle "wy" The sccord spest sefocingg to this sdeca "eel' and can get the whole sysiem layest Q
M.
31R
RR0
14.8065, 5.9177 4. 1.65% 3.4181]
7621, 3 5145, 3,371, 7.6447)
top
thic the sccand prortty agen near or "tett" acriin and 'rgg" is wilenve
111
0.0
122, 2.244,
2.4255,
2,150%
2460.3e15
R
TK0
E04534 1.5007 0.351270..4911
(0.5143, 019800. 1.5000, 0,49471)
(pread) buda (x) value gule close fiis covadd)
216005)e15
After evoeating dert, downj, The misior comglerdd
238
PCRL and DQN in deterministic transition environment CCPP We compared the final perfor-
239
mance of PCRL, joint-action DQN on grid world on various numbers of agents. The details of the results are shown in the Fig. 3
240
Fig. left) shows that when trained enough steps, PCRL can get close final performance to joint- action DQN. That means the PCRL network can successfully learn the priority conventions and the proper Q values, and has an ability similar to the monothetic system. Moreover, PCRL has the potential to deal with over 10 actions: the needed parameters of DQN are exponentially increasing while PCRL has linearly increasing number of parameters, about 562176 for 12 agents (see the middle of Fig. B). The performance of DQN is slightly better than PCRL, however the performance decreases quite rapidly and soon fails to tackle 12 more agents scenarios (see the right of Fig. 3
242
244
246
247
248
where the averaged return of PCRL is normalized as 100%)
Cocponcio Coeating
Number of Mauuectes to nandor
Mairum rdum comperison
PCL
Figure 3: Comparisons of PCRL and joint-action DQN. left: performance on CCPP of 2 agents and 10 x 10 map size with 99 cells except the down- fogn--ightmost visit in deterministic transition environment; middle: the total number of needed parameters; right: performance of DQN dives comparing to PCRL's.
249
Large space and non-determiiistic transition environment The Fig. depicts 18 agents on a 9 x 9 grid world the same as Fig. [c). with 54 uncovered cells in total. This case, at each step, owns over 10 action vector candidates. The experiment further made tougher to a non-deterministic (stochastic) environment. In the non-deterministic transition environment experiment, there is
250
251
253
non-zero probability p of "leftwards slipping" when agents take actions (say agent takes "up" then has p probability being moved to the "left" cell), where agents' do not have any prior knowledge about
7

---

255 the environment transition. Fig. 4 shows the averaged score and averaged steps with sliding-window window 258 width 100 in the training episode. As shown, the training is converging gradually and smoothly. The averaged steps is approaching 20 and the averaged return is about 44.
10300
13683
20003
160
15.00
153
1000
Figure 4: The training of 18 agents in the stochastic environment, where the joint-action DQN unable to tackle.
To further compare the steps, which is the focus of CCPP, we employ heuristic search algorithm where the agent selects the minimum Manhattan distance cell and goes towards the cell. The Violin plot is depicted in Fig. S where the first "violin" is the performance of RNN in mid-course of training, while the second one is of the final RNN after training. The third one is for the heuristic algorithm.
259
281
PCRL can learn to optimize and use 20% smaller steps (19.7 VS 24.5) cover all the shaded cells,
283
and is more stable.
distributions
175
125
50
Figure 5: 18 agent performance PCRL (mid-course and final) compared to the heuristic. Mcan/Stdev of steps are 28.9/16, 19.7/5.6, 24.5/13.3, respectively.
4.2 Cooperative pong
285
Cooperative pong Fig. (d) is game where the objective is to keep the ball in play for the longest time. The game over when the ball goes out of bounds from either the left right edge of the screen. All collisions of the ball are elastic. Cooperative Pong has 480 pixels x 280 pixels, so a ball with speed 9 will cost about 60 steps to go from the left paddle to the right paddle. Algorithms that can keep the ball for 400 steps are rare [35]. The CP can be established as joint-action DQN with and microscopically sequenceable multi- agelt- problem. To show the applicability of PCRL in CP task, we applied PCRL on the state-based and pixel- based CP, respectively.
257
289
271
272
State-based based CP and pixel-based CP We trained PCRL and the joint-action DQN on CP with similar scale of network parameters, and the performance illustrated in Fig. 6al Set ball b speed=9 pixelsstep, left paddle_speedee bounce saaeeeerdndomnns=aalsse each frame reward=1, out boundary reward=-100 We can see that PCRL even outperforms the joint-action DQN which treats the two agents monothetic agent. The key reason for this result may be that PCRL higher parameters efficiency than DQN of a similar scale of parameters.
273
right paddle_ soeelle_ppee=28,,, cake_ cake_paddle=Fau paddle=False, max mexx__cccl=000,,.
274
275
277

---

279
To better demonstrate the effectiveness of our approach, we also use the pixel states as the Q-net inputs. We resize the original pixel state 84 84 * 3 tensor. We use a 3-layer convolution network transforming the pixel state to a vector state first, and then feed the vector state as the RNN hidden state. The performance training with pixel states (in about four hours) shown in Fig. 6b from which we can see that our algorithm converges after about 1000 episodes and get satisfactory
280
282
284
performance. indicates that PCRL is effective and efficient even in the end-to-end setting without losing much performance compared to the state-based pong performance.
Cooperative Pong
140
230
DGN
Epiice
Figure 6: Convergence of Q. a: Training performance of statc-bascd cooperative pong. b: training of pixel-based CP (playing video attached)
Conclusion
286
This paper tackled the microscopically sequenceable multi-agent problems via reinforcement learning that combines agreed priority conventions. The agreed priority conventions can successfully break the exponential scale actions into sequence of actions (linear scale expressible) without losing optimality. From the multi-agent complete coverage planning and cooperative pong experiments, the algorithm shows closeness superiority in effectiveness and efficiency to the joint-action DQN and heuristics. The results suggest the potentials of PCRL for larger number of multi-agent systems (say recommending systems) or swarm robots.
288
290
292
283
294 In the future, further work can be done, such as (1) larger agent number multi-agent systems to verify the ability of PCRL for larger action space problems, say swarm robots. (2) application of this algorithm to fully-distributed or centralized- sondd-trriinnnnndd wwwaanneeetrralzeedeeeeeeee systems. (3) studies of PCRL for heterogeneous agents. (4) studies on partial observable domains.
296
multi-agent
References
298
[1] Pablo Hernadezz-eaal, Bilal Kartal, and Matthew E Taylor. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems, 33(6)7750-777, 2019.
300
302
[2] Jing Zhang and Dacheng Tao. Empowering things with intelligence: a survey of the progress, challenges, and opportunities in artificial intelligence of things. IEEE Internet of Things Journal, 8(10):7799-8877, 2020.
303
304
305
[3] Michael Rubenstein, Christian Ahler, and Radhika Nagpal. Kilobot: A low cost scalable robot system for collective behaviors. In 2012 IEEE International Conference on Robotics and Automation, pages 3293-3298. IEEE, 2012.
307
308
[4] Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5571-5580. PMLR, 2018.
310
[5] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning, Nature, 518(7540):5295333 2015.
312

---

314
[6] Wei Wu, Fengchun Yang, Fuhui Zhou, Han Hu, Qihui Wu, and Rose Qingyang Hu. Intelligent resource allocations for assisssi ofdm communications: A hybrid mdqn-ddpg approach. arXiv preprini arXiv:2202.05017, 2022.
315
316
317
[7]
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Rellermeyer. A survey on distributed machine learning. ACM Computing Surveys (CSUR),
318
319
53(2):1-33, 2020.
320
[8] Gabriel Dulac-Amold Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. Deep reinforcement learning in large discrete action spaces. arXiv preprint arXiv: 2015.
321
322
323
99] Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR), 52(1):1-33, 2019.
324
325
[10]
Yuxi Li. Deep reinforcement learning: An overview. arXiv preprint arXiv:1701.07274. 2017
[11]
Jason Pazis and Ronald Parr. Generalized value functions for large action sets. In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages
327
328
1 1192, 2011.
[12] Yash Chandak, Georgios Theocharous, James Kostas, Scott Jordan, and Philip Thomas. Learning action representations for reinforcement learning. In International Conference on Machine Learning, pages 941-950. PMLR, 2019.
330
[13] Prabhakar Raghavan and Clark D Tompson. Randomized rounding: technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374 1987.
333
334
[14] Brian Sallans and Geoffrey E Hinton. Reinforcement learning with factored states and actions. The Journal of Machine Learning Research, 5:1063-1088, 2004.
335
338
[15] Hajime Kimura. Reinforcement learning in multi-dimensional state-action space using random rectangular coarse coding and gibbs sampling. In SICE Annual Conference 2007, pages 2754-2761. IEEE, 2007.
337
338
339
[16]
Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J Mankowitz, and Shie Mannor. Learn what not to learn: action elimination with deep reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3566-3577,
340
341
342
2018
343
[17]
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, 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 4295-4300
344
345
348
PMLR, 2018
347
[18] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. In International Conference on Learning Representations, 2020.
348
348
[19] Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforce- ment learning with emergent roles. In International Conference on Machine Learning, pages 9876-9886. PMLR, 2020.
350
351
[20] 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. PMLR, 2019.
353
354
[21] Ivan Sorokin, Alexey Seleznev, Mikhail Pavlov, Aleksandr Fedorov, and Anastasiaa Ignateva. Deep attention recurrent q-network. arXiv preprint arXiv: 1512.0199,, 2015.
356
357
[22]
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. In 2015 aaai fall symposium series, 2015.
[23] Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pages 66-83. Springer, 2017.
360
10

---

362
[24] Ardi Tampuu, Tambet Matüsen, Dorian Kodelja, llya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. PloS one, 12(4))e0172395 2017.
363
365
[25] Peng Peng, Quan Yuan, Ying Wen, Yaodong Yang, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent wtwpeettiionnllyyyooonaaaa nets for learning to play starcraft combat games. arXiv preprint arXiv:/703. 10069, 2, 2017.
366
367
388
[26] Adam Lerer and Alexander Peysakhovich. Learning social conventions in markov games. arXiv preprint arXiv; 1806. 10071, 2018.
389
370
[77] Bingeai Chen, Chao Yu, Qishuai Diao, Rui Liu, and Yuliang Wang. Social individual learning? an aggregated solution for coordination in multiagent systems. Journal of Systems Science and Systems Engineering. 27(2):180-200, 2018.
371
372
373
28
Jelle R Kok, Matthijs TJ Spaan, Nikos Vlassis, al. An approach to noncommunicative multiagent coordination in continuous domains. In Benelearn, pages 46-52, 2002.
374
375
[29] Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropa- gation. In Advances in Neural Information Processing Systems, pages 2244 2252, 2016.
[30] Ryan Lowe, Yi Wu, Aviv Tamar. Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. Multi- environments. In Advances in Neural
378
agent actor-critic for mixed cooperative-competin Information Processing Systems, pages 6379-6399999 6390, 2017.
[31] Wojciech Zaremba, Ilya Sutskever, and Oriol Vinyals. Recurrent neural network regularization. arXiv preprint arXiv: 014444092223 2014.
381
382
[32] Yiming Zhang. Quan Ho Vuong, Kenny Song, Xiao Yue Gong, and Keith W Ross. Efficient entropy for policy gradient with multi muuti-diimnsional action space. In 6th International Conference on Learning Representations, ICLR 2018, 2018.
384
385
[33] Luke Metz, Julian Ibarz, Navdeep Jaitly, and James Davidson. Discrete sequential prediction of continuous actions for deep rl. arXiv preprint arXiv: (xXvv:/705.050:3 2017.
387
[34] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
388
389
[35] Justin K Terry, Benjamin Black, Mario Jayakumar, Ananth Hari, Ryan Sullivan, Luis Santos, Clemens Dieffendahl, Niall L Williams, Yashas Lokesh, Caroline Horsch, et al. Pettingzoo: Gym for multi-agent reinforcement learning. arXiv preprint 200.1:20009.4441,, 2020.
380
391
Checklist
392
1. For all authors...
394
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See the abstract and introduction. Moreover, The abstract, introduction and experiment results are consistent.
395
396
387
(b) Did you describe the limitations of your work? [Yes] See the conclusion part. (c) Did you discuss any potential negative societal impacts of your work? [Yes] The technique is neutral.
398
399
400
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Our paper is strictly comforms them.
402
2. If you are including theoretical results...
403
(a) Did you state the full set of assumptions all theoretical results? [Yes]
404
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL.)? [Yes] In the supplemental material.
407

---

409
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the article, appendix and codes.
410
411
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Each ran at least ten times.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In an ordinary desktop computer.
414
415
4. If you are using existing assets (c.g., code, data, models) or curating/releusing new assets...
416
(a) your work uses existing assets, did you cite the creators? [No]
417
(b) Did you mention the license of the assets? [No]
418
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you' 're
using/curating? [No]
420
421
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
424
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [No]
425
426
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [No]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No]
429
12

---

end for A Appendix
A.1 Pseudocode of PCRL
Algorithm 1 PCRL: Priority convention RL
1: Initialize replay memory D; Initialize the evaluation RNN (the action-value function Q) with
random weights 0; Initialize the target RNN (the action-value function Q) with weights 6 0
2: for episode=1 to E do
3: Observe initial state
4: while unterminated do Select action 7: with probability select random action vector by uniform sampling: otherwise, generate i as Fig. 2 and (Fq. to (Eq.
5:
6:
Carry action d
7:
Observe reward r and new state s'
8:
Store experience < s, a, r' into replay memory D Sample random transitions < 88, ad, rr, ss' >> from replay memory D Calculate target for each minibatch transition:
9:
if ss' is terminal state, then tt = pr
otherwise rr + y # max, Q (ss',, a²) where a' is generated as Fig. c) and (Eq. to
(Eq. 4)
Train the evaluation Q-network using (tt (sss, ad)) Laaux (88, ad, rr, 8s') as loss with respect O, where Louz is the auxiliary convergence loss in (Eq. II) and (Eq. 13
12:
Update target network as = (1-1) (1-r)0 T)0' r0
13:
14:
end while
15:
A.2
Microscopic generation proofs
Theorem: The action representation scheme and selection process will not lose the optimality of the action space and can select out the lexicographic-smaal smallesst optimal action vector.
434
Proof. Suppose ã = (01, 02 ...,... an)) and 3= (B1, f., BN) are two (More than two tie optimal
action vectors can also hold similar conclusion.) optimal tie actions for a state 8, and in the article 437 has deduced that (s) = (ss, ā') (ss B).
436
438
Since the state is the same, i.e., the map and agent states are the same, thus the agent priority orders identical. Suppose ā is lexicographic smaller than Ø (this is possible, since each component of a and 3 are comparable according agreed action priority, either ă is lexicographic smaller than or 3 is lexicographic smaller than a. The latter can prove the following similarly).
442 Let j = min;(a; < (3;), the planner's procedure will select a; instead of 3, for agent i.
Since the smallest-lexicorrann action vector can be selected out and leamed, PCRL will not lose 444 the optimality for the concerned problem.
445 Theorem: The action selection process breaks the exponential action space into linearly expressible space complexity.
447 Proof.
The recurrent neural network has N micro-step outputs, each micro-step output consists of [A] actions. Suppose that at each micro-step, the planner can select one action, so possible total action combination space is still |A| so RNN will not miss expressing the optimal vector. However, optimum (maximum) action vector can be expressed by and selected from |A] per micro-step x
448
450
N micro-steps.
13

---

452
A.3
Common hyper-paramettrs
453
The common hyper-parameters for experiments are:
Table 2: Add caption
Tasks
CCPP
CP
learning rate
1.50E-04
1.50E-04
replay buffer size batchsize
2.00E+05
2.00E+05
128
128
episode length
200
900
1.0 with step penalty 0.5
0.995
1.00E-03
1.00E-03
k(weight update frequency) episode number
4
min(40000,H w agent nums * 50)
2000
epsilon_star start epsilon end opsilon_decay
1
1
0.01
0.05
0.99992
0.95
LSTM hidden size auxiliary loss
1024
512
type 1
type 2
The auxiliary loss type 1 is (Eq. [TI and type are the mean squared error of max Qi max Q2. max Q2 to max Qa etc. This two can get similar results.
455
The y of CCPP is set as listed because of the reward hypothesis.
457
Reinforcement learning based on the reward hypothesis, that is, RL is maximize G. k= 7 T++*+11 When t = 0, it is maximizing G = Soo 7 Rı + +
458
459
Le., the maximum expected return from the initial setting of the environment.
460
one wants to maximize the reward G to get the fewest step coverage route of the agent, then one needs to set appropriate parameters such y that G fits the aim. Generally, 0 S 7 1, when O, it a single-step reflective and myopic behavior. In this appendix, we want to maximize the reward G to obtain the fewest steps of multi-agent complete coverage. Because the multi-agent is treated as a monothetic system, so one agent's s proofs can naturally be extended to a multi-agent system. Through mathematical analysis, the following theorems and proofs be obtained:
462
464
466
Theorem 3. When & < 1 and there is no single-step penalty for each step, maximizing the return does not always get the fewest step complete coverage. When ?/ = 1 and each step has single- penalty (step_ thee__pealty<00 maximizing the return is equivalent to the fewest step complete coverage.
466
469
Before the proof, use Fig. 7 to illustrate the first sentence when 7 < 1. The figure shows the same environment configuration (setting). including the same map state and agent position. The two paths of the agent are path (1) and path (2). Denote their rewards are respectively ((1), ( It can be seen 472 in the figure that path (1) is shorter than path (2). However, when 7 < and each step has no penalty,
473 the return of path (2) larger, that is, (()) < G()); According to the return formula, the return for
paths (1) and (2) is G()) 1 72 73 ( =1
7 this time
G() (1 + 2 + (1 (1+1 + +74)
(14)
72 2 - -1
(15)
-n² -1-1) - 77 )
(16)
= (1² - 72) 72) <0
(17)
475
The last step because when 0 < <
< r¹ and > 7
476 However, When y = 1 and a single-step penalty step_penalty = -0.2, the return of path (1) is 2.2, and the return of path (2) is 2.0. This fits the requirements of CCPP: fewest steps and maximum return.
478
From the illustration of the figure, mathematical proof of the theorem can be obtained.
14

---

G
G
Figure 7: Example diagram maximum reward hypothesis and shortest path
480
Proof. Because there are examples shown in Fig. 7 the first sentence of the theorem can be proved by contradiction. For the second sentence of the theorem, it can be equivalent "When y 1, and each step has single-step penalty (step_ (step_penalty<0) a greater return is equivalent to a fewer step complete coverage path".
482
484
The idea of the proof to assume that there are path (1) and path (2), and the number of steps used n and m, respectively. Assume < m, 0, m > 0 and step_penally < O.
486
First prove the necessity, that is, under the same environment configuration, fewer steps will get greater return, that is, needs to prove ( ( Denote C; the cell step i and C. 1 if the cell has never been visited.
488
Because (1) = +Ci+step_ pee_ppalllly < + (C2 step_penalty) (t.a (C1 + step peee__eealtt) + (C2 + step sste_ppenalty +... (C,, + step sstep_penalty) (Ci
490
Cx) + n step_
nwmber_of uf__ooe
+ step_penalty.
Similarly, G(2) = (C, + C2 ... Cm) + m slep_penally = numberr_of _tw_ooo__ooooed_________________
402
m * penalty. Due to the penalty of each step, we get (()) > G(2), that is, smaller number
493
494
of steps gets a higher reward.
495
Proof of adequacy, that is, greater returns can lead to fewer steps. Because the rewards of a scene can be written as number_ _f_ uunovereed cells + k step_penalty where is the number of steps visiting all shaded cells, a larger reward corresponds to a smaller number of steps.
497
498
A.4
Planning difficulty for CCPP
499
CCPP can be established as a Euclidean Traveling Salesman Problem which NP-hard. Here we establish it an MDP. To realize the difficulty of the problem to set proper problem scale, first conducted a agent random wandering experiment to cover all grids and the experimental results are gridworld, where the y-axis the cells (the start cell is in down-rightmost and is empty). can be seen that the number of steps required increases almost exponentially (the log linearly interpolation curve has been fit and has been plotted in the same 10, the number of random steps completely cover all cells is more than 1000 steps, so we set it as the scale of the experiments. Roughly estimated, the total number of paths for problem scale of 10x x map size and agents can reach 100! (about 158), So, this pre-exxeriment
501
502
shown in Fig. 3 the r-axís represents the of the square
expected steps (averaged among 1000 runs) for a agent to visit all n
503
504
505
506
figure). When
507
508
509
has partially shown the complexity of problems that PCRL can tackle and have strong optimization ability.
510
511
A.5
Deterministic transition environment of 18 agents CCPP
Fig. shows the settings of Fig. (c) and with a deterministic transition environment. shows return and steps of each training episode, the training cost and the sliding-window
512
window averaged steps. The ground truth return is 52.5 and PCRL. sometimes can get 51.5 and an average near 50. This picture again shows the LDAS dealing ability and high optimality-findin ability of PCRL.
514
15

---

average Steps
interpolated exponetial function
10000000
1000000
100000
10000
10000
11 13 15 17
21 23 25 27 29
37 39
lateral
square map
Figure 8: Expected steps to cover all cells with random wandering
Figure 9: The training of 18 agents in deterministic environment.
A.6 Gap of max Qi in state-based CP
517 As shown (Eq. the maximum of Qi will equal to the maximum Q2 at the state 8, theoretically. Respecting this, we evaluate trained neural network to analyze the convergence of Qıs. Define the gap as (max Q2 max /1)/ max Q'. The left part Fig. shows the gap at every state along one test episode, while the right part shows the averaged gap in the training history of an RNN. The former demonstrates an only 5% gap in the states. The latter demonstrates that as training goes, gap from substantially large becomes narrow and narrow. Both parts proved the convergence of gaps between Qi, 1,.... N.
519
521
523
16

---

Quvilun robolien arrora ratioçona opinode)
Q-vallae relative enrers reño
Figure 10: Convergence Qs. Left: The gap along a test episode. Right: The evolution of gap in the training stage.
17


Reviews:
[{"review_id": "drCSeutgpmU", "reviewer": "Reviewer_3mod", "summary": "The authors attempt to tackle the problem of RL in settings with large action spaces caused by there being many agents in the system. The authors provide a mechanism to pick an ordering over which actions for each agent are generated by a planner and show that they can pick the action that is \"lexicographically smallest\"", "questions": "What is the connection between the results in this work and the results in “Multi-Agent Reinforcement Learning is a Sequence Modeling Problem”? and how does this paper go beyond the results there?\n\nWhat is the importance of tie-braking and the connection to social conventions posited in the introduction?\n\nWhat is the importance of small lexicographic orderings?\n\n\n## PCRL: Priority Convention Reinforcement Learning for Microscopically Sequencable Multi-agent Problems\n\n### Grammar + sundry things:\n\n- I think in the title the word should be sequenceable?\n- In abstract it should be “existing work has mainly tackled”\n- Figure 2 is too low resolution and has to be improved to be legible. This is essential.\n- The paper is full of what I would call “unbacked opinions”. The authors will say things like “the probability is hard to model” (line 104). Hard how? Why? The reviewers are asked to believe this on faith rather than with some backing. Or in line 178 the authors say “the approximation has physical meaning” but don’t state what it is.\n- The paper should probably have a reference to “**Multi-Agent Reinforcement Learning is a Sequence Modeling Problem”** which contains quite similar ideas.\n- What is the relevance of the reward hypothesis in lines 185-186? Also, there’s a paper to cite for this rather than a footnote.\n\n### Writing:\n\n- There are many components in the introduction that need to be rewritten to make the contributions of the paper clearer:\n    - What do social conventions have to do with microscopic and macroscopic sequenceable models?\n    - Why are priority conventions important?\n    - Why is the sequencing a solution to action space blow-up?\n    - More intuition on what microscopic sequenceability is\n- This paper is not written in standard academic form and employs colloquialisms in many places such as lines 129-130\n- There are spelling mistakes through the paper. Please employ a spell-checker.", "limitations": "The authors, in the conclusion, point out that they investigate their results on a relatively limited number of systems.", "rating": 3, "confidence": 5, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Unfortunately, this paper is written in a manner that makes it not possible to assess the quality of the paper. The main figure in the paper is unreadable, basic definitions are missing, spelling errors are abundant in almost every paragraph, and the figures are low enough pixel density that I have trouble reading them on my laptop (they appear to be screenshots). This is unfortunate because the underlying idea, to the extent that I can figure out what it is, that actions can be selected sequentially in centralized, cooperative multi-agent problems is interesting and the related work suggests the authors have expertise on this topic. I would ask the authors to do a more thorough job in preparing their paper for submission and provide some suggestions on how to do so.", "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": "OedQjZPIxbh", "reviewer": "Reviewer_6W63", "summary": "The paper aims to tackle the problem of large discrete action spaces in multi-agent MDPs (MMDPs) where the number of actions rises exponentially with the number of agents. The paper proposes to embed agreed priority conventions (agent priorities, agent ID, action priorities) into reinforcement learning (PCRL) to tackle large action spaces. The paper leverages RNNs to generate Q-values for the system one dimension of the action vector at a time sequentially (while maintaining priority conventions), and proposes an equality auxiliary loss to make sure that the V*(s) are equal for each RNN output corresponding to each action dimension. The paper claims that the priority conventions do not miss the optimal actions. The authors evaluate their proposed approach on coverage planning and pong domains.", "questions": "- Can the authors answer questions from the weakness/strengths section?\n\n- Additional Questions\n\n  - It seems like the different priority conventions (agent priorities, agent ID, action priorities) conventions are predefined before learning. Would it affect the convergence if conventions are changed? For example, if action priorities are changed, would it change the final solution? How would one define such priority conventions for large scale domains like Starcraft II [7]?\n\n  - Line 235: the authors mentions that “PCRL network can successfully learn the conventions”. Aren’t the conventions already predefined for the domains? ", "limitations": "Yes, the authors does mention the limitations of their work via a future work paragraph. Additionally, the authors should consider partial observable domains and possibly learning priority conventions.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## General Comments \n- The proposed approach seems sound and it is interesting to see authors approach match up to the performance of DQN with significantly lesser number of parameters required.\n\n- The paper is a bit hard to understand at places with grammatical mistakes. Figure 2 makes it easier to understand the paper. It would be great if the authors could take some time to focus on the writing of the paper. Some points to consider:\n\n  - For example:  “some researchers resorted to independent reinforcement learning (RL) regardless of other agents, but that will form loose cooperation and yield suboptimal solutions” → Independent MARL has shown to be a surprisingly good baseline in recently published papers in cooperative MARL. [6]\n  - Some minor points:\n    - Line 161: \"where h_0 = C_0 is the featured and supplied state s\" → I am not sure what the authors mean by featured and supplied state?\n    - Line 166: ungaurenteed → unguaranteed; inconsitent → incosistent\n    - Line 198: (??) reference missing\n\n- The paper is missing several key citations from recent MARL literature which especially focuses on improving exploration in MARL large action spaces with role-based learning (RODE: [1]) as well as papers leveraging the centralised training decentralised execution (CTDE) framework (an intermediary between fully decentralised learning and centralised learning) [2,3,4,5]\n\n- The idea of leveraging RNNs to predict one dimension of the action vector at a time seems to be very similar to the other works [7,8] with similar equality constraints as proposed by authors in Eq. 11. Can the authors comment on the novelty of their approach?\n\n- The considered problem in the paper seems to be difficult from the perspective of a large number of agents (thereby large action spaces), and therefore the proposed approach seems to be only useful for scenarios with full observability and homogeneous agents which is not commonly observed in real-world multi-agent problems.\n\n## Comments on Experimental Section\n\n- The authors only compare their approach against the joint-action DQN based approach. There have been several recent works on tackling the large action spaces in MARL with role-based learning [1], and other CTDE based approaches [2,3,4,5] which can tackle large action spaces pretty effectively especially on the coverage and pong domains in the paper. The authors should compare against these approaches to fully showcase the effectiveness of their approach.\n\n- The authors does not evaluate on any large-scale multi-agent RL domains like Starcraft II (SMAC) [7] (with some maps having 27 agents and each agent allowed to take 8 actions) which would help prove the efficacy of their method on large action space domains.\n\n[1] Wang, Tonghan, et al. \"Rode: Learning roles to decompose multi-agent tasks.\" ICLR 2020.\n\n[2] Son, Kyunghwan, et al. \"Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning.\" International conference on machine learning. PMLR, 2019.\n\n[3] Mahajan, Anuj, et al. \"Maven: Multi-agent variational exploration.\" Advances in Neural Information Processing Systems 32 (2019). APA  \n\n[4] Rashid, Tabish, et al. \"Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning.\" Advances in neural information processing systems 33 (2020): 10199-10210. APA  \n\n[5] Son, Kyunghwan, et al. \"QTRAN++: improved value transformation for cooperative multi-agent reinforcement learning.\" arXiv preprint arXiv:2006.12010 (2020).\n\n[6] de Witt, Christian Schroeder, et al. \"Is independent learning all you need in the starcraft multi-agent challenge?.\" arXiv preprint arXiv:2011.09533 (2020).\n\n[7] Samvelyan, Mikayel, et al. \"The starcraft multi-agent challenge.\" arXiv preprint arXiv:1902.04043 (2019).\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": "IZfFewvZaH3", "reviewer": "Reviewer_Kbn5", "summary": "This paper looks to tackle multi-agent reinforcement learning problems operating in large-discrete-action spaces. The authors do so by introducing a priority convention into the RL loop. The priority convention results in generating a sequence of actions that are somehow better. The authors demonstrate the effectiveness of their algorithm by demonstrating experiments on various multi-robot problems. ", "questions": "I do not think this paper in its current form meets the high bar for publication at NeuRIPS. The paper is weak in many areas from writing. novelty, actual methodology, experimentation. \n\nI recommend the authors take a step back and re evaluate the proposal here and what introducing priorities does to the problem and if it even needs RL if one were to introduce a heuristic like priority convention. ", "limitations": "Please refer above. ", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper is thorough with its literature review. \n\nWeaknesses\n1. The paper is extremely poorly written and throws around a lot of words that carry no meaning scientifically. For example in the abstract alone \"In this work, we propose to embed agreed priority conventions into reinforcement learning (PCRL) to directly tackle the microscopically sequencable multi-agent LDAS problems\" To the best of my knowledge I have never heard the term microscopically sequencable (and after reading the paper I still do not know what the authors are trying to say with the term microscopically sequencable means in a rigid mathematical sense.) Further phrases such as \"can help exploitation around the lexicographic-smallest optimal action vector\" make no sense to me. Such phrases and terms occur in the paper at multiple places and either serve very little purpose or only stand to confuse the reviewer when not rigidly defined. The phrase cargmax or consistent argmax at a first glance only confuses the reader. I would very sincerely request the authors to overhaul Section 3 and define everything instead of vaguely throwing out terms that either mean nothing or only confuse the reader which is to say nothing of the poor choice of notation (writing out \"one hot\", ? in Line 198, writing out \"length\") that only makes things worse.\n2. Now to come to the actual methodology devised in the paper here; the authors say nothing about what the actual priority convention is anywhere in the paper or in their experiments. How is the priority convention decided? How is it set. What are the parameters. How does it affect the training. In the experiments the robots all look identical and how does interchangeable convention set precedence to anything; i.e if Robot 1 is the same as Robot N then how does it matter if I switch priority from 1 to N and vice-versa. \n3. Further, the paper itself doesn't say anything about what happens if you force in a priority convention/ie why do you still need RL. In most cases in multi-robot problems, setting a priority convention is akin to setting a heuristic and removes the need for any RL. One chooses multi-agent RL if there exists a hard to define objective function for each robot but there exists a global objective function we wish to optimize for. If one is able to discretize this and say R1 is more important than Rn, then it is fairly trivial (especially in the grid world situations) to design a controller without any RL or machine learning that simply optimizes for the R1 > Rn objective. If one thinks back about the problem in Fig 1c, if, there exists a priority convention for the 18 robots, you do not need a learning based solution and can simply write a dfs solution with some edges carrying more weights (corresponding to the priority convention) and have the optimal solution. In the case where you have stochasticity it still seems to me that one can get away without doing any RL and setup an objective function that accounts for the stochasticity.\n4. Lastly, the experiments are extremely poorly designed. The proposed method needs to be compared with a relevant algorithm, By biasing the proposed algorithm and not providing the baseline DQN any reward based on the priority convention or information about the priority convention, the baseline is handicapped. Further, the experiments themselves are not compelling enough to determine that the proposed method here outperforms any standard non heuristic enabled multi-agent RL algorithm. \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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Reject