MULTI-AGENT REINFORCEMENT LEARNING FOR NETWORKED SYSTEM CONTROL
Year: 2020

Abstract:
This paper considers multi-agent reinforcement learning (MARL) in networked system control. Specifically, each agent learns a decentralized control policy based on local observations and messages from connected neighbors. We formulate such a networked MARL (NMARL) problem as a spatiotemporal Markov decision process and introduce a spatial discount factor to stabilize the training of each local agent. Further, we propose a new differentiable communication protocol, called NeurComm, to reduce information loss and non-stationarity in NMARL. Based on experiments in realistic NMARL scenarios of adaptive traffic signal control and cooperative adaptive cruise control, an appropriate spatial discount factor effectively enhances the learning curves of non-communicative MARL algorithms, while NeurComm outperforms existing communication protocols in both learning efficiency and control performance.

text: This paper considers multi-agent reinforcement learning (MARL) in networked system control. Specifically, each agent learns a decentralized control policy based on local observations and messages from connected neighbors. We formulate such a networked MARL (NMARL) problem as a spatiotemporal Markov decision process and introduce a spatial discount factor to stabilize the training of each local agent. Further, we propose a new differentiable communication protocol, called NeurComm, to reduce information loss and non-stationarity in NMARL. Based on experiments in realistic NMARL scenarios of adaptive traffic signal control and cooperative adaptive cruise control, an appropriate spatial discount factor effectively enhances the learning curves of non-communicative MARL algorithms, while NeurComm outperforms existing communication protocols in both learning efficiency and control performance.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL), formulated as a Markov decision process (MDP), is a promising data-driven approach for learning adaptive control policies (Sutton & Barto, 1998). Recent advances in deep neural networks (DNNs) further enhance its learning capacity on complex tasks. Successful algorithms include deep Q-network (DQN) (Mnih et al., 2015), deep deterministic policy gradient (DDPG) (Lillicrap et al., 2015), and advantage actor critic (A2C) (Mnih et al., 2016). However, RL is not scalable in many real-world control problems. This scalability issue is addressed in multi-agent RL (MARL), where each agent learns its individual policy from only local observations. However, MARL introduces new challenges in model training and execution, due to non-stationarity and partial observability in a decentralized MDP from the viewpoint of each agent. To address these challenges, various learning methods and communication protocols are proposed to stabilize training and improve observability.
This paper considers networked MARL (NMARL) in the context of networked system control (NSC), where agents are connected via a communication network for a cooperative control objective. Each agent performs decentralized control based on its local observations and messages from connected neighbors. NSC is extensively studied and widely applied. Examples include connected vehicle control (Jin & Orosz, 2014), traffic signal control (Chu et al., 2019), distributed sensing (Xu et al., 2018), and networked storage operation (Qin et al., 2016). We expect an increasing trend of NMARL based controllers in the near future, after the development of advanced communication technologies such as 5G and Internet-of-Things.
Recent works studied decentralized NMARL under assumptions of global observations and local rewards (Zhang et al., 2018; Qu et al., 2019), which are reasonable in multi-agent gaming but not suitable in NSC. First, the control infrastructures are distributed in a wide region, so collecting global observations in execution increases communication delay and failure rate, and hurts the robustness. Second, online learning is not common due to safety and efficiency concerns. Rather, each model is trained offline and tested extensively before field deployment. In online execution, the model only runs forward propagation, and its performance is constantly monitored for triggering re-training. To reflect these practical constraints in NSC, we assume 1) each agent is connected to a limited number
of neighbors and communication is restricted to its neighborhood, and 2) training is offline and global information is available in rollout training minibatches, despite a decentralized training process.
The contributions of this paper are three-fold. First, we formulate NMARL under the aforementioned NSC assumptions as a decentralized spatiotemporal MDP, and introduce a spatial discount factor to stabilize training, especially for non-communicative algorithms. Second, we propose a new neural communication protocol, called NeurComm, to adaptively share information on both system states and agent behaviors. Third, we design and simulate realistic NMARL environments to evaluate and compare our approaches against recent MARL baselines. 1

heading: 2 RELATED WORK
text: MARL works can be classified into four groups based on their communication methods. The first group is non-communicative and focuses on stabilizing training with advanced value estimation methods. In MADDPG, each action-value is estimated by a centralized critic based on global observations and actions (or inferred actions) (Lowe et al., 2017). COMA extends the same idea to A2C and estimates each advantage using a centralized critic and a counterfactual baseline (Foerster et al., 2018). In Dec-HDRQN (Omidshafiei et al., 2017) and PS-TRPO (Gupta et al., 2017), the centralized critic takes local observations, but the parameters are shared globally. In the NMARL work of Zhang et al. (2018), the critic is fully decentralized but each takes global observations and performs consensus updates. In this paper, we empirically confirm that a spatial discount factor helps stabilize the training of non-communicative algorithms under neighborhood observation.
The second group considers heuristic communication protocols or direct information sharing. Foerster et al. (2017) shows performance gains with directly-shared low dimensional policy fingerprints from other agents. Similarly, mean field MARL takes the average of neighbor policies for informed action-value estimation (Yang et al., 2018). The major disadvantage of this group is that, unlike NeurComm, the communication is not explicitly designed for performance optimization, which may cause inefficient and redundant communications in execution.
The third group proposes learnable communication protocols. In DIAL, the message is generated together with action-value estimation by each DQN agent, then it is encoded and summed with other input signals at the receiver side (Foerster et al., 2016). CommNet is a more general communication protocol, but it calculates the mean of all messages instead of encoding them (Sukhbaatar et al., 2016). Both works, especially CommNet, incur an information loss due to aggregation on input signals. Another collection of works focuses on communications in strategy games. In BiCNet (Peng et al., 2017), a bi-directional RNN is used to enable flat communication among agents, while in MasterSlave (Kong et al., 2017), two-way message passing is utilized in a hierarchical RNN architecture of master and slave agents. In contrast to existing protocols, NeurComm 1) encodes and concatenates signals, instead of aggregating them, to minimize information loss, and 2) includes policy fingerprints in communication to reduce non-stationarity.
The fourth group focuses on communication attentions to selectively send messages. ATOC (Jiang & Lu, 2018) learns a soft attention which allocates a communication probability to each other agent, while IC3Net (Singh et al., 2018) learns a hard binary attention which decides communicating or not. These works are especially useful when each agent has to prioritize the communication targets. NMARL is less likely the case since the communication range is restricted to small neighborhoods.

