Learning to Share in Multi-Agent Reinforcement Learning
Authors: Yuxuan Yi
Ge Li
Yaowei Wang
Zongqing Lu
Venue:  (2021)

Abstract: In this paper, we study the problem of networked multi-agent reinforcement learning (MARL), where a number of agents are deployed as a partially connected network. Networked MARL requires all agents make decision in a decentralized manner to optimize a global objective with restricted communication between neighbors over the network. We propose a hierarchically decentralized MARL method, \textit{LToS}, which enables agents to learn to dynamically share reward with neighbors so as to encourage agents to cooperate on the global objective. For each agent, the high-level policy learns how to share reward with neighbors to decompose the global objective, while the low-level policy learns to optimize local objective induced by the high-level policies in the neighborhood. The two policies form a bi-level optimization and learn alternately. We empirically demonstrate that LToS outperforms existing methods in both social dilemma and two networked MARL scenarios.

Under review as a conference paper at ICLR 2021
LEARNING TO SHARE IN MULTI-AGENT REINFORCE- MENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we study the problem of networked multi-agent reinforcement learn- ing (MARL), where number of agents are deployed as a partially connected net- work. Networked MARL requires all agents make decision in decentralized manner to optimize a global objective with restricted communication between neighbors over the network. We propose hierarchically decentralized MARL method, LToS, which enables agents to learn to dynamically share reward with neighbors
to encourage agents to cooperate each agent, the high-level policy learns how to share reward with neighbors to de- compose the global objective, while the low-level policy learns to optimize local objective induced by the high-level policies in the neighborhood. The two poli- cies form bi-level optimization and learn alternately. We empirically demon- strate that LToS outperforms existing methods in both social dilemma and two networked MARL scenarios.
the global objective. For
INTRODUCTION
In multi-agent reinforcement learning (MARL), there multiple agents interacting with the envi- ronment via their joint action to cooperatively optimize an objective. Many methods of centralized training and decentralized execution (CTDE) have been proposed for cooperative MARL, such as VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018), and QTRAN (Son et al., 2019). However, these methods suffer from the overgeneralization issue (Palmer et al., 2018: Castellini al., 2019). Moreover, they may not easily scale up with the number of agents due to centralized learning (Qu et al., 2020a).
In many MARL applications, there are large number of agents that are deployed as partially con- nected network and collaboratively make decisions to optimize the globally averaged return, such as smart grids (Dall' Anese et al., 2013), network routing (Jiang et al., 2020). traffic signal control (Chu et al., 2020), and loT (Xu et al., 2019). To deal with such scenarios, networked MARL formulated to decompose the dependency among all agents into dependencies between only neighbors in such scenarios. To avoid decision- messages with neighbors make decisions in a decentralized way (Zhang et al., 2018; Qu et al., 2020b). However, there are still difficulties of dependency if anyone attempts to make decision independently, e.g., prisoner's dilemma and tragedy of the commons (Pérolat et al., 2017). Existing methods tackle these problems by consensus update of value function (Zhang al., 2018), credit assignment (Wang et al., 2020), or reward shaping (Chu et al., 2020). However, these methods rely on either access to global state and joint action (Zhang et al., 2018) or handcrafted reward functions (Wang et al., 2020; Chu al., 2020).
with insufficient information, agents are permitted to exchange the network. In such settings, it is feasible for agents to learn to
Inspired by the fact that sharing plays key role in human's 's learning of cooperation, in this paper, we propose Learning To Share (L.ToS), hierarchically decentralized learning method for networked MARL. LToS enables agents to learn to dynamically share reward with neighbors so as to collabo- ratively optimize the global objective. The high-level policies decompose the global objective into local ones by determining how to share their rewards, while the low-level policies optimize local objectives induced by the high-level policies. LToS learns in decentralized manner, and prove that the high-level policies are a mean-field approximation of the joint high-level policy. Moreover, the high-level and low-level policies form bi-level optimization and alternately learn to optimize

---

Under review as a conference paper at ICLR 2021
the global objective. LToS is easy implement and currently realized by DDPG (Lillicrap al., 2016) as the high-level policy and DGN (Jiang et al., 2020) as the low-level policy. We empirically demonstrate that LToS outperforms existing methods for networked MARL in both social dilemma and two real-world scenarios. To the best of our knowledge, LToS is the first to learn to share reward for global optimization in networked MARI..
RELATED WORK
There are many recent studies for collaborative MARL. Most of them adopt centralized training and decentralized execution, such as COMA (Foerster et al., 2018), VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018), and QTRAN (Son et al., 2019). Many are constructed on the basis of factorizing the joint Q-function by assuming additivity (Sunehag et al., 2018). monotonicity (Rashid et al., 2018), or factorizable tasks (Son et al., 2019). However, they are learned in a centralized way and hence may not easily scale up with the number of agents in networked MARL (Qu al., 2020a). Moreover, these factorized methods suffer from the overgeneralization issue (Palmer et al., 2018; Castellini et al., 2019).
Other studies focus on decentralized training specifically in networked MARL, to which our work is more closely related. Zhang et al. (2018) proposed consensus update of value function, but it requires global state at each agent, which is usually unavailable in decentralized training. Chu et al. (2020) introduced a spatial discount factor capture the influence between agents, but the spatial discount factor remains hand-tuned. Sodomka et al. (2013) and Peysakhovich & Lerer (201 8b) involved the concept of transferable utility to encourage cooperation, and Peysakhovich & Lerer (201 8a) resorted to game theory and gave more complex reward designs. However, these methods cannot be extended beyond two-player games. Hughes et al. (2018) proposed the inequity aversion model to balance agents' selfish desire and social fairness. Wang et al. (2020) considered to learn the Shapley value as the credit assignment. However, these methods still rely on hand-crafted reward designs. Mguni et al. (2019) added extra part to the original reward as non non-potential based reward shaping and used Bayesian optimization to induce the convergence to a desirable equilibrium between agents. However, the extra part remains fixed during episode, which makes it less capable of dealing with dynamic environments. Moreover, the reward shaping alters the original optimization problem.
3 BACKGROUND
3.1 NETWORKED MULTI-AGENT REINFORCEMENT LEARNING
Assume N agents interact with an environment. Let V = multi-agent system is modeled as an undirected graph G(V, E), where each agent serves as vertex i and & C V x V is the set of all edges. Two agents i,j E V can communicate with each other if and only if ezj (i,j) E. We denote agent and its all neighbors in the graph together as a set Ng. The state of the environment s E S transitions upon joint action a E A according to transition probability Pa
be the set of agents. The
AievA. Each agent i has a policy E IT; : S x A; - [0, 1], and we denote the joint policy of all agents as π E πT XI, For networked MARL, common and realistic assumption is that the reward of each agent just depends its action and the actions of its neighbors (Qu et al., 2020a), i.e., ri a) ri axç) ). Moreover, each agent i may only obtain partial observation o E O,, but can approximate the state by the observations of Ns (Jiang et al., 2020) or the observation history (Chu et al., 2020), which are all denoted by o, for simplicity. The global objective is to maximize the sum of cumulative rewards of all agents, i.e., Ere ΣN' 7/15.
A x S - [0, 1], where joint action set
3.2 MARKOV GAME
In such a setting, each agent can individually maximizes its own expected return, which is known as Markov game. This may lead to stable outcome or Nash equilibrium, which however is usually sub-optimal. Given ग. the value function of agent i is given by
(s) = Σ (aas)) pals' s, a)rra + yo (o)((s)) (s')l,
(1)
a
2

