Title: MULTI-AGENT REINFORCEMENT LEARNING FOR NETWORKED SYSTEM CONTROL

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.

1. INTRODUCTION:

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 2 RELATED WORK 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 Master-Slave (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.

3. SPATIOTEMPORAL RL:

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.

3.1. NETWORKED MARL:

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, {S i , A i } i∈V , p, r) where S i and A i are the local state space and action space of agent i. Let S := × i∈V S i and A := × i∈V A i 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 : S i × A i → [0, 1] to chose its own action a i,t ∼ π i (•|s i,t ) at time t. The MDP objective is to maximize E[R π 0 ], where R π t = T τ =t γ τ -t r τ 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 s t ∼ ρ, and the transition s τ +1 ∼ p(•|s τ , a τ ), regarding the step reward r τ = r(s τ , a τ ), ∀τ < T , and the terminal reward r T = r T (s T )2 . The same system can be formulated as a centralized MDP. Defining V π (s) = E[R π t |s t = s] as the state-value function and

Q π (s, a) = E[R π t |s t = s, a t = 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 s i,t ∈ S i ⊆ S does not provide sufficient information for π i . Even assuming s i,t = s t , the transition p i (s i,t+1 |s i,t , a i,t ) = a-i,t∈A-i π -i (a -i,t |s t ) • p(s t+1 |s t , a i,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, {S i , A i } i∈V , {M ij } ij∈E , p, {r i } i∈V ) with the message space M, the global reward is defined as r = 1 |V| i∈V r i . All local rewards are shared globally, whereas the communication is limited to neighborhoods, that is, each agent i observes si,t := s i,t ∪ m Nii,t . Here N i := {j ∈ V|ji ∈ E}, m Nii,t := {m ji,t } j∈Ni , and each message m ji,t ∈ M ji is derived from all the available information at that neighbor.

Definition 3.2 (Spatiotemporal MDP). We assume local transitions are independent of other agents given the neighboring agents, that is,

EQUATION

where V i := N i ∪ {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 (S i , A i , {M ji } j∈Ni , p i , {r i } i∈V ), by optimizing the discounted return

EQUATION

where 0 ≤ α ≤ 1 is the spatial discount factor, and d ij 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, 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, a Vi ) = E[R π i,t |s t = s, a Vi,t = a Vi ], and V π i (s, a -i ) = V π i (s, a Ni ) = ai∈Ai π i (a i |s i )Q π i (s, a Vi )

, 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 , a Ni ) for fitting the optimal policy π * i and value function V πi . Note if si 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 a Ni,τ , are always available from each rollout minibatch in offline training. In contrast, only local information si,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 {(s i,τ , m Nii,τ , a i,τ , r i,τ )} 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

EQUATION

EQUATION

where

Âπ i,τ = Rπ i,τ -v i,τ is the estimated advantage, Rπ i,τ = τ B -1 τ =τ γ τ -τ j∈V α dij r j,τ + γ τ B -τ v i,τ B is the sampled action-value, v i,τ = V ω - i (s i,τ , a Ni,τ

) is the estimated state-value, and β is the coefficient of the entropy loss.

4. SPATIOTEMPORAL RL WITH NEURAL COMMUNICATION:

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., m ij = m i , ∀j ∈ N i . Then

EQUATION

where h i,t is the hidden state (or the belief ) of each agent and e λi and g νi are differentiable message encoding and extracting functions3 . 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., m i,t = s i,t ∪ π i,t-1 ∪ h i,t-1 , or si,t := s Vi,t ∪π Ni,t-1 ∪h Ni,t-1 as in Eq. ( 5). Note the communication phase is prior-decision, so only h i,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 λ s i (s Vi,t ), e λ p i (π Ni,t-1 ), e λ h i (h (k-1)

Ni,t )), where h (0) i,t = h i,t-1 , and k denotes each of the communication passes. The communication attentions can be integrated either at the sender as µ i,t (m i,t ), or at the receiver as µ i,t (m Ni,t ). Replacing the input (s i,t ) of Eq. (3)(4) with the belief (h i,t ), the actor and critic become π θi (•|h i,t ) and V ωi (h i,t , a Ni,t ), and the frozen estimations are π i,t and v i,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 si 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 (•|h i,t ) = π θi,t (•|s Vi,t , π Ni,t-1 ), with θi,t = {λ i , ν i , θ i }; while π θi,t+1 (•|h i,t+1 ) = π θi,t+1 (•|s Vi,t+1 , π Ni,t , {s Nj ,t , π Nj ,t-1 } j∈Ni ), with θ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, r i will be included in R π j . In contrast, the policy is fully decentralized in execution, as g νi depends on si 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.