heading: 3 SPATIOTEMPORAL RL
text: This section formulates the NMARL problem as a decentralized spatiotemporal MDP, and introduces the spatial discount factor to reduce its learning difficulty. To simplify the notation, we assume the true system state is observable, and use “state” and “observation” interchangeably. This does not affect the validity of proposed methods in practice. To save space, all proofs are deferred to A.
1Code link: https://github.com/cts198859/deeprl_network.

heading: 3.1 NETWORKED MARL
text: The networked system is represented by a graph G(V, E) where i ∈ V is each agent and ij ∈ E is each communication link. The corresponding MDP is characterized as (G, {Si,Ai}i∈V , p, r) where Si and Ai are the local state space and action space of agent i. Let S := ×i∈VSi and A := ×i∈VAi be the global state space and action space, MDP transitions follow a stationary probability distribution p : S × A × S → [0, 1], and global step rewards be denoted by r : S × A → R. In a multi-agent MDP, each agent i follows a decentralized policy πi : Si × Ai → [0, 1] to chose its own action ai,t ∼ πi(·|si,t) at time t. The MDP objective is to maximize E[Rπ0 ], where Rπt = ∑T τ=t γ
τ−trτ is the long-term global return with discount factor γ. Here the expectation is taken over the global policy π : S×A → [0, 1], the initial distribution st ∼ ρ, and the transition sτ+1 ∼ p(·|sτ , aτ ), regarding the step reward rτ = r(sτ , aτ ), ∀τ < T , and the terminal reward rT = rT (sT ) 2. The same system can be formulated as a centralized MDP. Defining V π(s) = E[Rπt |st = s] as the state-value function and Qπ(s, a) = E[Rπt |st = s, at = a] as the action-value function, we have E[Rπ0 ] = ∑ s∈S ρ(s)V
π(s), V π(s) = ∑ a∈A π(a|s)Qπ(s, a), and the advantage function Aπ(s, a) = Qπ(s, a)− V π(s).
MARL provides a scalable solution for controlling networked systems, but it introduces partial observability and non-stationarity in decentralized MDP of each agent, leading to inefficient and unstable learning performance. To see this, note si,t ∈ Si ⊆ S does not provide sufficient information for πi. Even assuming si,t = st, the transition pi(si,t+1|si,t, ai,t) = ∑ a−i,t∈A−i π−i(a−i,t|st) · p(st+1|st, ai,t, a−i,t) is non-stationary if the behavior policies of other agents π−i := {πj}j∈V\{i} are evolving over time. In this paper, we enforce practical constraints and only allow local observations and neighborhood communications, which makes MARL even more challenging. Definition 3.1 (Networked Multi-agent MDP with Neighborhood Communication). In a networked cooperative multi-agent MDP (G, {Si,Ai}i∈V , {Mij}ij∈E , p, {ri}i∈V) with the message spaceM, the global reward is defined as r = 1|V| ∑ i∈V ri. All local rewards are shared globally, whereas the communication is limited to neighborhoods, that is, each agent i observes s̃i,t := si,t ∪mNii,t. Here Ni := {j ∈ V|ji ∈ E}, mNii,t := {mji,t}j∈Ni , and each message mji,t ∈Mji is derived from all the available information at that neighbor.