---

Under review as a conference paper at ICLR 2021
where Pa E Pa describes the state transitions. A Nash equilibrium is defined (Mguni et al., 2019)
(s)
(s) 2 us -- (s) VT E II,, S,
(2)
where n- = {jE)(())
4
METHOD
The basic idea of LToS is enable agents to learn how to share reward with neighbors such that agents are encouraged to collaboratively optimize the global objective in networked MARL. LToS decentralized hierarchy. At each agent, the high-level policy determines the weights of reward sharing based on low-level policies while the low-level policy directly interacts with the environ- ment optimize local objective induced by high-level policies. Therefore, they form bi-level optimization and alternately learn towards the global objective.
4.1 REWARD SHARING
The intuition of reward sharing is that agents share their rewards with others, each agent has to consider the consequence of its actions others, and thus it promotes cooperation. In networked MARL, as the reward of an agent is assumed to depend on the actions of neighbors, we allow reward sharing between neighboring agents.
For the graph of V. we additionally define a set of directed edges, D, constructed from &. Specif- for each agent and split each undirected edge Eij directed edges: dı = (i,j) and djs- = (j.i) E D. Each agent determines a weight wy E [0, 1] for each directed edge dij. Vj E N,, subject to the constraint ΣjEN, Wij 1, so that wiy proportion of agent i's environment reward r; will be shared to agent j. Let E W Xd. e EDyj be the weights of the graph. Therefore, the shaped reward after sharing for each agent is defined as
ically, we add a loop du
into two
Σ W. jEN
(3)
4.2 HIERARCHY
Assume there is joint high-level policy & 4: S W > [0, 1] to determine w. Given & and we can define the value function of π at each agent based on (1) as
D (s: Φ) Σ o(wls) Σ T(als, w) Σ Pa (s a) + + (s):
(4)
2o s: w. Σ Taass, w) Σ palsslss + + (s):
We express discrete action for simplicity. It also holds for continuous action as long change all the summations to integrals.
Let V2" (s; = EiEv oi (s; Φ)) and Q8 w; TT) = Eiev oi (s; Φ).
Proposition 4.1. Given n, V (s; T) and Q8 w; T) are respectively the value function and action-value function of Φb
Proof. Let r E. (als, wir?" and (s w) Ea (als, w)Pa(s'ls a). As commonly assumed the reward deterministie given s and a, from (4), we have.
0 (s:
Σ (bwls)
n w))s,
pa( a) (s):
(s'))
(6)
Σ Φ (w]s)
(s ()) + (s':
(7)
w
where Pwr Par S x W S [0, describes the state transitions given
3

---

Under review as a conference paper at ICLR 2021
Let r = Evev ; +
and from (7) we have
V (3:
ΣΣ Σ Pu w)(r? + (s: [))]
E Φ(w]s)
(8)
iEV
Σ ((wls
Pw (s Σ r +
o (s':
(9)
1EV
iEV
Σ
p(wls 8)
Pw Pw (s
w)2
(s':
(10)
and similarly,
(; ΣΣ
ss w)(? +7 Σ H(w'ls'') (s::
(11)
Σ Piol's w) Σ + + Σ Hw'ls |s') Σ
o (s': w Φ)]
(12)
icV
iEV
Euu(s' w) + Σ Jew (( w w';]
(13)
Moreover, from the definitions of r." and r. we have
π Tals, w)
rt
Σ π Talss w)
Σ Σ
Wjsfy
(14)
NEV
iEViEN:
= Σ x Tals, w)
Σ (i.))D
Wifri
Σ π (a|s, w) ri
Σ
(15)
iEV
Thus, given л, VT((s) and ( w) are respectively the value function and action-value function of Φ in terms of the sum of expected cumulative rewards of all agents, i.e., the global objective. D
Proposition 4.1 implies that & directly optimizes the global objective by generating w given π. Unlike existing hierarchical RL methods, we can directly construct the value function and action- value function of & based on the value function of π at each agent.
As & optimizes the global objective given π while n; optimizes the shaped reward individually each agent given & (assuming π convergent Nash equilibrium or stable outcome, denoted as lim), they form bi-level optimization. Let (T) and J=(Ø) denote the objectives of Φ and π respectively. The bi-level optimization can be formulated as follows.
max JT( +
(16)
s.l.
π T') arg lim (+))..
4.3 DECENTRALIZED LEARNING
Proposition 4.2. The joint high-level policy can be learned in a decentralized manner, and the decentralized high-level policies of all agents form a mean-field approximation of &b
Proof. Let diy E D serve vertex with action wi and reward WayT; in new graph G'. Each ver- tex has its own local policy Ø.y (Wiyls) and we can verify their independence by means of Markov Random Field. For Vi V. {dislū .M.) should form fully connected subgraph in G'. be- cause their actions are subject to the constraint ΣjEN, Wij = As di E g' only connects to (duilk E NGG(),, the fully connected subgraph is also a maximal clique. According to Hammers- ley- Clifford theorem (Hammersley & Clifford, 1971), we have (p(u(s) z [lsvv di di("(" [s), where wutt (wyb j Ai}.
Proposition 4.1 and 4.2 indicate that for each agent i, the low-level policy simply learns a local Ti Ti(0s|s (s, w where whth {wyilū N1). to optimize the cumulative reward of r since r!" is
4

---

Under review as a conference paper at ICLR 2021
fully determined by wt" according to (3) and denoted as r from now And the high-level policy 6 just needs to locally determine w to maximize the cumulative reward of r simplified rf.
Therefore, for decentralized learning, (16) can be decomposed locally for each agent i as
max
Tx()))
(17)
8.L. (()) arg max Jz, (TT 01 ( (*((T)))))))))
R;
We abuse the notation and let & and æ also denote their parameterizations respectively. To solve the optimization, we have
V se (o (T)). (x
(18)
Vo. Jo, (0- क. aV (b), UN + Vx (6)),
where a is the learning rate for the low-level policy. Let गं denote n; + a ni Jn, (Ø), we have
(0 xx)())
N Σ j=1
Ln, ", (19)
= Vo. (o- ... N +
v2
The second-order derivative is neglected due high computational complexity, without incurring significant performance drop such as in meta-learning (Finn et al., 2017) and neural architecture search (Liu et al., 2019). Similarly, have
V n. Js. (T (.. (NT(T)
(20)
JT, + 3V Jo, (T), ... ØN + 3V (ox())))))))))))))))))))))))))
where 3 is the learning rate of the high-level policy. Therefore, we can solve the bi-level optimiza- tion (16) by the first-order approximations in decentralized way. For each agent i, d; and mi
alternately updated.
In distributed learning, each agent i usually does not have access to state, we further approximate Φ, (u ss and n, (a,]s, w(")) by du(""" and ma(a;lo, w re- spectively. Moreover, in network MARL each agent i closely related to neighboring agents, (17) can be fur- ther seen T; maximizes the cumulative discounted re- ward of ri" given dw,, where Φx; = XjeN; oy. and ø; optimizes the cumulative discounted reward of r! given
agent
neighbors
d (uug" (a,)
naighbors
(a: lo anf"))
TA, (i.e, rf), where TA.. x Ty During training. TA, and dey; are implicitly considered by interactions of with and with respectively. The architecture of LToS is illustrated in Figure 1. At each timestep, the high-level policy of each agent makes a decision of action w as the weights of reward sharing based the observation.
gradient
data flow
environment
Figure 1: LToS
Then, the low-level policy takes the observation and with as an input and outputs the action. Agent obtains the shaped reward according to with for both the high-level and low-level policies. The gradients backpropagated along purple dotted lines.
Further, from Proposition 4.1, we have o." (s, ufth TN;)) u." (s; whth (w;)) where ofth is the action- value function of Φ; given TN;, 1 is the value function of given dov; and conditioned win. As aforementioned, we approximately have Shah (o,, wn(")) n (o:; w We can see that the action- value function of d; is equivalent to the value function of æ; That said, we can use a single network to approximate these two functions simultaneously. For a deterministic low-level policy, the high- level and low-level policies can share same action-value function. In the current instantiation of LToS, we use DDPG (Lillicrap et al., 2016) for the high-level policy and DGN (Jiang et al., 2020) (Q-learning) for the low-level policy. Thus, the Q-network of DGN also serves the critic of DDPG, and the gradient whth is calculated based on the maximum Q-value of a, More discussions about training LToS and the detailed training algorithm are available in Appendix A.I.
5

---

Under review as a conference paper at ICLR 2021
prisoner
(c) murting
rafficc
Figure 2: Three experimental scenarios: (a) prisoner, (b) traffic, and (c) routing.
5 EXPERIMENTS
For the experiments, we adopt three scenarios depicted in Figure 2. Prisoner is grid game about social dilemma that easily measures agents' cooperation, while traffic and routing are real-world scenarios of networked MARL. We obey the principle of networked MARL that only allows com- munication in neighborhood as Jiang et al. (2020); Chu al. (2020).
To illustrate the reward sharing scheme each agent learned, we use simple indicator: selfishness, the reward proportion that an agent chooses keep for itself. For ablation, we keep the sharing weights fixed for each agent, named fixed LToS. Throughout the experiments, we additionally compare with the baselines including DQN, DGN, QMIX and two methods for networked MARL, i.e., ConseNet (Zhang et al., 2018 8) and NeurComm (Chu et al., 2020), both of which take advantage of recurrent neural network (RNN) for the partially observable environment (Hausknecht maximize the average global reward directly, we specially tune the reward shaping factor of other baselines in prisoner and introduce QMIX as centralized baseline in traffic and routing. Moreover, DGN is the low-level policy of LToS, DGN also serves the ablation of LToS without reward sharing.
Stone, 2015). To
5.1 PRISONER
We use prisoner, a grid game version of the well-known matrix game prisoner's 's dilemma from Sodomka et al. (2013) to demonstrate that LToS is able to learn cooperative policies to achieve the global optimum (i.e. maximize globally averaged return). As illustrated in Figure 2a, there two agents A and B that respectively start two sides of the middle of a grid corridor with full observation. At each timestep, each agent chooses an action left or right and moves to corresponding adjacent grid, and each timestep every action incurs cost -0.01. There are three goals, two goals at both ends and one in the middle. The agent gets a reward +1 for reaching the goal. The game ends once This game resembles prisoner's dilemma: going for the middle goal ("defeect") will bring more rewards than the farther one on its side ("cooperate"). but if agents both adopt that, collision occurs and only one of the agents wins the goal with equal probability. On the contrary, both agents obtain a higher return if they both "cooperate", though takes more steps.
agent reaches goal or agents reach different goals simultaneously.
Figure 3 illustrates the learning curves of all the models in terms average return. Note that for all three scenarios, we represent the average of three training runs with different random seeds by solid lines and the min/max value by shad- owed areas. As a result of self-interest optimization, DQN converges to the "defect/deffett Nash equilibrium where each agent receives since it only aims to take advantage of its neighbors' observa- tions while prisoner is fully observable environment already. ConseNet agents sometimes choose to cooperate by building a consensus average return the beginning, but it is unstable
1.0
66
DON
expected reward about 0.5. So does DGN
Feed Lhy
Coopo
220
4.0
Figure 3: Learning curves in prisoner.

---

Under review as a conference paper at ICLR 2021
and abandoned subsequently. Given hand-tuned reward shaping factor to direct agents to maximize average return, NeurComm and fixed LToS agents are able to cooperate eventually. However, they converge much slower. Coco-Q (Sodomka et al., 2013) and LToS outperform all other methods. As a modified tabular Q-learning method, Coco-Q introduces the coco value (Kalai & Kalai, 2010) as substitute for the expected return in the Bellman equation and regards the difference transferred reward. However, it is specifically designed for some games, and it is hard to be extended beyond two-player games. LToS can learn the reward sharing scheme where one agent at first gives all the reward to the other so that both of them are prevented from "defect", and thus achieve the best av- erage return quickly. By prisoner, we verify LToS can escape from local optimum by learning to share reward.
5.2 TRAFFIC
In traffic, as illustrated in Figure 2b, we aim to investigate the capa- bility of LToS in dealing with highly dynamic environment through reward sharing. We adopt the same problem setting as in (Wei et al., 2019). In a road network. each agent serves as traffic signal con- trol at an intersection. The observation of an agent consists of a one-hot representation of its current phase (directions for red/green lights) and the number of vehicles on each incoming lane of the intersection. At each timestep, an agent chooses phase from the pre-defined phase set for the next time interval, i.e., 10 seconds. The reward is set to be the negative of the sum of the queue lengths of all approaching lanes at current timestep. The global objective is minimize average travel time of
Table I: Statistics of traffic flows
Time (second)
Arrival Ratc (vehicles/s)
0- 600
600 - 1, 200
1/4
1,200 - 1,800
1 1/3
1,800
2, 2,400
2
2,400
3, 3,000
1/5
3, 3,000
3, 3,0
1/2
all vehicles in the road network, which is equivalent to minimizing the sum of queue lengths of all intersections over episode (Zheng al., 2019). The experiment was conducted on traffic simu- lator, CityFlow (Zhang et al., 2019). We use a 6 x 6 grid network with 36 intersections. The traffic flows were generated simulate dynamic traffic flows including both peak and off- off-peak period, and the statistics is summarized in Table I.
Table 2: Average travel time of all the models in traffic
DQN
DGN
fixed LToS
LToS
NeurComm
ConseNet
QMIX
118.75
110.59
113.83
98.57
106.53
111.18
596.52
Figure 4 shows the learning curves of all the models in terms of average travel tiem of all vehicles in logarithmic form. The performance after convergence is summarized in Table 2, where LToS outperforms all other methods. LToS outperforms DGN, which demonstrates the reward sharing scheme learned by the high-level policy indeed helps to improve the coopera- tion of agents. Without the high-level policy, i.e., given fixed sharing weights, fixed LToS does not perform well in dynamic environment. This indicates the necessity of the high-level pol- icy. Although NeurComm and ConseNet both take advantage of RNN for partially observable environments, LToS still out- performs these methods, which verifies the great improvement of LToS in networked MARL. QMIX shows apparent instability and is confined suboptimality (Mahajan et al., 2019). Specifically, in the best episode, QMIX tries to release traffic flows from one direction while stopping flows from the other all the time.
DOA
LTcd
Ese L7G
ephote
Figure 4: Learning curves in traffic.
We visualize the variation of selfishness of all agents during an episodes in Figure 5 and 6. Figure 5 depicts the temporal variance of selfishness for each agent. For most agents, there are two valleys occurred exactly during two peak periods (i.e. 0- 600s and 1, 800 - 2, 400s). This is because for heavy traffic agents need to cooperate more closely, which can be induced by being less selfish. We can see this from the fact that selfishness is even lower in the second valley where the traffic is even heavier (i.e. 2 vs.. vehicles/s). Therefore, this demonstrates that the agents learn to adjust their extent of cooperation to deal with dynamic environment by controlling the sharing weights. Figure 6 shows the spatial pattern of selfishness at different timesteps, where the distribution of agents is the same the road network in Figure 2b. The edge and inner agents tend have very
7

---

Under review as a conference paper at ICLR 2021
Figure 5: Temporal pattern of selfishness
Figure Spatial pattern of selfishness
different selfishness. addition, inner agents keep their selfishness more uniform during off-peak periods, while they diverge and present cross-like patterns during peak periods. This shows that handling heavier traffic requires more diverse reward sharing schemes among agents to promote more sophisticated cooperation.
5.3 ROUTING
Packet routing is regarded complex problem in distributed com- puter networks. Here simplified version of the problem. net- work consists of multiple routers with stationary network topol- ogy. Data packets come into the network (started at router) fol- lowing the Poisson distribution, and the arrival rate varies during episode as summarized in Table Each router has a FIFO queue the packet buffer. For simplicity, assume that each queue has unlimited volume allowance, and each packet has a size same as each link's bandwidth. At every timestep, each router observes the data packets in the queue and incoming links well as indices of neighboring routers, forwards the first packet in the FIFO to the selected next hop, and obtains reward which is the negative of the queue length. The transmission time of packet over link is proportional to the geographic distance, and the packet will be stored after arriving at the next hop unless it reaches the destination. The delay of a packet is the sum of timesteps spent the routers and on the links. The goal of packet routing is to send the packets to their destinations through hop-by-hop transmissions with minimum average delay. Compared with traffic, routing a more fine-grained task, because it requires specific control for each data packet.
Table Statistics of packet flow
Time
Arrival
(timestep) (packets/timestep)
100
1
100 200
10/3
200
300
1
In the experiment, we choose a real network topology: IBM backbone network of 18 vertices that each works for city in North America (Knight al., 2011) and the topology is de- picted in Figure 2c, where each edge consists of two unidirec- tional links and varies considerably in distance. We assume that each router helps with loopback detection while forward- ing. Figure 7 illustrates the learning curves of all the models terms of average delay, and their performance after conver- gence in terms of throughout and delay is also summarized in Table NeurComm, ConseNet and QMIX are not up this task and may need much more episodes to converge. By learn- ing proper reward sharing, LToS outperforms all other base- lines in terms of both metrics. Compared to traffic, routing additionally considers the heterogeneous network topology. Therefore, the experimental results also verify the capability of LToS of handling both temporal and spatial heterogeneity in networked MARL.
1755
SeaOCem
150
250
Figure 7: Learning curves routing.
Table 4: Performance of all models in routing: throughput (packets) and average delay (timesteps)
DQN
DGN
fixed LToS
LToS
NeurComm
ConseNet
QMIX
throughput
297.69
299.24
304.99 89,50
311.50 86.71
116.53 122.68
185.32 111.87
218.79 105.74
delay
91.06
90.96
8

---

Under review as a conference paper at ICLR 2021
6 CONCLUSION
In this paper, we proposed LToS, a hierarchically decentralized method for networked MARL. LToS enables agents to share reward with neighbors so as encourage agents to cooperate on the global objective. For each agent, the high-level policy learns how to share reward with neighbors to decom- pose the global objective, while the low-level policy learns to optimize local objective induced by the high-level policies in the neighborhood. Experimentally, we demonstrate that LToS outperforms existing methods in both social dilemma and two networked MARL scenarios.
REFERENCES
Jacopo Castellini, Frans A Oliehoek, Rahul Savani, and Shimon Whiteson. The representational capacity action-value networks for multi-agent reinforcement learning. In AAMAS, 2019.
Tianshu Chu, Sandeep Chinchali, and Sachin Katti. Multi-agent reinforcement learning for net- worked system control. In ICLR, 2020.
E. Dall' Anese, H. Zhu, and G. B. Giannakis. Distributed optimal power flow for smart microgrids. IEEE Transactions on Smart Grid, 4444:1664 2013.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. In ICML, 2017.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018.
M. Hammersley and Clifford. Markov fields on finite graphs and lattices, 1971.
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. 1eXiv:1507.0655 2015.
Edward Hughes, Joel Z. Leibo, Matthew G. Phillips, Karl Tuyls, Edgar A. Duznez-Guzmán, Anto- nio Garefa Castañeda, lain Dunning. Tina Zhu, Kevin McKee, Raphael Koster, Heather Roff, and Thore Graepel. Inequity aversion improves cooperation in intertemporal social dilemmas. In NeurIPS, 2018
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. ICLR, 2020.
Adam Tauman Kalai and Ehud Kalai. Cooperation and competition in strategic games with private information. In EC, 2010.
Knight, H.X. Nguyen, N. Falkner, R. Bowden, and M. Roughan. The internet topology zoo. IEEE Journal on Selected Areas in Communications, 2969): -1775, 2011.
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In ICLR, 2016.
Hanxiao Liu. Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In ICLR, 2019.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In NewrIPS, 2019.
David Mguni, Joel Jennings, Emilio Sison, Sergio Valcarcel Macua, Sofia Ceppi, and En- rique Munoz de Cote. Coordinating the crowd: Inducing desirable equilibria in non-cooperative systems. In AAMAS, 2019.
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani. Lenient multi-agent deep rein- forcement learning. In AAMAS, 2018.

---

Under review as a conference paper at ICLR 2021
Julien Pérolat, Joel Z Leibo, Vinicius Zambaldi, Charles Beattie, Karl Tuyls, and Thore Graepel. A multi-agent reinforcement learning model of common-pon mommonoooool resource appropriation. In NeurlPS, 2017.
Alexander Peysakhovich and Adam Lerer. Consequentialist conditional cooperation in social dilem- mas with imperfect information. In ICLR, 20.
Alexander Peysakhovich and Adam Lerer. Prosocial learning agents solve generalized stag hunts better than selfish ones. In AAMAS, 2018b.
Chao Qu, Hui Li, Chang Liu, Junwu Xiong, James Zhang, Wei Chu, Yuan Qi, and Le Song. Intention propagation for multi-agent reinforcement learning. arXiv:2004.08883 08888, 2020a.
Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi-agent reinforcement learning for networked systems with average reward. In NeurIPS, 2020b.
Tabish Rashid, Mikayel Samvelyan. Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforce- ment learning. In ICML., 2018
Eric Sodomka, Elizabeth Hilliard, Michael Littman, and Amy Greenwald. Coco-q: Learning in stochastic games with side payments. In ICML, 2013.
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 ICML, 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning based on team reward. In AAMAS, 2018.
Jianhong Wang, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. Shapley q-value: local reward approach to solve global reward games. In AAAI, 2020.
Hua Wei, Nan Xu, Huichu Zhang, Guanjie Zheng, Xinshi Zang, Chacha Chen, Weinan Zhang, Yanmin Zhu, Kai Xu, and Zhenhui Li. Colight: Learning network-level cooperation for traffic signal control. In CIKM, 2019.
Yue Xu, Zengde Deng, Mengdi Wang, Wenjun Xu, Anthony Mancho So, and Shuguang Cui. Voting- based multi-agent reinforcement learning for intelligent iot. urXiv:1907.01333 2019.
Huichu Zhang, Siyuan Feng, Chang Liu, Yaoyao Ding, Yichen Zhu, Zihan Zhou, Weinan Zhang, Yong Yu, Haiming Jin, and Zhenhui Li. Cityflow: A multi-agent reinforcement learning environ- ment for large scale city traffic scenario. In WWW, 2019.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi- agent reinforcement learning with networked agents. In ICML, 2018.
Guanjie Zheng, Xinshi Zang, Nan Xu, Hua Wei, Zhengyao Yu, Vikash Gayah, Kai Xu, and Zhenhui Li. Diagnosing reinforcement learning for traffic signal control. arXiv:1905.04716, 2019.
A APPENDIX
A.1 ALGORITHM AND DISCUSSIONS
As hierarchically decentralized MARL method, LToS brings challenges for training. Algo- rithm 1 presents the training algorithm of LToS.
Selfishness Initializer. On the basis of straightforward idea that one should generally focus more on its own reward than that of others when optimizing its own policy, the initial output of each high-level policy network is supposed to be higher the sharing weight of its own than others. We
10

---

Under review as a conference paper at ICLR 2021
Algorithm LToS
1: Initialize de parameterized by 9; and parameterized by μ4 for each agent (Ø; is learned using DDPG and n; is learned using DGN, where they share the Q-network)
2: for episode 1 to max-training-round do
3: Initialize a random process X for w-action exploration
4: Initialize random process 2 for d-action exploration for max-episode-lenge for each agent do u:: + Φ:(0:) + X'
5:
do
6:
7:
8:
a; f [o; w(t) + 2
9:
Execute action a, obtain original reward rss and transition to of Exchange uha and ra and get wit and r:
10:
11:
Store (0;. w." 0g, r .o)
end for
13:
if time to update then
for each agent do Sample minibatch D {(ot, wi",, at, 74,77" ((,,)" from replay buffer B, Exchange wpni d((o() and get wt
15:
Set 34 + r:" + (d/, al; wp" ( )a(=);((o(ru")) Update π,, by V Di Eion bor.uffaa arrr of)eD 0,¹ (o;, (0, as; )²
17:
18:
19:
Exchange with +- (0;))) and get w."h
20:
Calculate the gradient 9," Varg (o,, arg max,, 9 w!!!)
21:
Exchange o and get gradient gfth for unan 1
22:
Update 0g by (D] Eo,eD (Vo, (o(:))
Softly update 0 and p\: 02 + T0, + (1-r)0; and μl t Tpt + (1- T)p
24:
end for
end if
26: end for
27: end for
choose to predetermine the initial selfishness to learn the high-level policy effectively. However, with normal initializers, the output of the high-level policy network will be evenly distributed initially. Therefore, we use special selfishness initializer for each high-level policy network instead. As we use the softmax to produce the weights, which guarantees the constraint: ΣjEN; Way = 1, Vi E V, we specially set the bias of the last fully-connected layer so that each decentralized high-level policy network tends keep for itself the same reward proportion the given selfishness initially. The rest of reward is still evenly distributed among neighbors. LToS learns started from such initial weights, while fixed LToS uses such weights throughout each experiment. Moreover, use grid search to find the best selfishness for fixed LToS in traffic and routing. For prisoner we deliberately set the selfishness to 0.5 so that fixed LToS directly optimizes the average return.
Unified Pseudo Random Number Generator. LToS is learned in decentralized manner. This incurs some difficulty for experience replay. As each agent needs w to update network weights for both high-level and low-level policies, it should sample from its buffer batch of experiences where each sampled experience should be synchronized across the batches all agents (i.e,, the experiences should be collected unified pseudo random number generator and the same random seed.
same timestep). To handle this, all agents can simply use
Different Time Scales. As many hierarchical RL methods do, running at a slower time scale than the low-level one. Proposition 4.1 still holds if we expand ez for more than one step forward. Assuming the high-level policy runs every M timesteps, can fix M M is referred to action interval in Table 6.
the high-level policy to
w ouut w 0-
Infrequent Parameter Update with Small Learning Rate. Based on the continuity of w. a small modification of means slight modification of local reward functions, and will intuitively result

---

Under review as a conference paper at ICLR 2021
Table 5; Hyperparameters for DQN and DGN (also the low-level policy network of LToS)
Hyperparamater
Prisoner
Traffic
Routing
sample
10
1,000
batch size
buffer capacity
200,000
10,000
200,000
e/decay/minimum value
0.8/1/0.8
0.4/0.9/0.00
0.2/0.98/0
initializer
random normal
random normal
random normal
optimizer learning rate
Adam
Adam
Adam
Ic-3
lc-3
Ic-3
?
0.99
0.99
7 for soft update
0.1
0.1
0.1
MLP units MLP activation
32
32
128
ReLU
ReLU
ReLU
# encoder MLP layers attention heads for DGN convolutional layers DGN
2
2
2
4
Table 6: Hyperparameters for the high-level policy network of LToS
Hyperparamater
Prisoner
Traffic
Routing
update frequency
step
episodes
20 episodes
action interval sample size batch size
step
15 steps
steps
2,000
1,000
2,000
32
20
32
noise for exploration
6 Gaussian
OU
OU
noise parameter
0.8, =1
0.25c
0.025e
initializer initial selfishness
selfishness 0.5
selfishness
selfishness
0.8
0.9
optimizer
SGD
SGD
SGD
learning rate
le-1
le-3
le-3
last MLP layer activation
softmax
softmax
sofimax
Table 7: Hyperparamettes NeurComm, ConseNet and QMIX
Hyperparamater
Prisoner
Traffic
Routing
initializer
orthogonal RMSProp
orthogonal RMSProp 5e-4
orthogonal
optimizer
RMSProp
learning rate
5c-3
5c-4
# MLP units MLP activation cell state units
20
16
128
ReLU
ReLU
ReLU
20
16
128
hidden state units
20
16
128
RNN type NeurComm and ConseNet
LSTM
LSTM GRU
LSTM
RNN type for QMIX hypemetwork layerl units for QMIX
GRU
36 x 16 16
18 x 128 128
hypemetwork layer2 units for QMIX for NeurComm
0.1
0.05
in an equally slight modification of the low-level value functions. This guarantees the low-level policies are highly reusable.
A.2 HYPERPARAMATERS
Table 5 summarizes the hyperparameters of DQN and DGN that also serves as the low-level network of LToS. We follow many of the original DGN in prisoner and routing, but choose the setting of Wei et al. (2019) in traffic for consistency. Table 6 summarizes the hyperparameters of the high- level network of LToS, which different from the low-level network. Table 7 summarizes the
12

---

Under review as a conference paper at ICLR 2021
hyperparameters of NeurComm and ConseNet, which adhere to the implementation (Chu et al., 2020). In addition, for tabular Coco-Q, the step-size parameter 0.5. We adopt soft update for both high-level and low-level networks and use Orntein-UUlenbedd Process (abbreviated as OU) for high-level exploration.
Both fixed LToS and NeurComm exploit static reward shaping, but they adopt different reward shaping schemes which are hard to compare directly. We consider a simple indicator: Self Neighbor Ratio (SNR), the ratio of reward proportion that agent chooses keep for itself to that obtains from a single neighbor. As the rest reward is evenly shared with neighbors in LToS, for each agent i, we have SNR selisshnexx/ssellidbneee
([NG) 1) for LToS, and SNR 1/a for NeurComm where is the spatial discount factor. We adjust the initial selfishness and a to set the SNR of both methods the same level for fair comparison.
13


Reviews:
[{"review_id": "gvJLIDDlYrL", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\nThe paper considers the cooperative MARL setting where agents get local rewards and they are interconnected as a graph where neighbors can communicate. The paper specifically considers the communication of reward sharing, that is, an agent shares (part of) its reward to its neighbors, such that each agent optimizes its local reward plus rewards from its neighbors. This motivates a bi-level optimization framework where the high-level policy decides how the rewards are shared and the low-level policy locally optimizes the shared rewards given the high-level’s decision. The paper’s flow motivates such a framework well. The experimental results demonstrate the method’s effectiveness. I think it is a strong paper (accept), but my confidence is low due to the following confusions I have.\n \nComments/Questions\n \n1. I have a high-level comment on the reward sharing mechanism. It seems that the proposed method does not support multi-hop sharing because rewards can only be shared to neighbors. Why is this single-hop sharing effective in the experiments? Is it because of domain-specific reasons, or it’s because that single-hop sharing is in principle equally effective, why?\n\n2. The derivation of (18) using taylor expansion is unclear to me. Could the authors explain it with more details?\n\n3. I don’t fully understand the proof of Proposition 4.2. Specifically, does “phi can be learned in a decentralized manner” mean that the *optimal* phi can be based on only the local observation for each agent, instead of based on global state? Could the authors comment on the approximation error induced by the mean-field approximation? Why the proof begins with phi_i based on o_i and ends with phi_i based on global state s.\n\n4. In Equation (17) and (20), should phi^* be just phi (i.e. no * here)?\n\n5. The low-level policy is to optimize the shared rewards. My understanding is that any (single-agent) RL algorithm can be used for optimizing the shared rewards, e.g. DQN, DDPG, A2C, etc. Why would the authors choose DGN, a rather less popular RL algorithm? Have the authors tried more popular algorithms as the low-level policy?\n\n6. For fixed LToS,  how do we determine the fixed sharing weights?\n\n---\nThanks for the response. I've increased my confidence. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "b9O_b_yBHBo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper addresses multi-agent RL problems by presenting a decentralized approach where the agents learn to share their reward with their neighbors. In this method, a high-level policy determines a weight vector for weighting the reward of neighboring agents, and then each agent learns their own independent policy. The learning is thus conducted locally in a partially connected network toward a common goal and without the knowledge of global state and actions.\n\nOverall, the approach is intuitive and interesting for decentralized learning in MARL tasks. However, I have some comments/questions for improving the paper that are summarized below.  Hence, I vote to reject at this stage.\n\nPros:\n+ Intuitive design of communication among agents in decentralized setting\n+ Clever adaption of algorithms\n+ Well written paper and properly organized\n\nComments:\n- The contribution of the paper is mainly in formulating the problem in the actor-critic setup of DDPG method which leads to a limited novelty.\n\n- A key concern about the paper is how to decompose the reward in the first place. The paper aims at optimizing a global objective and assumes (also in the propositions) that this objective has additive connection with the decentralized rewards. Nevertheless, this is a strong assumption, particularly in real-world applications. A global reward can be decomposed into summation of smaller rewards, but not necessarily the other way around. As long as there is a global objective, we need a way to distribute the reward among the agents via learning or reward reshaping (or even manually). How can we properly define the reward of each agent in such scenarios?\n\n- It is also unclear what is the benefit of sharing only with the neighbors. The method learns a weight vector of size |N_i| for every agent. Does it make a difference in the architecture/algorithm if we learn the weights of all the other agents (size |N|) instead?\n\n- Formulating the weights as finite discrete values looks unnatural. If the method is designed for continuous action space, it is expected to have the notations to be continuous as well. Can we just simply convert the summations into integration in the propositions!?\n\n- The authors claim that the problem with the related work is that they can not scale up with the number of agents. However, there is no (empirical) support that how the proposed approach deals with large-scale problems.\n\n- In general, the experiments are small and based on simulation, and simulated scenarios are not considered real-world (which is claimed otherwise in the paper). I would recommend to incorporate more supportive empirical evaluation.\n\n\nMinor:\nWhat is \\phi_{-i} in eq 17", "extra_scores": {}, "extra_text": {}}, {"review_id": "60wI5bcMhON", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper present a new method, called LToS which enables agents to share rewards in MARL. Two levels of policies, high-level and low-level, determines rewards and optimize global objectives. Three diverse scenarios were used to test the performance of LToS compared to other baseline methods. LToS consistently outperforms other methods. In the second scenario, authors also show the need for high-level policy by introduction fixed LToS. \n\n- At the end of Introduction, the sentence ‘LToS is easy to implement and currently realized by DDPG…’ can be misleading because of the word ‘realized’ and the fact that authors argue that LToS is a newly proposed method. Does this mean LToS simply combines DDPG and DGN?\n- Do Figure 5 and 6 represent selfishness of agents when LToS is used?\n- Minor editorial errors in Appendix", "extra_scores": {}, "extra_text": {}}, {"review_id": "2J1Lj5YxCeI", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Update: I appreciate the detailed replies to my questions. Indeed, some of the points I raised were addressed well and the paper updated accordingly. \n\nHowever, some new concerns were also raised by the replies:\n- Using 3 seeds for the experimental evaluation is an extremely questionable evaluation protocol. There is no way to know if any of the results are going to hold up. \n- It's also clear now that none of the experiments are comparing to benchmark numbers from other publications. It would have been more confidence inspiring if the method was tested on a set of tasks where external benchmarks have already been established. \n- This is particularly true for the new results that were added to the paper, e.g. the QMIX results. It's difficult to make sense of them and the instability points towards a potential hyperparameter issue.   \n- All baselines for the 'prisoners' case should at least compare to the fully cooperative case of adding up the rewards. Comparing to a DQN baseline that maximizes individual rewards is a red herring. \n- It's odd that all experiments require less than 1000 episodes to train. This is very unusual for challenging multi-agent RL problems. It would be great to understand if the main selling point of LToS is sample-complexity/learning speed or if there is something else going on.\n\nI also agree with the concern raised by other reviewers that the paper is currently not positioned clearly. \nAll things considered, I believe my score is still appropriate for the paper. However, I also believe that a future version of the paper with clarified positioning and more thorough experimental evaluation could make for a compelling contribution.\n\nOriginal review:\n==========\n-\"Obviously, CTDE cannot address such problems due to the curse of dimensionality.\". CTDE means that there is the *option* to use centralized information at training time. Clearly, some ways of using centralized information will scale better than others and claiming that none of them scale is simply unfounded. \n\n-\"One is that the reward function.. tragedy of the commons.\". I am struggling to make sense of this paragraph. Please work on the clarity of the writing. \n\n-\"However, they are learned in a centralized way and hence not scalable.\" These methods have been scaled to large numbers of agents in complex environments. Please provide citations when making a claim that something doesn't scale. For example, the \"The StarCraft Multi-Agent Challenge\", Samvelyan et al 2020, includes results for numbers of agents comparable to the largest experiments in this paper.  \n\n-\"Moreover, the observation of each agent oi ∈ Oi can be enhanced to the Cartesian product of agent i and its neighbors (Jiang et al.,\n2020) or the observation history (Chu et al., 2020)\". I don't follow this. If the observation of each agent includes the observation of all neighbors (which includes the observation of their neighbors), then shouldn't everyone observe everything? \n\n-Equation (1) is wrong. The left-hand side conditions on 'oi_', but the right-hand side conditions on 's'. This also affects all following equations. \n\n-\"The simple way to optimize the global objective is that each agent maximizes its own expected return, which is known as Markov game. \". This is wrong. When each agent optimizes their own expected return this is typically not a means of optimizing the global objective. \n\n-\". In networked MARL, as the reward of an agent is assumed to depend on the actions of neighbors, we allow reward\nsharing between neighboring agents\": The reward function also depends on the global state, 's', which is a function of the joint action of all of the agents. So this local reward sharing seems clearly insufficient in general. \n\n- Eqn 6 to 15: This proof seems unnecessarily cumbersome. W only redistributes the rewards, so the sum of total rewards is unchanged, qed.\n\n-\"Unlike existing hierarchical RL methods, we can directly construct the value function and action value function of φ based on the value function of π at each agent.\": Constructing the value function isn't really the problem, but approximating and learning it is challenging.\n\nTheory:\n-4.3: \"Each vertex has its own local policy φij (wij |oi), and we can verify their independence by means of Markov Random Field.\" This is not clear to me. Furthermore, given that the transition function conditions on the joint action and that the reward function depends on the central state, this seems wrong. Unless I am mistaken, the dependency on the central state should break any locality assumptions. \n\nExperiments:\n- The results on the prisoner's dilemma are misleading. Clearly, if there is an ability to change the reward functions of individual agents (which is assumed by LToS), there is no more social dilemma. As such, only baselines that maximize the total reward are credible comparisons (and seem to be missing completely). \n- The \"traffic\" and \"ROUTING\" experiments seem more interesting. A few caveats: None of the results include uncertainty estimates. It is furthermore unclear, how many seeds were used. Furthermore, the fixed LToS baseline (\"For ablation, we keep the sharing weights fixed for each agent, named fixed LToS\") seems odds. Did you try a baseline where all agents simply share their reward equally with their neighbors? Also, centralized baselines are missing. E.g: https://arxiv.org/pdf/1910.00091.pdf. \n- In \"ROUTING\" Fixed LToS (ie. not learning to share) and LToS seem indistinguishable. \n\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-JHJijUyJE4", "reviewer": "AnonReviewer5", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a hierarchical multi-agent reinforcement learning method for the restricted communication setting and verifies the algorithm performance in a number of useful applications. The hierarchical approach to the networked MARL problem proves novel, effective, and interesting.\n\n+ Strengths:\n\n+ The work targets an arguably less explored area by focusing on the restrictions on inter-agent communication that may be present in realistic scenarios.\n\n+ Evaluation setup is varied, explained in detail and visualized in an intuitive manner.\n\n+ Niche is well-identified, and the contribution is clear.\n\n\n- Major Concerns:\n\n- The reviewer had issues positioning the paper among the different lines of research. Although the research gap itself is clear (scalable MARL methods in a restricted communication setting), it isn't obvious why and how relevant the cited works are. For example, mentioning VDN, QMIX, and QTRAN (which together are some of the latest works in the factorization methods) does not seem to serve any further purpose, as they are no longer compared quantitatively or qualitatively to LToS. The authors' claim that they are not scalable leads the reviewer to anticipate that LToS naturally is scalable, but there appears to be no evidence whatsoever presented in the latter sections of the paper to show, let alone prove, the superior scalability of LToS, with, for example, growing numbers of agents and training times.\n\n-  Furthermore, some of the cited works have been left out at the evaluation stage, which leaves the reviewer puzzled as to which baselines LToS really hopes to outshine. The work needs some justification over why the following studies have not been compared to in the evaluation:\n\nIf the main strength of LToS lies in its capability to function effectively and efficiently in restricted communications setting, comparison to one or more of the following works should be of great advantage in illustrating that edge:\nDIAL/RIAL by  Foerster 2016 - Learning to Communicate with Deep Multi-Agent Reinforcement Learning\nBiCNet by Peng 2017 arXiv - Multiagent Bidirectionally-Coordinated Nets\nCommNet by Sukhbaatar 2016 NeurIPS - Learning Multiagent Communication with Backpropagation\nIC3Net by Singh 2019 ICLR - Learning When to Communicate at Scale in Multiagent Cooperative and Competitive Tasks\nSchedNet by Kim 2019 ICLR - Learning to Schedule Communication in Multi-agent Reinforcement Learning\n\nIf the main strength of LToS lies in its capability to resolve selfishness and assign credits appropriately to bring about a harmonious cooperation in social dilemmas, analysis with respect to the this work should be helpful:\nEccles 2019 CoRR - Learning Reciprocity in Complex Sequential Social Dilemmas\n\nIt would be interesting to draw some parallels between LToS and BAD, as both draw inspiration from a hierarchical decomposition:\nBAD by Foerster 2019 ICML - Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning\n\nThis recent AAMAS paper is based on peer evaluation and exchanging evaluation messages computed from recently obtained rewards:\nPED-DQN by Hostallero 2020 AAMAS - Inducing Cooperation through Reward Reshaping based on Peer Evaluations in Deep Multi-Agent Reinforcement Learning\nSome of the potential issues to discuss are: bandwidth usage of message exchange, message overhead in sharing the neighbors' rewards.\n\nUsing neighbors' information to achieve scalability in MARL most likely requires discussion of mean-field methods, such as:\nYang 2018 ICML - Mean Field Multi-Agent Reinforcement Learning.\n\n- Going through the Appendices spurred a great deal of curiosity, as the authors mention that all agents share the same, synchronized random number generator with the same seed across all the agents. This leads me to believe that the philosophy of decentralized learning is lost in LToS. Synchronization is definitely not cost-free; all the more so if the synchronized RNG is used to sample an experience from the agents' replay buffers. How do the agents synchronize their RNG in a decentralized manner?\n\n- In the Routing evaluation. has overhead been taken into account? How does LToS fare with respect to varied communications channel? What if the network were sparser? Do you observe any trends as you vary the extent of network connectivity?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although there was some initial disagreement on this paper, the majority of reviewers agree that this work is not ready for publication and can be improved in various manners. After the discussion phase there is also serious concern that the experiments need more work (statistically), to verify if they hold up. More comparisons with baselines are required as well. The paper could also be better put in context with the SOTA and related work. The paper does contain interesting ideas and the authors are encouraged to deepen the work and resubmit to another major ML venue.
Decision: Reject