5. NUMERICAL EXPERIMENTS:



5.1. ENVIRONMENT SETUP:

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.

5.1.1. ADAPTIVE TRAFFIC SIGNAL CONTROL:

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 F 1 are generated with origin-destination (O-D) pairs x 10 -x 4 , x 11 -x 5 , and x 12 -x 6 , meanwhile three minor flows f 1 are generated with O-D pairs x 1 -x 7 , x 2 -x 8 , and x 3 -x 9 .

After 15 minutes, F 1 and f 1 start to decay, while their opposite flows F 2 and f 2 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. 

5.1.2. COOPERATIVE ADAPTIVE CRUISE CONTROL:

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/s 2 . 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 h st = 5m and full-speed headway h go = 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

(h i,t -h * ) 2 + (v i,t -v * t ) 2 + 0.1u 2 i,t

. Whenever a collision happens (h i,t < 1m), a large penalty of 1000 is assigned to each agent and the state becomes absorbing. An additional cost 5(2h sth i,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, v i,0 = v * t =15m/s and h

i,0 = h * , ∀i = 1, whereas h 1,0 = a • h * , with a ∈ U [3, 4]. In Slow-down scenario, v i,0 = v * 0 = b•15m/s, b ∈ U [1.5, 2.5],

and h i,0 = h * , ∀i, whereas v * t linearly decreases to 15m/s during the first 30s and then stays at constant.

5.2. ALGORITHM SETUP:

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) 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.