heading: 3.2 SPATIOTEMPORAL RL
text: Definition 3.2 (Spatiotemporal MDP). We assume local transitions are independent of other agents given the neighboring agents, that is,
pi(si,t+1|sVi,t, ai,t) = ∑
aNi,t∈ANi
∏ j∈Ni πj(aj,t|s̃j,t) · p(si,t+1|sVi,t, ai,t, aNi,t), (1)
where Vi := Ni ∪ {i} is the closed neighborhood, and p is abused to denote any stationary transition. Then from the viewpoint of each agent i, Definition 3.1 is equivalent to a decentralized spatiotemporal MDP, characterized as (Si,Ai, {Mji}j∈Ni , pi, {ri}i∈V), by optimizing the discounted return
Rπi,t = T∑ τ=t γτ−t ∑ j∈V αdijrj,t  , (2) where 0 ≤ α ≤ 1 is the spatial discount factor, and dij is distance between agents i and j.
The major assumption in Definition 3.2 is that the Markovian property holds both temporally and spatially, so that the next local state depends on the neighborhood states and policies only. This assumption is valid in most networked control systems such as traffic and wireless networks, as well as the power grid, where the impact of each agent is spread over the entire system via controlled flows, or chained local transitions. Note in NSC, each agent is connected to a limited number of neighbors (the degree of G is low). So spatiotemporal MDP is decentralized during model execution, and it naturally extends properties of MDP. To reduce the learning difficulty of spatiotemporal MDP, a spatiotemporally discounted return is introduced in Eq. (2) to scale down reward signals further away (which are more difficult to fit using local information). When α→ 0,
2In infinite MDP, rT (s) = E [∑∞ t=T γ t−T rt ∣∣∣∣sT = s].
each agent performs local greedy control; when α → 1, each agent performs global coordination and Rπi,t = R π t ,∀i ∈ V . Further, we have Qπi (s, a) = Qπi (s, aVi) = E[Rπi,t|st = s, aVi,t = aVi ], and V πi (s, a−i) = V π i (s, aNi) = ∑ ai∈Ai πi(ai|s̃i)Q π i (s, aVi), since the immediate local reward of each agent is only affected by controls within its closed neighborhood.
Now we assume each agent is A2C, with parametric models πθi(s̃i) and Vωi(s̃i, aNi) for fitting the optimal policy π∗i and value function V
πi . Note if s̃i is able to provide global information through cascaded neighborhood communications, both πθi and Vωi are able to fit return R π i,t. Also, global and future information, such as Rπi,τ and aNi,τ , are always available from each rollout minibatch in offline training. In contrast, only local information s̃i,t is allowed in online execution of policy πθi . Proposition 3.1 (Spatiotemporal RL with A2C). Let {πθi}i∈V and {Vωi}i∈V be the decentralized actor-critics, and {(si,τ ,mNii,τ , ai,τ , ri,τ )}i∈V,τ∈B be the on-policy minibatch from spatiotemporal MDPs under stationary policies {πθi}i∈V . Then each actor and critic are updated by losses
L(θi) = 1 |B| ∑ τ∈B ( − log πθi(ai,τ |s̃i,τ )Âπi,τ + β ∑ ai∈Ai πθi(ai|s̃i,τ ) log πθi(ai|s̃i,τ ) ) , (3)
L(ωi) = 1 |B| ∑ τ∈B ( R̂πi,τ − Vωi(s̃i,τ , aNi,τ ) )2 , (4)
where Âπi,τ = R̂ π i,τ − vi,τ is the estimated advantage, R̂πi,τ = ∑τB−1 τ ′=τ γ τ ′−τ (∑ j∈V α dijrj,τ ′ ) + γτB−τvi,τB is the sampled action-value, vi,τ = Vω−i (s̃i,τ , aNi,τ ) is the estimated state-value, and β is the coefficient of the entropy loss.

heading: 4 SPATIOTEMPORAL RL WITH NEURAL COMMUNICATION
text: For efficient and adaptive information sharing, we propose a new communication protocol called NeurComm. To simplify the notation, we assume all messages sent from agent i are identical, i.e., mij = mi,∀j ∈ Ni. Then
hi,t = gνi(hi,t−1, eλsi (sVi,t), eλ p i (πNi,t−1), eλhi (hNi,t−1)), (5)
where hi,t is the hidden state (or the belief ) of each agent and eλi and gνi are differentiable message encoding and extracting functions 3. To avoid dilution of state and policy information (the former is for improving observability while the later is for reducing non-stationarity), state and policy are explicitly included in the message besides agent belief, i.e., mi,t = si,t ∪ πi,t−1 ∪ hi,t−1, or s̃i,t := sVi,t∪πNi,t−1∪hNi,t−1 as in Eq. (5). Note the communication phase is prior-decision, so only hi,t−1 and πi,t−1 are available. This protocol can be easily extended for multi-pass communication: h (k) i,t = gν(k)i (h (k−1) i,t , eλsi (sVi,t), eλ p i (πNi,t−1), eλhi (h (k−1) Ni,t )), where h (0) i,t = hi,t−1, and k denotes each of the communication passes. The communication attentions can be integrated either at the sender as µi,t(mi,t), or at the receiver as µi,t(mNi,t). Replacing the input (s̃i,t) of Eq. (3)(4) with the belief (hi,t), the actor and critic become πθi(·|hi,t) and Vωi(hi,t, aNi,t), and the frozen estimations are πi,t and vi,t, respectively. Proposition 4.1 (Neighborhood Neural Communication). In spatiotemporal RL with neighborhood NeurComm, each agent utilizes the delayed global information to learn its belief, and it learns the message to optimize the control performance of all other agents.
NeurComm enabled MARL can be represented using a single meta-DNN since all agents are connected by differentiable communication links, and s̃i are the intermediate outputs after communication layers. Fig. 1a illustrates the forward propagations inside each individual agent and Fig. 1b shows the broader multi-step spatiotemporal propagations. Note the gradient propagation of this meta-DNN is decentralized based on each local loss signal. As time advances, the involved parameters in each propagation expand spatially in the meta-DNN, due to the cascaded neighborhood communication. To see this mathematically, πθi,t(·|hi,t) = πθ̃i,t(·|sVi,t, πNi,t−1), with θ̃i,t = {λi, νi, θi}; while πθi,t+1(·|hi,t+1) = πθ̃i,t+1(·|sVi,t+1, πNi,t, {sNj ,t, πNj ,t−1}j∈Ni), with
3Additional cell state needs to be maintained if LSTM is used.
θ̃i,t+1 = {λj , νj}j∈Ni ∪ {λi, νi, θi}. In other words, {λi, νi} will be updated for improving actors πθj , ∀j ∈ V , as soon as they are included in θ̃j ; meanwhile, ri will be included in Rπj . In contrast, the policy is fully decentralized in execution, as gνi depends on s̃i only.
NeurComm is general enough and has connections to other communication protocols. CommNet performs a more lossy aggregation since the received messages are averaged before encoding, and all encoded inputs are summed up (Sukhbaatar et al., 2016). In DIAL, each DQN agent encodes the received messages instead of averaging them, but still it sums all encoded inputs (Foerster et al., 2016). Also, both CommNet and DIAL do not have policy fingerprints included in messages.

heading: 5 NUMERICAL EXPERIMENTS

heading: 5.1 ENVIRONMENT SETUP
text: There are several benchmark MARL environments such as cooperative navigation and predator-prey, but few of them represent NSC. Here we design two NSC environments: adaptive traffic signal control (ATSC) and cooperative adaptive cruise control (CACC). Both ATSC and CACC are extensively studied in intelligent transportation systems, and they hold assumptions of a spatiotemporal MDP.

heading: 5.1.1 ADAPTIVE TRAFFIC SIGNAL CONTROL
text: The objective of ATSC is to adaptively adjust signal phases to minimize traffic congestion based on real-time road-traffic measurements. Here we implement two ATSC scenarios: a 5×5 synthetic traffic grid and a real-world 28-intersection traffic network from Monaco city, using standard microscopic traffic simulator SUMO (Krajzewicz et al., 2012).
General settings. For both scenarios, each episode simulates the peak-hour traffic, and a 5s control interval is applied to prevent traffic light from too frequent switches, based on RL control latency and driver response delay. Thus, one MDP step corresponds to 5s simulation and the horizon is 720 steps. Further, a 2s yellow time is inserted before switching to red light for safety purposes. In ATSC, the real-time traffic flow, that is, the total number of approaching vehicles along each incoming lane, is measured by near-intersection induction-loop detectors (ILDs) (shown as the blue areas of example intersections in Fig. 2). The cost of each agent is the sum of queue lengths along all incoming lanes.
Scenario settings. Fig. 2a illustrates the traffic grid formed by two-lane arterial streets with speed limit 20m/s and one-lane avenues with speed limit 11m/s. We simulate the peak-hour traffic dynamics through four collections of time-variant traffic flows, with both loading and recovering phases. At beginning, three major flows F1 are generated with origin-destination (O-D) pairs x10-x4, x11-x5, and x12-x6, meanwhile three minor flows f1 are generated with O-D pairs x1-x7, x2-x8, and x3-x9.
After 15 minutes, F1 and f1 start to decay, while their opposite flows F2 and f2 start to dominate, as shown in Fig. 2b. Note the flows define the high-level demand only, the particular route of each vehicle is randomly generated. The grid is homogeneous and all agents have the same action space, which is a set of five pre-defined signal phases. Fig. 2c illustrates the Monaco traffic network, with controlled intersections in blue. NMARL in this scenario is more challenging since the network is heterogeneous with a variety of observation and action spaces. Four traffic flow collections are generated to simulate the peak-hour traffic, and each flow is a multiple of a “unit” flow of 325veh/hr, with randomly sampled O-D pairs inside rectangle areas in Fig. 2c. F1 and F2 are simulated during the first 40min, as [1, 2, 4, 4, 4, 4, 2, 1] unit flows with 5min intervals; F3 and F4 are generated in the same way, but with a delay of 15min. See code for more details.

heading: 5.1.2 COOPERATIVE ADAPTIVE CRUISE CONTROL
text: The objective of CACC is to adaptively coordinate a platoon of vehicles to minimize the car-following headway and speed perturbations based on real-time vehicle-to-vehicle communication. Here we implement two CACC scenarios: “Catch-up” and “Slow-down”, with physical vehicle dynamics.
General settings. For both CACC tasks, we simulate a string of 8 vehicles for 60s, with a 0.1s control interval. Each vehicle observes and shares its headway h, velocity v, and acceleration a to neighbors within two steps. The safety constraints are: h ≥ 1m, v ≤ 30m/s, |a| ≤ 2.5m/s2. Safe RL is relevant here, but itself is a big topic and out of the scope of this paper. So we adopt a simple heuristic optimal velocity model (OVM) (Bando et al., 1995) to perform longitudinal vehicle control under above constraints, whose behavior is affected by hyper-parameters: headway gain α◦, relative velocity gain β◦, stop headway hst = 5m and full-speed headway hgo = 35m. Usually (α◦, β◦) represent the human driver behavior, here we train NMARL to recommend appropriate (α◦, β◦) for each OVM controller, selected from four levels {(0, 0), (0.5, 0), (0, 0.5), (0.5, 0.5)}. Assuming the target headway and velocity profile are h∗ = 20m and v∗t , respectively, the cost of each agent is (hi,t − h∗)2 + (vi,t − v∗t )2 + 0.1u2i,t. Whenever a collision happens (hi,t < 1m), a large penalty of 1000 is assigned to each agent and the state becomes absorbing. An additional cost 5(2hst − hi,t)2+ is provided in training for potential collisions.
Scenario settings. Since exploring a collision-free CACC strategy itself is challenging for onpolicy RL, we consider simple scenarios. In Catch-up scenario, vi,0 = v∗t =15m/s and hi,0 = h
∗, ∀i 6= 1, whereas h1,0 = a · h∗, with a ∈ U [3, 4]. In Slow-down scenario, vi,0 = v∗0 = b·15m/s, b ∈ U [1.5, 2.5], and hi,0 = h∗, ∀i, whereas v∗t linearly decreases to 15m/s during the first 30s and then stays at constant.