5.3. ABLATION STUDY:

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 = 1 T T -1 t=0 i∈V r i,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., h i,t = LSTM(h i,t-1 , relu(s Vi,t ) + relu(m Ni,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.

5.4. TRAINING RESULTS:

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. 

Scenario Name:

NeurComm CommNet DIAL IA2C FPrint ConseNet ATSC Grid 1.0 1.0 1.0 0.9 0.95 0.9 ATSC Monaco 1.0 0.9 0.9 0.9 0.9 0.9 CACC Catch-up 1.0 1.0 1.0 1.0 1.0 1.0 CACC Slow-down 1.0 1.0 1.0 0.8 0.9 0.8 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.

5.5. EXECUTION RESULTS:

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. 

6. CONCLUSIONS:

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.

et al. ( 2018), the decentralized actor and critic are πθi (s) and Ṽωi (s, a -i ), for fitting π * i (•|s) and ai∈Ai π i (a i |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 , a Ni ) ≈ Ṽωi (s, a -i ), with the best observability.

Hence, replacing π θ (a|s), V ω (s), r by π θi (a i |s i ), V ωi (s i , a Ni ), and ri , respectively, we establish Eq. (3)(4) from Eq. (6)(7), which concludes the proof.

Note partial observability and non-stationarity are present in π θi (a i |s i ) and V ωi (s i , a Ni ). Fortunately, communication improves the observability. Based on Definition 3.1, any information that agent j knows at time t can be included in m ji,t . We assume s j,t ∪ {m kj,t-1 } k∈Nj ⊂ m ji,t . Then

si,t ⊃ s i,t ∪ {s j,t ∪ {m kj,t-1 } k∈Nj } j∈Ni ⊃ {s j,t } j∈Vi ∪ {s j,t-1 ∪ {m kj,t-2 } k∈Nj } j∈V|dij =2 ⊃ {s j,t } j∈Vi ∪ {s j,t-1 } j∈V|dij =2 ∪ {s j,t-2 ∪ {m kj,t-3 } k∈Nj } j∈V|dij =3 ⊃ . . . ⊃ s i,t ∪ s j,t+1-dij j∈V\{i} .

Thus, si,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 |s t , a t ] =E πi,pi [r i,t |s Vi,t , a Ni,t ] + α j∈Ni E πi,pj [r j,t |s Vj ,t , a Vj \{i},t ] + dmax d=2   α d j∈{V|dij =d} E pj [r j,t |s Vj ,t , a Vj ,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.

A.2 PROOF OF PROPOSITION 4.1:

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,

EQUATION

where x ⊃ y if information y is utilized to estimate x, and x 0:t := {x 0 , x 1 , . . . , x t }.

Proof. Based on the definition of NeurComm protocol (Eq. ( 5)), m i,t ⊃ h i,t-1 , and

h i,t ⊃ h i,t-1 ∪ s Vi,t ∪ π Ni,t-1 ∪ m Ni,t . Hence, h i,t ⊃ s i,t ∪ {s j,t , π j,t-1 } j∈Ni ∪ {h j,t-1 } j∈Vi ⊃ s i,t ∪ {s j,t , π j,t-1 } j∈Ni ∪ s j,t-1 ∪ {s k,t-1 , π k,t-2 } k∈Nj ∪ {h k,t-2 } k∈Vj j∈Vi = s i,t-1:t ∪ {s j,t-1:t , π j,t-2:t-1 } j∈Ni ∪ {s j,t-1 , π j,t-2 } j∈{V|dij =2} ∪ {h j,t-2 } j∈{V|dij ≤2}

⊃ . . . ⊃ s i,0:t ∪ {s j,0:t , π j,t-2:t-1 } j∈Ni ∪ {s j,0:t-1 , π j,0:t-2 } j∈{V|dij =2} ∪ . . . ∪ {s j,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 = i}.

Proof. If we rewrite the required information for a given hidden state h i,t using intermediate messages instead of inputs, the result of Lemma A.1 becomes

h i,t ⊃ {m j,t } j∈Ni ⊃ {h j,t-1 } j∈Ni ⊃ {m j,t-1 } j∈{V|dij =2} ⊃ . . . ⊃ {m j,t+1-d } j∈{V|dij =d} ⊃ . . .

Hence, m i,τ is included in the meta-DNN of agent j at time τ + d ij -1. In other words, {ν i , λ i } receive gradients from L(θ j ), L(ω j ), ∀j ∈ {V|j = i}, except for the first d ij -1 experience samples. Assuming d max |B|, {ν i , λ i } receive almost all gradients from loss signals of all other agents, which concludes the proof.

B ALGORITHMS:

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. 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. 

Algorithm 1: Multi-agent A2C with NeurComm (Training) Parameter :α, β, γ, T , |B|, η ω , η θ . Result: {λ i , ν i , ω i , θ i } i∈V . 1 initialize s 0 , π -1 , h -1 , t ← 0, k ← 0, B ← ∅; 2 repeat 3 for i ∈ V do 4 send m i,t = f λi (h i,t-1 ); 5 end 6 for i ∈ V do 7 observe si,t = s Vi,t ∪ π Ni,t-1 ∪ m Ni,t ; 8 update h i,t ← g νi (h i,t-1 , si,t ), π i,t ← π θi (•|h i,

:

Code link: https://github.com/cts198859/deeprl_network.

In infinite MDP, rT (s) = E ∞ t=T γ t-T rt sT = s .

Additional cell state needs to be maintained if LSTM is used.

Figures and Tables:

(a) Intra-step propagations. (b) Inter-step propagations.

Figure 1: Forward propagations of NeurComm enabled MARL, illustrated in a queueing system. (a) Single-step forward propagations inside agent i. Different colored boxes and arrows show different outputs and functions, respectively. Solid and dashed arrows indicate actor and critic propagations, respectively. (b) Multi-step forward propagations for updating the belief of agent i.

Fig.2cillustrates 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. F 1 and F 2 are simulated during the first 40min, as[1, 2, 4, 4, 4, 4, 2, 1] unit flows with 5min intervals; F 3 and F 4 are generated in the same way, but with a delay of 15min. See code for more details. Traffic flows within the grid.

Figure 2: ATSC scenarios for NMARL. (a) Synthetic traffic grid, with major and minor traffic flows shown in solid and dotted arrows. (b) Simulated time-variant traffic flows within the traffic grid. (c) Monaco traffic network, with traffic flow collections shown in colored arrows.

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(|s i | + |π i | + |h i |) for DIAL and NeurComm, O(|s i | + |h i |) for CommNet, O(|s i | + |π i |) for FPrint, and O(|s i |) for IA2C and ConseNet. The implementation details are in C.1.

Figure 3: Sensitivity and ablation study of spatial discount factor (top) and NeurComm (bottom). The best learning curves are in bold.

Figure 4: Training performance comparison after tuned spatial discount factors.

(a) Average queue length in ATSC Grid. (b) Average queue length in ATSC Monaco. (c) Average intersection delay in ATSC Grid. (d) Average intersection delay in ATSC Monaco.

Figure 5: Execution performance comparison among top policies in ATSC scenarios, measured as average queue length and average intersection delay over time.

Figure 6: Headway and velocity profiles of the first and last vehicles of the platoon, controlled by top communicative and non-communicative policies in execution.

Figure 7: Possible signal phases at each intersection.

Figure 8: Screenshots of traffic distribution in the grid. Each row is a non-communicative MARL controller and each column is a simulation step. The traffic condition along each lane is visualized as a line segment, with the color indicating the queue length or congestion level (grey: 0% traffic, green: 25% traffic, yellow: 50% traffic, orange: 70% traffic, red: 90% traffic, intermediate traffic condition is shown as the interpolated color), while the thickness indicating the intersection delay (the thicker the longer waiting time at intersection).

Best spatial discount factors α * across NMARL scenarios.

Table content: <table/>

Execution performance comparison over trained MARL policies. Best values are in bold.

Table content: <table><tr><td>Scenario Name</td><td colspan="4">NeurComm CommNet DIAL IA2C FPrint ConseNet</td></tr><tr><td>ATSC Grid</td><td>-136.1</td><td>-165.1</td><td>-214.4 -160.2 -155.9</td><td>-187.5</td></tr><tr><td>ATSC Monaco</td><td>-226.3</td><td>-263.0</td><td>-339.4 -369.7 -359.4</td><td>-528.9</td></tr><tr><td>CACC Catch-up</td><td>-94.6</td><td>-95.6</td><td>-246.4 -261.7 -57.8</td><td>-419.7</td></tr><tr><td>CACC Slow-down</td><td>-934.7</td><td>-950.8</td><td>-1112 -2209 -697.9</td><td>-1038</td></tr></table>

t ); ← V ωi (h i,t , a Ni,t ); ,t+1 , r i,t } i∈V ; 16 update B ← B ∪ {(s i,t , π i,t-1 , a i,t , r i,t , v i,t )} i∈V ; 17 update t ← t + 1, k ← k + 1; , π -1 , h -1 , t ← 0; Âπi τ , ∀τ ∈ B,based on Proposition 3.1; 24 update {λ j , ν j } j∈V ∪ {ω i }, based on η w ∇L(w i ); 25 update {λ j , ν j } j∈V ∪ {θ i }, based on η θ ∇L(θ i );

Table content: <table><tr><td>9</td><td>update a i,t ∼ π i,t ;</td></tr><tr><td>10</td><td>end</td></tr><tr><td>11</td><td>for i ∈ V do</td></tr><tr><td colspan="2">12 update v i,t 13 execute a i,t ;</td></tr><tr><td>14</td><td>end</td></tr><tr><td colspan="2">15 simulate {s i18 if t = T then</td></tr><tr><td colspan="2">19 initialize s 0 20 end</td></tr><tr><td>21</td><td>if k = |B| then</td></tr><tr><td>22</td><td>for i ∈ V do</td></tr><tr><td colspan="2">23 τ , 26 update Rπi end</td></tr><tr><td>27</td><td>initialize B ← ∅, k ← 0;</td></tr><tr><td>28</td><td>end</td></tr><tr><td colspan="2">29 until Stop condition is reached;</td></tr></table>

Performance of MARL controllers in ATSC environments: synthetic traffic grid (top) and Monaco traffic network (bottom). Best values are in bold.

Table content: <table><tr><td>Temporal Average Metrics</td><td colspan="6">NeurComm CommNet DIAL IA2C FPrint ConseNet</td></tr><tr><td>avg queue length [veh]</td><td>1.16</td><td>1.44</td><td>2.36</td><td>1.63</td><td>1.62</td><td>2.04</td></tr><tr><td>avg intersection delay [s/veh]</td><td>68</td><td>111</td><td>145</td><td>376</td><td>415</td><td>366</td></tr><tr><td>avg vehicle speed [m/s]</td><td>2.28</td><td>1.82</td><td>1.78</td><td>0.26</td><td>0.23</td><td>0.29</td></tr><tr><td>trip delay [s]</td><td>293</td><td>455</td><td>1949</td><td>2067</td><td>1949</td><td>321</td></tr><tr><td>avg queue length [veh]</td><td>1.27</td><td>1.56</td><td>1.88</td><td>1.93</td><td>1.87</td><td>2.74</td></tr><tr><td>avg intersection delay [s/veh]</td><td>221.1</td><td>236.5</td><td colspan="3">231.3 147.4 174.8</td><td>187.3</td></tr><tr><td>avg vehicle speed [m/s]</td><td>0.55</td><td>0.61</td><td>0.94</td><td>2.36</td><td>1.26</td><td>1.03</td></tr><tr><td>trip delay [s]</td><td>569</td><td>847</td><td>506</td><td>295</td><td>428</td><td>540</td></tr><tr><td colspan="2">C.3 EXPERIMENTS IN CACC ENVIRONMENTS</td><td/><td/><td/><td/><td/></tr><tr><td colspan="3">C.3.1 SUMMARY OF EXECUTION PERFORMANCE</td><td/><td/><td/><td/></tr><tr><td>Table</td><td/><td/><td/><td/><td/><td/></tr></table>

Performance of MARL controllers in CACC environments: catch-up (above) and slow-down (below). Best values are in bold.

Table content: <table><tr><td colspan="7">Temporal Average Metrics NeurComm CommNet DIAL IA2C FPrint ConseNet</td></tr><tr><td>avg vehicle headway [m]</td><td>20.45</td><td>20.47</td><td colspan="3">21.99 22.02 20.44</td><td>21.45</td></tr><tr><td>std vehicle headway [m]</td><td>1.20</td><td>1.18</td><td>0.20</td><td>0.19</td><td>1.03</td><td>0</td></tr><tr><td>avg vehicle velocity [m/s]</td><td>15.33</td><td>15.33</td><td colspan="3">15.07 15.07 15.33</td><td>15.00</td></tr><tr><td>std vehicle velocity [m/s]</td><td>0.90</td><td>0.87</td><td>0.16</td><td>0.18</td><td>0.75</td><td>0</td></tr><tr><td>collision number</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>avg vehicle headway [m]</td><td>15.84</td><td>16.24</td><td>14.42</td><td>-</td><td>18.21</td><td>11.60</td></tr><tr><td>std vehicle headway [m]</td><td>2.10</td><td>2.16</td><td>1.70</td><td>-</td><td>2.40</td><td>0.49</td></tr><tr><td>avg vehicle velocity [m/s]</td><td>13.43</td><td>13.82</td><td>12.28</td><td>-</td><td>15.47</td><td>8.59</td></tr><tr><td>std vehicle velocity [m/s]</td><td>2.77</td><td>2.88</td><td>2.49</td><td>-</td><td>3.37</td><td>1.19</td></tr><tr><td>collision number</td><td>13</td><td>12</td><td>16</td><td>50</td><td>8</td><td>23</td></tr></table>

Peer review (iclr2020):
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. I am not an expert in this type of distributed MARL, and what the SotA there is. What is proposed here makes sense to me, even though it also does not look very surprising to me. Spatial discounting seems to make sense. The authors do not comment on the relationship between the d_{ij} (or how to choose them) with the neighborhood graph, I suppose that neighbors have short distances, while non-neighbors have not. The NeurComm protocol is a bit vague to me, and I cannot say how it relates to other proposals. I find it a bit strange (unless I misunderstood something) that complete state and policy information is transmitted to every neighbor, and on top some latent vector. This sounds expensive to me, surely these communication channels are limited? It*d be more interesting to consider bandwidth limitations here. Without knowing related work on other protocols in detail, I suspect they probably work less well than NeurComm, simply because they allow for smaller messages only (f.ex., whereas they talk about *policy fingerprints*, they seem to submit the complete policy parameters to neighbors -- that is not just a fingerprint). Maybe I am wrong, but if so, the paper does not explain things properly (there is some encoding and decoding going on, but just to propagate the hidden states at each node). To me as an outsider, this looks like interesting work with well-simulated experiments. Of course, these are simulated and allow for no real-world conclusions, but then much of RL work does neither. It is just I*d be hard pressed to say what is really surprising in this paper, and what could be learned from it.