heading: 5.2 ALGORITHM SETUP
text: For fair comparison, all MARL approaches are applied to A2C agents with learning methods in Eq. (3)(4), and only neighborhood observation and communication are allowed. IA2C performs independent learning, which is an A2C implementation of MADDPG (Lowe et al., 2017) as the critic takes neighboring actions (see Eq. (4)). ConseNet (Zhang et al., 2018) has the additional consensus
update to overwrite parameters of each critic as the mean of those of all critics inside the closed neighborhood. FPrint (Foerster et al., 2017) includes neighbor policies. DIAL (Foerster et al., 2016) and CommNet (Sukhbaatar et al., 2016) are described in Section 4. IA2C, ConseNet, and FPrint are non-communicative policies since they utilize only neighborhood information. In contrast, DIAL, CommNet, and NeurComm are communicative policies. Note communicative policies require more messages to be transferred and so higher communication bandwidth. In particular, the local message sizes are O(|si|+ |πi|+ |hi|) for DIAL and NeurComm, O(|si|+ |hi|) for CommNet, O(|si|+ |πi|) for FPrint, and O(|si|) for IA2C and ConseNet. The implementation details are in C.1. All algorithms use the same DNN hidden layers: one fully-connected layer for message encoding eλ, and one LSTM layer for message extracting gν . All hidden layers have 64 units. The encoding layer implicitly learns normalization across different input signal types. We train each model over 1M steps, with γ = 0.99, actor learning rate 5× 10−4, and critic learning rate 2.5× 10−4. Also, each training episode has a different seed for generalization purposes. In ATSC, β = 0.01, |B| = 120, while in CACC, β = 0.05, |B| = 60, to encourage the exploration of collision-free policies. Each training takes about 30 hours on a 32GB memory, Intel Xeon CPU machine.

heading: 5.3 ABLATION STUDY
text: We perform ablation study in proposed scenarios, which are sorted as ATSC Monaco > ATSC Grid > CACC Slow-down > CACC Catch-up by task difficulty. ATSC is more challenging than CACC due to larger scale (>=25 vs 8), more complex dynamics (stochastic traffic flow vs deterministic vehicle dynamics), and longer control interval (5s vs 0.1s). ATSC Monaco > ATSC Grid due to more heterogenous network, while CACC Slow-down > CACC Catch-up due to more frequently changing leading vehicle profile. To visualize the learning performance, we plot the learning curve, that is, average episode return (R̄ = 1T ∑T−1 t=0 ∑ i∈V ri,t) vs training step. For better visualization, all learning curves are smoothened using moving average with a window size of 100 episodes.
First, we investigate the impact of spatial discount factor, by comparing the learning curves among α ∈ {0.8, 0.9, 1} for IA2C and CommNet. Fig. 3 reveals a few interesting facts. First, α∗CommNet is always higher than α∗IA2C. Indeed, α ∗ CommNet = 1 in almost all scenarios (except for ATSC Monaco). This is because communicative policies perform delayed global information sharing, whereas noncommunicative policies utilize neighborhood information only, causing difficulty to fit the global return. Second, learning performance becomes much more sensitive to α when the task is more difficult. Specifically, all α values lead to similar learning curves in CACC Catch-up, whereas appropriate α values help IA2C converge to much better policies more steadily in other scenarios. Third, α∗ is high enough: α∗IA2C = 0.9 except for CACC Slow-down where α ∗ IA2C = 0.8. This is because the discounted problem must be similar enough to the original problem in execution.
Next, we investigate the impact of NeurComm under α = 1. We start with a baseline which is similar to existing differentiable protocols, i.e., hi,t = LSTM(hi,t−1,relu(sVi,t) + relu(mNi,t)). We then evaluate two intermediate protocols “Concat Only” and “FPrint Only”, in which encoded inputs are concatenated and neighbor policies are included, respectively. Finally we evaluate their combination NeurComm. As shown in Fig. 3, all protocols have similar learning curves in easy CACC Catch-up scenario. Otherwise, both “Concat” and “FPrint” are able to enhance the baseline learning curves in certain scenarios and their affects are additive in NeurComm.

heading: 5.4 TRAINING RESULTS
text: Fig. 4 compares the learning curves of all MARL algorithms, after tuned α∗ ∈ {0.6, 0.8, 0.9, 0.95, 1}. As expected, α∗ for non-communicative policies are lower than those for communicative policies.
Tab. 1 summarizes α∗ of controllers across different NMARL scenarios. For challenging scenarios like ATSC Monaco, lower α is preferred by almost all policies (except NeurComm). This demonstrates that α is an effective way to enhance MARL performance in general, especially for challenging tasks like ATSC Monaco. From another view point, α serves as an informative indicator on problem difficulty and algorithm coordination level. Based on Fig. 4, NeurComm is at least competitive in CACC scenarios, and it clearly outperforms other policies on both sample efficiency and learning stability in more challenging ATSC scenarios. Note in CACC a big penalty is assigned whenever a collision happens, so the standard deviation of episode returns is high.

heading: 5.5 EXECUTION RESULTS
text: We freeze and evaluate trained MARL policies in another 50 episodes, and summarize the results in Tab. 2. In CACC scenarios, α enhanced FPrint policy achieves the best execution performance. Note NeurComm still outperforms other communicative algorithms, so this result implies that delayed information sharing may not be helpful in easy but real-time and safety-critical CACC tasks. In contrast, NeurComm achieves the best execution performance for ATSC tasks. We also evaluate the execution performance of ATSC and CACC using domain-specific metrics in Tab. 3 and Tab. 4, respectively. The results are consistent with the reward-defined ones in Tab. 2.
Further, we investigate the performance of top policies in ATSC scenarios. For each ATSC scenario, we select the top two non-communicative and communicative policies and visualize their impact on network traffic by plotting the time series of network averaged queue length and intersection delay in Fig. 5. Note the line and shade show the mean and standard deviation of each metric across execution runs, respectively. Based on Fig. 5a, NeurComm achieves the most sustainable traffic control in ATSC Grid, so that the congested grid starts recovering immediately after the loading phase ends at 3000s. During the same unloading phase, CommNet prevents the queues from further increasing while non-communicative policies are failed to do so. Also, FPrint is less robust than IA2C as it
introduces a sudden congestion jump at 1000s. Similarly, NeurComm achieves the lowest saturation rate in ATSC Monaco (Fig. 5b).
Intersection delay is another key metric in ATSC. Based on Fig. 5c, communicative policies are able to reduce intersection delay as well in ATSC Grid, though it is not explicitly included in the objective and so is not optimized by non-communicative policies. In contrast, communicative policies have fast increase on intersection delay in ATSC Monaco. This implies that communicative algorithms are able to capture the spatiotemporal traffic pattern in homogeneous networks whereas they still have the risk of overfitting on queue reduction in realistic and heterogenous networks. For example, they block the short source edges on purpose to reduce on-road vehicles by paying a small cost of queue length.
Finally, we investigate the robustness (string stability) of top policies in CACC scenarios. In particular, we plot the time series of headway and velocity for the first and the last vehicles in the platoon. The profile of the first vehicle indicates how adaptively the controller pursues h∗ and v∗, while that of the last vehicle indicates how stable the controlled platoon is. Based on Tab. 1 and Tab. 4, the top communicative and non-communicative controllers are NeurComm and FPrint.
Fig. 6 shows the corresponding headway and velocity profiles for the selected controllers. Interestingly, MARL controllers are able to achieve steady state v∗ and h∗ for the first vehicle of platoon, whereas they still have difficulty to eliminate the perturbation through the platoon. This may be because of the heuristic low-level controller as well as the delayed information sharing.

heading: 6 CONCLUSIONS
text: We have formulated the spatiotemporal MDP for decentralized NSC under neighborhood communication. Further, we have introduced the spatial discount factor to enhance non-communicative MARL algorithms, and proposed a neural communication protocol NeurComm to design adaptive and efficient communicative MARL algorithms. We hope this paper provides a rethink on developing scalable and robust MARL controllers for NSC, by following practical engineering assumptions and combining appropriate learning and communication methods rather than reusing existing MARL algorithms. One future direction is improving the recurrent units to naturally control spatiotemporal information flows within the meta-DNN in a decentralized way.

heading: ACKNOWLEDGMENTS
text: We would like to thank Marco Pavone and Alexander Anemogiannis for valuable discussions and insightful comments.

heading: APPENDIX

heading: A PROOFS

heading: A.1 PROOF OF PROPOSITION 3.1
text: Proof. The proof follows the learning method in A2C Mnih et al. (2016), which shows that
L(θ) = 1 |B| ∑ τ∈B ( − log πθ(aτ |sτ )Âπτ + β ∑ a∈A πθ(a|sτ ) log πθ(a|sτ ) ) , (6)
L(ω) = 1 |B| ∑ τ∈B ( R̂πτ − Vω(sτ ) )2 , (7)
where Âπτ = R̂ π τ − vτ , R̂πτ = ∑τB−1 τ ′=τ γ τ ′−τrτ ′ + γ τB−τvτB , and vτ = Vω−(sτ ), based on on-policy minibatch from a MDP {(sτ , aτ , rτ )}τ∈B. Now we consider spatiotemporal MDP, which has transition in Eq. (1), optimizes return in Eq. (2), and collects experience (si,t,mNii,t, ai,t, r̃i,t), where r̃i,t = ∑ j∈V α dijrj,t. In Theorem 3.1 of Zhang
et al. (2018), the decentralized actor and critic are π̃θi(s) and Ṽωi(s, a−i), for fitting π ∗ i (·|s) and∑
ai∈Ai πi(ai|s)Q πi(s, a) under global observations, respectively. Now assuming the observations and communications are restricted to each neighborhood as in Definition 3.1, then the actor and critic become πθi(s̃i) ≈ π̃θi(s) and Vωi(s̃i, aNi) ≈ Ṽωi(s, a−i), with the best observability. Hence, replacing πθ(a|s), Vω(s), r by πθi(ai|s̃i), Vωi(s̃i, aNi), and r̃i, respectively, we establish Eq. (3)(4) from Eq. (6)(7), which concludes the proof.
Note partial observability and non-stationarity are present in πθi(ai|s̃i) and Vωi(s̃i, aNi). Fortunately, communication improves the observability. Based on Definition 3.1, any information that agent j knows at time t can be included in mji,t. We assume sj,t ∪ {mkj,t−1}k∈Nj ⊂ mji,t. Then
s̃i,t ⊃ si,t ∪ {sj,t ∪ {mkj,t−1}k∈Nj}j∈Ni ⊃ {sj,t}j∈Vi ∪ {sj,t−1 ∪ {mkj,t−2}k∈Nj}j∈V|dij=2 ⊃ {sj,t}j∈Vi ∪ {sj,t−1}j∈V|dij=2 ∪ {sj,t−2 ∪ {mkj,t−3}k∈Nj}j∈V|dij=3 ⊃ . . . ⊃ si,t ∪ { sj,t+1−dij } j∈V\{i} .
Thus, s̃i,t includes the delayed global observations. On the other hand, Eq. (1)(2) mitigate the non-stationarity. To see this mathematically,
Eπi,p[r̃i,t|st, at] =Eπi,pi [ri,t|sVi,t, aNi,t] + α ∑ j∈Ni Eπi,pj [rj,t|sVj ,t, aVj\{i},t]
+ dmax∑ d=2 αd ∑ j∈{V|dij=d} Epj [rj,t|sVj ,t, aVj ,t]  , where the further away reward signals are discounted more. Note if communication is allowed, each agent will have delayed global observations, and the non-stationarity mainly comes from limited information of future actions.

heading: A.2 PROOF OF PROPOSITION 4.1
text: This proposition contains two statements regarding neural communication based global information sharing in forward and backward propagations. We establish each of them separately. Lemma A.1 (Spatial Information Propagation). In NeurComm, the delayed global information is utilized to estimate each hidden state, that is,
hi,t ⊃ si,0:t ∪ { sj,0:t+1−dij , πj,0:t−dij } j∈V\{i} , (8)
where x ⊃ y if information y is utilized to estimate x, and x0:t := {x0, x1, . . . , xt}.
Proof. Based on the definition of NeurComm protocol (Eq. (5)), mi,t ⊃ hi,t−1, and hi,t ⊃ hi,t−1 ∪ sVi,t ∪ πNi,t−1 ∪mNi,t. Hence,
hi,t ⊃ si,t ∪ {sj,t, πj,t−1}j∈Ni ∪ {hj,t−1}j∈Vi ⊃ si,t ∪ {sj,t, πj,t−1}j∈Ni ∪ { sj,t−1 ∪ {sk,t−1, πk,t−2}k∈Nj ∪ {hk,t−2}k∈Vj } j∈Vi
= si,t−1:t ∪ {sj,t−1:t, πj,t−2:t−1}j∈Ni ∪ {sj,t−1, πj,t−2}j∈{V|dij=2} ∪ {hj,t−2}j∈{V|dij≤2}
⊃ . . . ⊃ si,0:t ∪ {sj,0:t, πj,t−2:t−1}j∈Ni ∪ {sj,0:t−1, πj,0:t−2}j∈{V|dij=2}
∪ . . . ∪ {sj,0:t+1−dmax , πj,0:t−dmax}j∈{V|dij=dmax}, which concludes the proof.
Lemma A.2 (Spatial Gradient Propagation). In NeurComm, each message is learned to optimize the performance of other agents, that is, {νi, λi} receive almost all gradients from L(θj), L(ωj), ∀j ∈ {V|j 6= i}.
Proof. If we rewrite the required information for a given hidden state hi,t using intermediate messages instead of inputs, the result of Lemma A.1 becomes
hi,t ⊃ {mj,t}j∈Ni ⊃ {hj,t−1}j∈Ni ⊃ {mj,t−1}j∈{V|dij=2} ⊃ . . . ⊃ {mj,t+1−d}j∈{V|dij=d} ⊃ . . .
Hence, mi,τ is included in the meta-DNN of agent j at time τ + dij − 1. In other words, {νi, λi} receive gradients from L(θj), L(ωj), ∀j ∈ {V|j 6= i}, except for the first dij − 1 experience samples. Assuming dmax |B|, {νi, λi} receive almost all gradients from loss signals of all other agents, which concludes the proof.

heading: B ALGORITHMS
text: Algo. 1 presents the algorithm of model training in a synchronous way, following descriptions in Section 3 and 4. Four iterations are performed at each step: the first iteration (lines 3-5) updates and sends messages; the second iteration (lines 6-10) updates hidden state, policy, and action; the third iteration (lines 11-14) updates value estimation and executes action; the fourth iteration (lines 22-26) performs gradient updates on actor, critic, and neural communication. On the other hand, Algo. 2 presents the algorithm of decentralized model execution in an asynchronous way. It runs as a job that repeatedly measures traffic, sends message, receives messages, and performs control.
Algorithm 1: Multi-agent A2C with NeurComm (Training) Parameter :α, β, γ, T , |B|, ηω , ηθ. Result: {λi, νi, ωi, θi}i∈V .
1 initialize s0, π−1, h−1, t← 0, k ← 0, B ← ∅; 2 repeat 3 for i ∈ V do 4 send mi,t = fλi(hi,t−1); 5 end 6 for i ∈ V do 7 observe s̃i,t = sVi,t ∪ πNi,t−1 ∪mNi,t; 8 update hi,t ← gνi(hi,t−1, s̃i,t), πi,t ← πθi(·|hi,t); 9 update ai,t ∼ πi,t;
10 end 11 for i ∈ V do 12 update vi,t ← Vωi(hi,t, aNi,t); 13 execute ai,t; 14 end 15 simulate {si,t+1, ri,t}i∈V ; 16 update B ← B ∪ {(si,t, πi,t−1, ai,t, ri,t, vi,t)}i∈V ; 17 update t← t+ 1, k ← k + 1; 18 if t = T then 19 initialize s0, π−1, h−1, t← 0; 20 end 21 if k = |B| then 22 for i ∈ V do 23 update R̂πiτ , Âπiτ , ∀τ ∈ B, based on Proposition 3.1; 24 update {λj , νj}j∈V ∪ {ωi}, based on ηw∇L(wi); 25 update {λj , νj}j∈V ∪ {θi}, based on ηθ∇L(θi); 26 end 27 initialize B ← ∅, k ← 0; 28 end 29 until Stop condition is reached;
Algorithm 2: Multi-agent A2C with NeurComm (Execution)

heading: Parameter :{λi, νi, ωi, θi}i∈V , ∆tcomm, ∆tcontrol.
text: 1 for i ∈ V do 2 initialize hi ← 0, πi ← 0, {sj , πj ,mj}j∈Ni ← 0; 3 repeat 4 observe si; 5 update mi ← fλi(hi); 6 send si, πi,mi; 7 for j ∈ N do 8 receive and update sj , πj ,mj within ∆tcomm; 9 end
10 update s̃i ← sVi ∪ πNi ∪mNi ; 11 update hi ← gνi(hi, s̃i), πi ← πθi(·|hi); 12 execute ai ∼ πi; 13 sleep ∆tcontrol; 14 until Stop condition is reached; 15 end

heading: C EXPERIMENT DETAILS

heading: C.1 ALGORITHM SETUP
text: Detailed algorithm implementations are listed below, in term of Eq. (5). IA2C: hi,t = LSTM(hi,t−1,relu(sVi,t)). ConseNet: same as IA2C but with consensus critic update. FPrint: hi,t = LSTM(hi,t−1,concat(relu(sVi,t),relu(πNi,t−1))). NeurComm: hi,t = LSTM(hi,t−1,concat(relu(sVi,t),relu(πNi,t−1),relu(hNi,t−1))). DIAL: hi,t = LSTM(hi,t−1,relu(sVi,t) + relu(relu(hi,t−1)) + onehot(ai,t−1)). CommNet: hi,t = LSTM(hi,t−1,tanh(sVi,t) + linear(mean(hNi,t−1))). For ConseNet, we only do consensus update on the LSTM layer, since the input and output layer sizes may not be fixed across agents. Also, the actor and critic are πi,t = softmax(hi,t), and vi,t = linear(concat(hi,t,onehot(aNi,t)))

heading: C.2 EXPERIMENTS IN ATSC ENVIRONMENT

heading: C.2.1 ACTION SPACE
text: Fig. 7 illustrates the action space of five phases for each intersection in the ATSC Grid scenario. The ATSC Monaco scenario has complex and heterogeneous action spaces, please see the code for more details. To summarize, there are 11 two-phase intersections, 3 three-phase intersections, 10 four-phase intersections, 1 five-phase intersection, and 3 six-phase intersections.

heading: C.2.2 SUMMARY OF EXECUTION PERFORMANCE
text: Table 3 summarizes the key metrics in ATSC. The spatial average is taken at each second, and then the temporal average is calculated for all metrics (except for trip delay, which is directly aggregated over all trips). NeurComm outperforms all baselines on minimizing queue length and intersection delay. Interestingly, even though IA2C is good at optimizing the given objective of queue length, it performs poorly on optimizing intersection and trip delays.
C.2.3 VISUALIZATION OF EXECUTION PERFORMANCE
Fig. 8 and Fig. 9 show screenshots of traffic distributions in the grid at different simulation steps for each MARL controller. The visualization is based on one execution episode with random seed 2000. Clearly, communicative MARL controllers have better performance on reducing the intersection delay. NeurComm and CommNet have the best overall performance.

heading: C.3 EXPERIMENTS IN CACC ENVIRONMENTS

heading: C.3.1 SUMMARY OF EXECUTION PERFORMANCE
text: Table 4 summarizes the key metrics in CACC. The best headway and velocity averages are closest ones to h∗ = 20m, and v∗ = 15m/s. Note the averages are only computed from safe execution episodes, and we use another metric “collision number” to count the number of episodes where an collision happens within the horizon. Ideally, “collision-free” is the top priority. However, safe RL is not the focus of this paper so trained MARL controllers cannot achieve this goal in the experiments of CACC.

Review summaries:
This paper is concerned with network multi-agent RL (N-MARL), where agents need to update their policy based on messages obtained only from neighboring nodes. This is done under sensible restrictions on the state transition distribution, which can be claimed to hold true in realistic networked settings. The authors argue that introducing a spatial discount factor (along a temporal one), where neighboring nodes have a small distance, stabilizes learning. Also, they provide a way of learning a networked communication protocol. Experiments are done on somewhat realistic simulations of traffic.

The authors use decentralized MARL for networked system control. Each agent might control a traffic light (exp 1) or a car in traffic (exp 2). Some features of their approach are a spatial Markov assumption (only neighborhood matters), a spatial discount factor, and NeurComm: a general message passing scheme between agent policies. The authors compare their method with CommNet (averages messages before broadcast), DIAL (small-scale direct communication), etc.