Fully Decentralized Model-based Policy Optimization with Networked Agents
Authors: Yuchen Liu
Yali Du
Runji Lin
Hangrui Bi
Mingdong Wu
Jun Wang
Hao Dong
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning
model-based
multi-agent
deep learning
networked system control.

Abstract: Model-based RL is an effective approach for reducing sample complexity. However, when it comes to multi-agent setting where the number of agent is large, the model estimation can be problematic due to the exponential increased interactions. In this paper, we propose a decentralized model-based reinforcement learning algorithm for networked multi-agent systems, where agents are cooperative and communicate locally with their neighbors. We analyze our algorithm theoretically and derive an upper bound of performance discrepancy caused by model usage, and provide a sufficient condition of monotonic policy improvement. In our experiments, we compare our algorithm against other strong multi-agent baselines and demonstrate that our algorithm not only matches the asymptotic performance of model-free methods but also largely increases its sample efficiency.

Under review as a conference paper at ICLR 2022
FULLY DECENTRALIZED MODEL-BASED POLICY OP- TIMIZATION WITH NETWORKED AGENTS
Anonymous authors Paper under double-blind review
ABSTRACT
Model-based RL is an effective approach for reducing sample complexity. How- ever, when comes to multi-agent setting where the number of agent large. the model estimation can be problematic due to the exponential increased interac- tions. this paper, we propose a decentralized model-based reinforcement learn- ing algorithm for networked multi-agent systems, where agents are cooperative and communicate locally with their neighbors. We analyze our algorithm theo- retically and derive upper bound of performance discrepancy caused by model usage, and provide a sufficient condition of monotonic policy improvement. In our experiments, we compare algorithm against other strong multi-agent baselines and demonstrate that our algorithm not only matches the asymptotic performance of model-free methods but also largely increases its sample efficiency.
INTRODUCTION
Many real world problems, such autonomous driving, wireless communications, multi-playee games can be modeled as multi-agent RL problems, where multiple autonomous agents coexist in a common environment, aiming maximize its individual team reward in the long term by inter- acting with the environment and other agents. Unlike single-agent tasks, multi-agent tasks are more challenging, due partial observations and unstable environments when agents update their policies simultaneously. Therefore, there are hardly any one-fite -its-fltllll-- solutions for MARL problems. Exam- ples include networked systems control (NSC) (Chu al. 2202), in which agents are connected via stationary network. They perform decentralized control based on its local observations and mes- sages from connected neighbors. Examples of networked systems include connected vehicle control (Jin & Orosz, 2014), traffic signal control (Chu et al. 2020), etc.
Despite the success of multi-agen reinforcement (RL) algorithms, their performance relies on massive amount of model usage. Typically, multi-agent RL algorithm needs millions of inter- action with the environment to converge. On the other hand, model-based reinforcement learning (MBRL) algorithms, which utilize predictive models of the environment help data collection, empirically more data-efficient than model-free approaches. Although model inaccuracy performs bottleneck of policy quality in model-based algorithms, we can still learn good policy with an imperfect model (Luo et al.) 2019), especially combined with the trick of branched rollout (Janner) al. 2019) limit model usage. Experimentally. MuZero (Schrittwieser et al. (020)). model- based RL algorithm, succeeded in matching the performance of AlphaZero on Go, chess and shogi, and becomes state-of-the-art on Atari games. Model-based MARL is not fully investigated. Exist- ing MB-MARL algorithms either limit their field of research on specific scenario, e.g. two-player zero-sum Markov game (Zhang et al.) 2020) or pursuit evasion game (Bouzy & Métivier (007), or use tabular RL method (Bargiacchi et al. 2021). MB-MARL for multi-agent MDPs is still an open problem to be solved (Zhang et al. 2019), with profound challenges such as scalability issues caused by large state-action space and incomplete information of other agents' state actions.
In this paper, we develop decentralized model-based algorithms on networked systems, where agents are cooperative, and able to communicate with each other. We use localized models to predict future states, and use communication to broadcast their predictions. To address the issue of model error, adopt branched rollout (Janner et al. 2019) to limit the rollout length of model trajectories. In the policy optimization part, we use decentralizd PPO (Schulman et al. 2017) with a extended value function. At last, analyze these algorithms theoretically to bound the performance discrepancy

---

Under review as a conference paper at ICLR 2022
between method and its model-free, centralized counterpart. At last, run these algorithms in traffic control environments (Chu et al.) 2020; Vinitsky et al. 2018) to test the performance of our algorithm. We show that our algorithm increases sample efhciency, and matches the asymptotic performance of model-free methods.
In summary, our contributions are three-fold. Firstly, we propose algorithmic framework, which is a fully decentralized model-based reinforcement learning algorithm, which is named as Decentralized Model-based Policy Optimization (DMPO). Secondly, we analyze the theoretical performance of our algorithm. Lastly, empirical results on traffic control environments demonstrate the effectiveness of DMPO in reducing sample complexities and achieving similar asymptotic per- formance of model-free methods.
RELATED WORK
Model-based methods are known for their data efficiency (Kaelbling et al. 1996), especially com- pared with model-free algorithms. There vast literature on the theoretical analysis of model- based reinforcement learning, In single-agent scenario, monotonic improvement of policy op- timization has been achieved (Luo et al. 2019; Sun et al., 2018). and a later work improved the performance of model-based algorithms by limiting model usage (Janner et al., 2019). But these analysis is restricted to single-agent scenarios, whereas ours addresses multi-agent problems.
On the other hand, Networked System Control (NSC) (Chu et al. 2020 is challenging setting for MARL algorithm to take effect. Some multi-agent algorithms falls into centralized training decen- tralized execution (CTDE) framework. For example. QMIX (Rashid et al. (0188) and COMA (Foer- ster et al.] 2018) all use a centralized critic. In a large network, however, centralized training might not scale. In many scenarios, only fully decentralized algorithms can be used. Zhang al. (2018) proposed an algorithm of NSC that can be proven to converge under linear approximation. Qu et al. (2020a) proposed truncated policy gradient, to optimize local policies with limited communication. Baking in the idea of truncated Q-learning in (Qu et al. 2020a)), we generalize their algorithm to deep RL, rather than tabular RL. Factoring environmental transition into marginal transitions can be seen as factored MDP. Guestrin et al. (2001) used Dynamic Bayesian Network to predict system transition. SSimao Spaan (2019) proposed a tabular RL algorithm to ensure policy improvement at each step. However, our algorithm is deep RL algorithm, enabling better performance in general tasks.
There are some works on applying model-based methods in MARL settings. A line of research focuses on model-based RL for two-player games. For example, Brafman & Tennenholtz (2000)
solved soggl--conttoller-stcchtttttttt games, which is certain type of two-player zero-sum game; Bouzy & Métivier (007) performed MB-MARL in the pursuit evasion game; Zhang et al. (2020)
proved that model-based method can be nearly optimally sample efficient in two-player zero-sum Markov games. |Bargiacchi et al. (202I) extended the concept of prioritized sweeping into MARL scenario. However, this is a tabular reifforcement algorithm, thus unable deal with cases where state and action spaces are relatively large, or even continuous. In contrast to existing works, our algorithm is not only applicable to more general multi-agent problems, but also the first fully decentralized model-based reinforcement learning algorithm.
3 PROBLEM SETUP
In this section, we introduce multi-agent networked MDP and model-based networked system con- trol.
Networked MDP We consider environments with graph structure. Specifically, agents coexist in an underlying undirected and stationary graph G = (V,E). Agents are represented as a node in the graph, therefore V = [I,...nn n is the set of agents. E V x V comprises the edges that represent the connectivity of agents. Agents are able to communicate along the edges with their neighbors. Let N; denote every neighbor of agent i, and N, = N, U {t}. Furthermore, let N denote the k-hop neighborhood of i, i.e. the nodes whose graph distance to is less than or equal to k. For the simplicity of notation, also define No,- V N/5
2

---

Under review as a conference paper at ICLR 2022
The corresponding networked MDP is defined as (G. As local state 5; E S,, and perform action d, A,, The global state the concatenation of all local S == S X Sn. Similarly, the global action is = (a1,..., 0,)) A := Ai X ... x An. For the simplicity of notation, we define 8N; to be the local states of every agent in Nú, that is, given N₂ (f1,-..:el Je), then SN; (8)) 85.)- ON,,
Each agent i have their
states: ..., 5n)
are defined similarly. The transition function is defined p(s' ((s'(s,a) a) S x A S. Each agent possess localized policy Th (a: [s that is parameterized by 0g E Or meaning the local policy dependent only on states of its neighbors and itself. We use == (01..... 0x) to denote the tuple of localized policy parameters, and x (als) II ":
a (a, denote the joint policy, We also assume that reward functions is only dependent on local state and action: ri(8s, az), and the global reward function defined to be the average reward rss, a) E==1 (s( a,).
The goal of reinforcement learning is to maximize the expected sum of discounted rewards, denoted by n7:
oc
72
0
Egg arg max 7/(TT arg max n
Σ
re(se, at)
T²
72
where y E (0, is the temporal discount factor. We define the stationary distribution under policy be (s).
Independent Networked System Networked system may have some extent of locality, meaning in some cases, local states and actions do not affect the states of distant agents. In such systems, environmental transitions can be factorized, and agents are able to maintain local models to predict future local states. We define Independent Networked System (INS) as follows:
Definition 1. An environment is an Independent Networked System (INS) if:
p() ΠI ps px(((18,, ==1
INS might an assumption that is too strong to hold, However, for the dynamics that cannot be factorized, we can still use an INS to approximate it. Let Drv denote the total variation distance between distributions, we have the following definition:
Definition 2. (E- (e-eenend) Assume there exists an Independent Networked System p such that p(s' II'=1 ( v. a4). An environment is E-dependent, if: &
sup Drv (p(s a) 8.0
sup Σ 10(8'1s,)) p(8'1s, SE. 8.0. S'ES
To explain the intuition behind this definition, we point out that E actually the lower bound of model eгror when we use local models ,()), Recall that p(s'|s,a) a) is the real environment transition, p I[ (,, a.) is the product of marginal environment transitions. and p a) Il: (c(s/[5,,, a.) is the product of model transitions. Then the universal model error D(pli)) can be divided into two parts: dependency bias D(pl(p) and model error D(
D(pl(p) < D(pll)) + (p)
Then for É-dependent system, when models become very accurate, meaning D s O, sup D(pllp) sup D(plip) = E. While 1) can be any appropriate distance metric, we use the TV-distance hereafter for the ease of presentation. In the following, we develop theory under both INS and g-dependent scenarios.
DECENTRALIZED MODEL-BASED POLICY OPTIMIZATION
In this section, we formally present Decentralized Model-based Policy Optimization (DMPO), which is a fully decentralized model-based reinforcement learning algorithm. Compared with inde- pendent multi-agent PPO, DMPO is augmented in three ways: localized model, policy with one-step communication. and extended value function. We introduce the detail of localized model in 4. Pol- icy and value functions are introduced in 4.2 The illustration of our algorithm is given in Figure M All the components mentioned above are analyzed in Section We argue that under certain conditions, algorithm ensures monotonic policy improvement.
3

---

Under review as a conference paper at ICLR 2022
+
+
(a) Neighborhood
Value function
(c) Graph convolutional model
Figure 1: (a) presents the concept of neighborhood. If agent i is the node in purple, then purple and orange is N,, and combination of purple, orange and green is N (b) explains that extended value function takes SNy as input, here 3. (c) is the illustration of graph convolutional model.
4.1 DECENTRALIZED PREDICTIVE MODEL
To perform decentralized model-based learning, we let each agent maintain localized model. The localized model can observe the state of I-hop neighbor and the action of itself, and the goal of localized model is to predict the information of the next timestep, including state, reward and done. This process is denoted by (a(5), r/, &,,,,, 0:).
We implement a localized model with graph convolutional networks (GCN). Recall that agents are situated in graph G = (V,E). In the first step, a node-level encoder encodes local state into node embedding.
h = f pencode (s:). Then we perform one step of graph convolution as follows,
h(a)) (0.)) (h.. n2),, h frode Σ hag)).
(3)
e=(i))
In this way, hy is dependent only on 8, and a, Finally, node-level decoder generates the predic- tion of state, reward and done from h) as follows:
of ftaate (h+) + S4. = ffword (ht) fdone (ht).
Note that we predict the next state with skip connection, because empirically, it's efficient predict the change of the state rather than the state itself.
In practice, the data all stored locally by each agent. Data that collected in the environment by agent is denoted as De and those generated by predictive model is denoted as Dmodel
Scaling model-based methods into real tasks result in decreased performance, even if the model relatively accurate. One main reason is the compound modeling error when long model rollouts used, and model error compound along the rollout trajectory, making the trajectory ultimately in- accurate. To reduce the negative effect of model error, we adopt a branched rollout scheme proposed in (Janner al. 2019). branched rollout, model rollout starts from an initial state, but from state that was randomly selected from the most recent environmental trajectory Additionally, the model rollout length is fixed to be This scheme shown be effective in reducing the negative influence of model error both theoretically and empirically.
To deal with the bias of model trajectories, at each model rollout, we allow the algorithm to fall back to the real trajectory with probability go. where go is hyperparameter. We describe the detailed framework of model usage and experiment storage Algorithm
4.2 PROXIMAL POLICY OPTIMIZATION WITH EXTENDED VALUE FUNCTION
To optimize the policies, need to adopt algorithm that exploit network structure, whilst remaining decentralized. Independent RL algorithms that observes only local state are fully decen- tralized, but they often fail learn optimal policy. Centralized algorithms that utilize centralized

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Decentralized Model-based Policy Optimization (DMPO) for MARL
Input: hyperparameters: rollout length T, truncation radius
1: Initialize the model p. actor "H
9. and critic V,
2: Initialize replay buffers Denue and D.model
3: for M iterations do
4: Perform environmental rollout together, and each agent collect trajectory information TÜ.
5: for in N agents do
6: D = De U {
7: Train p," on Dr
8: Dimodel =
9:
for inner iterations: do
10:
Generate random number q ~ (O, 1).
if q > 40 then
12:
Dimodel Ti. [Fall back to real trajectory with probability 40-}
13:
else
14:
do Perform T T-sepp model rollout starting from s using policy Pv. append to Dmodel for G steps, i 0, ..... n do
for R rollouts,
15:
16:
Take step along the gradient to update πं and critic Vi on Dimadel
critics often achieve better performance than decentralized algorithms, but they might scale to large environments where communication costs are expensive.
We propose Proximal Policy Optimization with extended value function, which is defined as V((SN;) = E ye ~dn |E r; 1 $Nę E V. The intuition behind extended value func- tion comes from (Qu et al. 2020a). where truncated Q-function Q(syy= ax²) ) is initially proposed. In 5.3 we prove that Vi(NN; is a good approximation of Vi(s). with a difference decreasing expo- nentallyy with
To generate the objective for extended value function, or return R, we use reward-to-go technique. However, because model rollout is short, standard reward-to- go returns would get biased estima- tion of V. To resolve this issue, we add the value estimation the last state to the return. this way, with local trajectory T {(5) rf, (s') d', log m(), 0, 1,..,.. 1}, the objective of V is
T-1-1
R Σ 1 V ((5)
(5)
and the loss of value function is defined Cratue E DeDDemee [v RRmT'' In policy training, extended value functions Vú are reduced via communication to their k-hop neighbors to generate estimation of global value function,
V
MV n
(6)
JENS
and advantages Å, are computed on V. with generalized advantage estimation (GAF) Schulman al. 2015) for policy gradient update. The surrogate loss function of DMPO agent is defined
T (allb))) ((svr). ((s A((ov:))
Cpolicy
min
YI
8" n. (aflss)
mEDmodee
similar PPO-Clip loss.
The communication ş step might seem costly, yet information No is only used the training phase. We argue that in the training phase, algorithms are less sensitive with latency than execu- tion. Furthermore, since model- based learning can effectively increase sample efficiency, we might tolerate more communication.

---

Under review as a conference paper at ICLR 2022
5 THEORETICAL ANALYSIS
In this section, we analyze DMPO theoretically. 5.2 we derive a bound between the true returns and the returns under model in a networked system. 5.3 we prove that extended value function (i(s is good approximation of Vi(s), and with extended value function, the true policy gradient can also be approximated.
5.1 BACKGROUND: MONOTONIC MODEL-BASED POLICY OPTIMIZATION
Let n/[=] denote the returns of the policy in the true environment, n[ denote the returns of the policy under the approximated model. To analyze the difference between 7[m]] and fj(m], we need to construct bound
n 2 78 [ C(p. p. TT, TD);
where non-negative function, and TD the data-collest collectolllnngg policy. According to equation g if every policy update ensures an improvement of nf by at least C, n/ will improve monotoni- cally. This inequality was first presented in single agent domain (Janner al. 2019). In this work, we extend this to the multi-agent networked system, aiming to achieve monotonic team reward im- provement.
In this work, we let indicate collective policy I Tn.. and the model ý be INS ((s'ls, a) = II. pi(s] n., a.) that approximating the true MDP. In DMPO, each agent learns a localized model +;. policy Ti (I,,,,,), critic Vi(5xp), making it never trivial extension. We give the detailed analysis in 5.2
5.2 ANALYSIS OF RETURNS BOUND
In model-based learning, different rollout schemes can be chosen. The vanilla rollout assumes that models are used in an infinite horizon. The branched rollout performs rollout from a state sampled by a state distribution of previous policy TD, and runs T steps according to x. Based on different rollout schemes, we can construct two lower bounds. Under vanilla rollout, real return and model return can bounded by model error and policy divergence. Formal results are presented in Theorem 1 The detailed proof is deferred to Appendix C
Theorem 1. Consider an independent networked system. Denote local model errors as fm; max x, .,, (prvlp a.)li, N. aa)], and divergences between the data-collecting policy and evaluated policy as cx. = maxxN, Drv Drv(TD(als
(alz(as)sx)) )] Assume the upper bound of rewards of all agents is Tmax. Let rp" [ nn) denote the real returns in the environment. Also, let r 11| .... Nn. denote the returns estimated the model trajectories, and the states and actions are collected with TD. Then we have:
2r Vax
n
Exs n
NN,
|nP[ [TI,,,,,
17 [1
Tnll
S
(Em; + 2E
7
k=
Intuitively, the term Σr x++1 would be in the same magnitude as بيرر which might be huge given the choice of y, making the bound too loose to be effective. To make tighter the discrepancy bound in Theorem [] we adopt the branched rollout scheme. The branched rollout enables effec- tive combination of model- based and model-free rollouts. For each rollout, we begin from a state sample from dxpx and run T steps in each localized म;. When branched rollout applied an INS, Theorem 2 gives the returns bound.
Theorem 2. Consider an independent networked system. Denote local model errors as cm; max, w, oa Drv [p<(s as)li a.)), and divergences between the data-collecting policy and evaluated policy as <x. = max Dry[Tp(as (ails (ll (ag)s))) }} Assume the upper bound of rewards of all agents is Tmax- Let 1p ,.., un) denote the real returns in the environment. Also, let v branch [m1,... Nn) denote the returns estimated via T -stepp branched rollout scheme. Then we have:
117" [[TT,,.., nx] nz] branch [1 [1,... Tnll S
2r max
Σ
T-1
I
R+1
N + C. (
80
A+1 IN;
Cm,
1
i=1
k=
R=

---

Under review as a conference paper at ICLR 2022
Comparing the results in Theorem I aad
2 we can see that branched rollout scheme reduced the efficient before Cm, from Σk=0 A+1IN, I i- to Σx=o ) |N; E/ x
x(1-r²)
This reduction explains that empirically, branched rollout brings better asymptotic performance. Also, we set 7 this bound turn into a model-free bound. This indicates that when <m, lower than ea, allowed by our algorithm, model might increase the performance.
In reality, not every system satisfies the definition of INS, Yet we can generalize Theorem into E-dependent system.
Corollary 1. Consider an E-dependent networked system. Denote local model errors as 6m; :, ee Prv(p:(s)))
(.) 0.)], :()) and divergences between the data-collecting policy and evaluated policy as cx, maxxs Drv(TD DevlTtpaall (a N (ll(a [[ Assume the upper bound of rewards of all agents is Tmax. Let rf" [Ts... ..., Rn) denote the real returns the environment. Also, let prranch (T,,.. un] denote the returns estimated via T Ttep branched rollout scheme. Then have:
m
10p (TI,,,,, Tn. -1 branch [Tl Tnl
2r max
2r max
7)26
Em:
+ cx;
k=
k=T
The proof can also be found in Appendix Compared to Theorem 2 Corollary Lis more general, as is applicable to the multi-agent systems that are not fully independent. Intuitively, if a networked system seems nearly independent, local models will be effective enough. The bound indicates that when the policy in optimized in trust region where DTT, TD) S Ex., the bound would also be restricted, making monotonic update more achievable.
5.3 EXTENDED VALUE FUNCTION
In this section, analyze the effect of extended value function. The idea of extended value function (s(N)) comes from truncated Q-function Qi(ENT- anç) proposed (Qu et al. 2020a). We prove that extended value function is an approximation of the real value function. The detailed proof of Theorem is deferred to Appendix
Theorem 3. Define Vi((Np) EsNz, ddr Ei=o 1/10 sNy) and Vi(s) E r/1s0" s).
then:
(V((s) - Vi(sNz))
Tmax 1->
From Theorem it is straightforward that the global value function can be approximated with the average of all extended value functions: [V(s) En V.(sN;)) < Tima
functions are used for calculating advantages Á() (1) + (V( 1-y 7th In PPO, value (0))), and we have proven that (ss) can be estimated with the average of extended value functions EE= Vi(sN;) In practice, an agent might not get the value function of distant agents. However, we can prove that V/ = EjENN V5(N)g) ) is already very accurate for calculating the policy gradient for agent i. Theorem ijustifies that the policy gradients computed based on the sum of the nearby extended value functions is close approximation of true policy gradients.
Theorem Ler A, V
be the TD residual, and g, = B[ÁV,, v, log ग. (a s)] be the policy gradient. If A, and ÿi are the TD residual and policy gradient when value function (s) is replaced by V.(s) n EjENG Vz(SNy), ) we have:
R-1
No
99 Tel < 1-7 -22)
Tmaxfmax:
where Taax and 9max denote the upper bound of the absolute value of reward and gradient, respec- fively.

---

Under review as a conference paper at ICLR 2022
6 EXPERIMENTS
6.1 ENVIRONMENTS
We test algorithm in four environments, namely Figure Eight, Ring Attenuation (Wu et al., 2017a), CACC Catchup, and CACC Slowdown (Chu et al. 2020). Detailed description and visual- ization of these environments is deferred to Appendix
Cooperative Adaptive Cruise Control The objective of CACC is to adaptively coordinate a pla- toon of 8 vehicles to minimize the car-following headway and speed perturbations based real-time cehicle-to-vchicle communication. CACC consists of two scenarios: Catch-up and Slow-down. In CACC Catch-up, vehicles need catch up to the first car. CACC Slow-down, every vehicle is faster than the optimal speed, and they need to slow down without causing any collision. The agents receives negative reward if the headway or the speed is not optimal. Also, whenever collision happens, huge negative reward of -1000 is given.
Flow environments This task consists of Figure Fight and Ring Attenuation. The objective of these environments is letting the automated vehicles achieve target average speed inside the road network while avoiding collisions. The state of each vehicle is its velocity and position, and the action is the acceleration of itself. In Ring Attenuation, the objective is to achieve high speed, while avoiding soop-and-go loops. Vehicles are rewarded with their speed, but also punished for their accelerations. In the perspective of networked system, assume that the vehicles connected with the preceding and succeeding vehicle, thus resulting in a loop-structured graph.
6.2 BASELINES
We describe the following algorithms for performance comparison:
Centralized PPO learns a centralized critic Vi(s). This baseline aims to analyze the performance when k is set to be arbitrarily huge, and is used in (Vinitsky et al. 2018 benchmark algorithm for networked system control.
CPPO:
IC3Net (Singh al. 2018): A communication based multi-agent RL algorithm. The agents maintain their local hidden states with a LSTM kernel, and actively determines the com- munication target. Compared with DPPO, IC3Net uses hidden state and continuous com- munication, whereas DPPO agents directly observe the states of their neighbors.
DPPO: Decentralized PPO learns an independent actor and critic for each agent. We im- plement it by using neighbor's state for extended value estimation.
DMPO (our method): DMPO is a decentralized and model-based algorithm based on DPPO. On top of it, we use decentralized graph convolutional kernel predictive model.
6.3 RESULTS
Figure shows the episode reward v.s. number of training samples curves of the algorithms. We address that CACC environments, DMPO uses decentralized SAC as base algorithm. Similar with DPPO, decentralized SAC uses extended Q-function Qi(s aN!") for its policy gradient. From the results, we conclude that our algorithm matches the asymptotic performance of model-free methods. It also learns the policy faster, resulting in increased sample efficiency.
The comparison between DMPO and DPPO can be viewed as an ablation study model usage. In figure eight, DMPO increases sample efficiency at the beginning, but as the task becomes difficult, the sample efficiency our method decreased. In a relatively easy task, ring attenuation, our method increased sample efficiency massively, compared with its model-free counterpart.
The comparison between the asymptotic performance CPPO and DMPO or DPPO can be viewed as an ablation study of extended value function. From the result in four environments, we ob- serve that the asymptotic performance of CPPO does not exceed that the algorithms that uses extended value function. In this way, conclude that by using extended value function, tralized algorithm can be decomposed into decentralized algorithm, but the performance would not drop significantly.
8

---

Under review as a conference paper at ICLR 2022
Figure 3 shows the accuracy of our model in predicting the reward and state during training. The ror is defined as the ratio of MSE loss to variance. From the figures, we conclude that neighborhood information is accurate enough for model to predict the next state in these environments. However, in CACC Slow-down, local models might fail to learn the reward. We observe that the erros may increase as the agents explore new regions in the state space.
370
-2000
200
230
-5030
DaR Eiie
(a) Figure Fight
(h) Ring Attenuation
392
030
5.0
320
203
230
GIFO
IPPO
Dero
-120
50000
120000
150000
230208
230002 300000
350080
-120
200082
400000
COOO00
860000
2000000
CACC Catch-up
(d) CACC Slow-down
Figure 2: Training curves on multi-agent environments. Solid curves depict the mean of five trails, and shaded region correspond to standard deviation.
10
10
10
10
10g
1eg
agh1
agg1t
20000
40000
63003
20302
230080
20000
40000
63020
80300
230303
(a) State Error
(b) Reward Error
Figure 3: Figures of state and reward error. Both state error and reward error < 10% in every environment.
7 CONCLUSIONS
In this paper, we propose algorithm DMPO, model-based and decentralized multi-agent RI. algo- rithm. We then give a theoretical analysis on the algorithm to analyze its performance discrepancy, compared with model-free algorithm. By experiments in several tasks in networked systems, we show that although our algorithm is decentralized and model-based, it matches the asymptotic performance of some of multi-agent algorithms. From the results, also conclude that using extended value function instead centralized value function did not sacrifice performance massively, yet it makes our algorithm scalable.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Masako Bando, Katsuya Hasebe, Akihiro Nakayama, Akihiro Shibata, and Yuki Sugiyama. Dy- namical model of traffic congestion and numerical simulation. Physical review E, 51(2):0035 1995.
Eugenio Bargiacchi, Timothy Verstracten, and Diederik M. Roijers. Cooperative prioritized sweep- ing. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), pp. 160-168. IFAAMAS, 2021.
Bruno Bouzy and Mare Métivier. Multi-agent model-based reinforcement learning experiments in the pursuit evasion game. 2007.
Ronen Brafman and Moshe Tennenholtz. A near-optimal polynomial time algorithm for learning in certain classes of stochastic games. Artificial Intelligence, 121(1-2)31-477 2000.
Tianshu Chu, Sandeep Chinchali, and Sachin Katti. Multi-agent reinforcement learning for net- worked system control. In International Conference on Learning Representations (ICLR), 2020. URL
net/foruu 1d=Syx7A3NFVV A33NPv
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In Advances in Neural Information Processing Systems (NeurIPS), volume 1, pp. 1523-1530, 2001.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model- based policy optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
I Ge Jin and Gábor Orosz. Dynamics of connected vehicle systems with delayed acceleration feed- back. Transportation Research Part C: Emerging Technologies, 46:46-66 64, 2014.
Leslie Pack Kaelbling, Michael Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
Yuping Luo, Huazhe Xu, Yuanzhi Li, Yuandong Tian, Trevor Darrell, and Tengyu Ma. Algorithmic framework for model-based deep reinforcement learning with theoretical guarantees. In Interna- tional Conference on Learning Representations (ICLR), 2019.
Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi ageet reinforcement learning for networked systems with average reward. Advances Neural Information Processing Systems (NeurIPS), 33, 2020a.
Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning of localized policies for multi-agent networked systems. Learning for Dynamics and Control (L4DC), pp. 256-266. PMLR, 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 International Conference on Machine Learning, pp. 4295-4304 PMLR, 2018.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839)6004660) 2020.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02435 02438. 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06347, 2017.
10

---

Under review as a conference paper at ICLR 2022
Thiago D Simao and Matthijs TJ Spaan. Safe policy improvement with baseline bootstrapping in factored environments. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), volume 33, pp. 4967-4974, 2019.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when communicate at scale in multiagent cooperative and competitive tasks. arXiv preprini arXiv: 11X2::/8/2.09755, 2018.
Wen Sun, Geoffrey J Gordon, Byron Boots, and Bagnell. Dual policy iteration. Advances in Neural Information Processing Systems (NeurIPS), 31:7059-7065 2018.
Eugene Vinitsky, Aboudy Kreidich, Luc Le Flem, Nishant Kheterpal, Kathy Jang, Cathy Wu, Fangyu Wu, Richard Liaw, Eric Liang, and Alexandre M Bayen. Benchmarks for reinforce- ment learning in mixed-autonomy traffic. In Conference on robot learning, pp. 399-409, PMLR, 2018.
Cathy Wu, Aboudy Kreidich, Kanaad Parvate, Eugene Vinitsky, and Alexandre Bayen. Flow: Architecture and benchmarking for reinforcement learning in traffic control. arXiv preprint arXiv:1710.05465, 10, 2017a.
Cathy Wu, Aboudy Kreidieh, Eugene Vinitsky, and Alexandre M Bayen. Emergent behaviors in mixed-autonomy traffic. In Conference Robot Learning, pp. 398-409 PMLR, 2017b.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. International Conference on Machine Learning (ICMI.), pp. 5872-5881, 2018.
Kaiqing Zhang. Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms, 2019.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. Advances Neural Information Processing Systems (NeurIPS), 33, 2020.
11

---

Under review as a conference paper at ICLR 2022
A
EXPERIMENT DETAILS
The code of our algorithm can found at Ai-aagorithms--
A.1 ENVIRONMENT DESCRIPTION
The objective of CACC is to adaptively coordinate line of vehicles to minimize the car-following headway and speed perturbations based on real-time vehicle-to-vchicle communication, We conduct experiments on two scenarios: CACC catch-up, CACC slow-down. The local observation of cach agent consists of headway h, velocity v, acceleration a and is shared neighbors within two steps. The action of each agent is to choose appropriate hyper-pane troller Bando et al. (1995,, selected from four levels parameters (8) for each OVM con- where a", 3 denotes headway gain and relative gain for OVM controller respectively. The reward function is defined as (h.,, - h )² (Vt, )²)² + 0.1a to punish the gap between the current state to target state and speed perturbations, where the target headway and velocity profile are ht 20m and of, respectively. Whenever a collision happens (hi,e < 1m), a large penalty of -1000 is assigned to each agent and the state becomes absorbing. An additional cost 5 (2hat hi,)) is provided in training for potential collisions. In catch-up scenario, initial headway of the first vehicle is larger than the target headway, thus the following agents learn how to catch up with the first vehicle, where target speed V/ / and initial headway h1,0 ha,0, Vi o 1. In slow-down scenario, target speed or linearly decreases 15m/s during the first 30s and then stays constant, thus agents learn how to slow down speed cooperatively, where initial headway hą h.
Flow environments consists of Figure Eight and Ring Attenuation. The objective of these environ- ments is letting the automated vehicles achieve a target average speed inside the road network while avoiding collisions.
The figure eight network, previously presented in (Wu et al. 2017b), acts closed representation of an intersection. In a figure eight network containing a total tion of queues resulting from vehicles arriving simultancously at the intersection and slowing down to obey right-of-way rules. This behavior significantly reduces the average speed vehicles in the network. The state consists of velocity and position for the vehicle. The action is the acceleration of the vehicle a E IR (Amii Aemax] The objective of the learning agent is to achieve high speeds while penalizing collisions. Accordingly, the local reward function is defined as r, = Udes Vdee - Vz|. where Udes is an arbitrary target velocity.
vehicles, we witness the forma-
In Ring Attenuation, the objective is to achieve a high speed, while avoiding acceleration- deceleration loops. To achieve this, vehicles rewarded with their speed and punished for their accelerations. The state and action of each vehicle is the same as Figure Eight. In the perspective of networked system, assume that the vehicles connected with the preceding and succeeding vehicle, thus resulting in loop-structured graph.
KAI ES EXL THE
(a) CACC
(b) Figure Fight
(c) Ring Attenuation
Figure 4: Visualization of CACC and Flow environments. (a) A line of vehicles that need to keep a stable velocity and desired headway. (b) Vehicles travel in figure eight shaped road section to learn the behavior an intersection (c) Vehicles travel in a ring to reduce stop-and-ge waves.
12

---

Under review as a conference paper at ICLR 2022
B HYPERPARAMETERS
We list some of the key hyperparameters for DMPO and DPPO in Table 1 and
Scenario
Catch Up
Slow Down
Figure Eight
Ring Attenuation
Hyperparameter
Learning rate of critic
3e-4
3e-4
5e-5
5e44
Learning rate of π
3e-4
3e-4
5e-5
5e-4
Learning rate of Model
3e-4
3e-4
5e-4
5e-4
Clip
0.15
0.2
GAE A
0,5
0.5
KL target
7.5e-3
0.01
Model usage probability
1
0.5
0.5
Rollout Length
1
25
25
Table 1: Hyperparameters for DMPO.
Scenario
Catch Up
Slow Down
Figure Eight
Ring Attenuation
Hyperparameter
Learning rate of V
7e-4
5e-4
5e-4
lc-3
Learning rate of æ
5e-5
5e-5
5e-5
1e-3
Clip
0.2
0.2
0.2
0.2
GAE À
0.5
0.5
0.5
0.5
KL target
0.01
0.01
0.01
0.01
2
3
Table Hyperparameters for DPPO.
C PROOF THEOREMS
C.I REMARKS ON PROOFS OF LEMMAS AND THEOREMS
To bound the returns, we use TV distance to assess the distance between 8t, a; at every timestep. based on the fact that BB..,,pi (8;, a;) - Es 7(s,, 0:)l S Tmax Drv (lp2). To achieve this, argue that in INS, sf only depends Xx which is the 1-hop neighbors' states previous timestep. Then, inductively, sf is only dependent on T-1 T-2
T-1
s... T-k and ultimately, N! N? ,.... No
6 NN.. Then we consider chain of states x² N 1, 0, I,.,, N in Lemma 4 to analyze how
sf depends model errors and policy divergences in step-by-step manner. Insipred by Janner et al., by summing the divergence at each timestep t = 0, 1..., we can generate overall discounted returns bound of branched rollout in Lemma 5 Lemma is simple corollary of Lemma 5 which handles normal rollout scenario.
If the returns bounded, the real return would also almost monotonically increase. Specifically, if *+] p[ C, combined with n|*++1| 2 Í][-*] C, we have n n But note that n increases monotonically, and it's lower bound of n[**+1] This means that *+1=++]] would almost monoton- ically increase.
show that if every optimization step increase the return by C,
C.2 PROOF OF THEOREM
Proof. 17" (T.,,..... nT. and 17d [1 ... nn. differs in two ways. First, they estimated with different transition dynamics. Second, the latter sample their states and actions with another policy, namely intermediate return r/mp), which is the
TD- To deal with these divergences separately,
13

---

Under review as a conference paper at ICLR 2022
return of TD in the environment. Then the difference be bounded by:
Ing (T...., Tnl ny [T......TTTT nnlll S Ing [1. Tal
of
[TD]
[TDl
188
11
Tnll
(9)
L1
L2
To bound L1, we apply Lemma with Em; = 0. Then:
2r max
L1 S
Exx
b+1
(10)
km
JEN
In I2, both the dynamics and policies and different, therefore:
L2 S
2r max
CT.
+
Σ JENK
(Cmy + G,,)l.
(11)
R= 0
Putting Equation 10 and 11 yields:
Inf m1,- nn) of 1..
Nnll
2r mamax
2
k+1
Σ
(Emy 26x))]-
(12)
k=
JENK
And because the binary relation k-hop neighbor symmetric, we have:
1 n
n
VV
ΣΣ
9=
(13)
n
1= JEN!
j=1
Then, by averaging Equation 12 we have:
In
[1
nnl
17 [T1 ... Jnl
"p [ I..... nm)
1/'2 [TI,, [TII..,, Tn]
==1
max
1
S
CT.
+
(Emy + 26,,)]
1 -
n
1=1
k=0
1=1 JENZ
(14)
max
1
Ex,
+
k++
(Em: + 2En,))
1
11 i=1
n
k=0
2r
max
n2
Cri
Σ k+1 N
+ (em, + 2Ex.)
1
n
n
C.3 PROOF OF THEOREM 2
Proof. To bound [17] Tn. 17 brannch [T], T, we need to analyze how do they differ from each other. 1/" denote the real returns these policies in the environment. prrnnch is the returns esti- mated in the branched rollout scheme. To explicitly illustrate this point, we describe their difference in Table
By Lemma
5 we have:
T-1
2 +
In [T1, Tal 17. branch [T,
Fall
5
max
k+1
Σ
Cm;
Σ
k-1 Σ Enyl
(15)
km
JEN
K=T
JEN!
14

---

Under review as a conference paper at ICLR 2022
branch point
before
after policies
dynamies
policies
dynamics
7
p
π
1) Franch
TD
P
Table 3: The difference between 1/" and branch
And because the binary relation of k-hop neighbor is symmetric, have:
|V
9
C-
(16)
JENT
j=1
Then, by averaging Equation 15
we have:
by | 1 ....
nnl
branch ... nzl
mnf [T. .... Tnl
branch
[T: Tnl
2 max
Cm,
Ex,]
k=0
jENK
k=T
jEN
(17)
max
|
Em,
+
k+1
N
Ests
1
n
k=0
k=T
i=1
2 max
N
N
k+1
+ 6x/
k+1
1
k=0
k=T
C.4 PROOF OF COROLLARY 1
Proof. Although p(s'|s, a) might not satisfy the criteria of an INS, we can construct another transition dynamic p = I P. (8, at), which is the product of marginal transitions, thus being an INS. Recall that by definition, if p is transition dynamic of g-dependent system, sup,,a s.u DTV (p(811s a) (l((s'(ss,)) < &. Then we divide the difference into two parts:
1/ [TI,,... kn] branch [TI,..., T..
|' Tnl 17 [mT,... Tn. + 17 [T Tn)
branch
(18)
Tn
L1
The first part is the difference of policy returns, estimated in two environments. Since there are no policy divergences, and the transition dynamics only differs in global manner, utilizing Lemma yields that:
(s, S Eg.
(19)
Then, we have:
L, 1/|TTI,.., Tn]
(TT,,,,.,, Tn.
< max
7 "Dv (o
1=0
(20)
< 2n max
7'tE
2rmax
1 7 5.
1 γ
15

---

Under review as a conference paper at ICLR 2022
As for L2, because is INS, directly apply Theorem 2
2r max
T-1
No.
L -
+
Ex.
(21)
n
n
R=
Summing Equation 20 and Equation 21 completes the proof.
C.5 PROOF OF THEOREM 3
Proof. (Qu al. 2020b), it was proven that if aNd and aNy are fixed, then no matter how other states and actions changes, Q Q-function will not change significantly:
[Q(sN;: aNp, SN ,N Q(SNy " aNy, s'wc, d'n 5
Tmax
(22)
As value function is the expectation of Q-function
(s(s) Q
(23)
Vi(SNz)) = Eura ONT),
we have,
[V((s) V.(oN;)1 |Bax ((5,a)
E Q(NN,
S Enn ((5, (NNN).aN))
(24)
x r maxx
y
which concludes the proof.
C.6 PROOF OF THEOREM
4
Proof. The difference of the gradients can be written as
9: 0: =E(A- o log (a:1oNN))
- Σ Á, (ogs)() + E Σ (A, - V,) (agss()))sx,)
1
11
JEN
JEN
El
Σ (1((5))))+(((())) (o
n
JENS
+ E Σ
(()((),))) - - (V5((())) - Vg(Nn; Vo, log (a.ls()))).))
JEN
=I, + L2.
(25)
Because for any function b(s) that depends only E[b(s) ". (alss,)) = 0.. Therefore, L2 in Equation 25 becomes:
L2
Σ
7IV3(8') - V3(''s (og
n
JEN!
(26)
NN
x++1
1-7 T TmaxXruss
n
For L,, note that 1y(8), az) + (V' Vi(s) -V) ry),,,, + EE By (s),, + > y=='V((s"1 (s""".). And in an INS, s aj,t t 0, b.1,.... 2 not affected by policy n. if & N., we k-...--2...
have that
L < E Σ
ly - || log (a,lss))))))
JEN
(27)
No. x
<1
maxxImax-
16

---

Under review as a conference paper at ICLR 2022
Put Equation 26 and 27 together, have
gi Dvl 1
L1|
Le
N
y
x+1
No
xk1
mmax9max (1
mmaxxmax
71
n
(28)
7 xK
No
(1
72)
I
F'max Imax.
7
n
D USEFUL LEMMAS
Lemma 1. (TVD of Joint Distribution) Consider distributions pi (1( y) pi (x))r(y) and p2(x,y) = P2(2 (2()))2(u) The total variation distance between them can be bounded as:
Drv (2) (22 v)) s Drv (pi()))p))))z) Ezwps (Drv
s Drv (pi (x)))(()>< max Drv (p
Proof.
Drv (pi(x, (1)p2(2)
Σ (2, p2(2,8)1
2,8
Σ (m(p)pp(
2,
1
(=((=)p)((l)) ((lpDpuuhh--ppolllll)))-------dd paa(s)a((la))
2,
1
S (x) (o(())))()))))) -
2,
R.M
1 Σ (x) -2())))()) Σ (rve))DDvv
(pr Er-py (Prv (rrp
< Drv(p((=)lp2(z)) + (
Lemma 2. Suppose there are two chains of distributions {at, 1 > 0}. 0}. At time t, the
states of both chains share an identical state space æf, xh Xt. Suppose these two chains satisfy
a Makkov-like property: 1 (x*+1 "',,,..'', ,x0) = p (x (2'). Then, the TVD of distributions
of two chains time can be decomposed as:
Drv Crv(pi (xT((") (lTT s
Σ t=1
E E DDV DDV (pf(al ")pp (aa 12) ">)pl
Proof. We prove this lemma by induction.
When T 0, it's easy that this lemma is true.
17

---

Under review as a conference paper at ICLR 2022
Assume it is true for T = k. We have:
11 (x 12 + (2chtt)
x+1 (xe 1 |x )pl (xx²)
x
<
p2 +++
pi
+
|r^* 2タ + ( (مم + ||- )1 + p x (2 (p) p (>*))) |
[IP]
11
+ (1 | Σ (
| -
DTV (r ( (x+ 11n2t (1b++((**)))
1
1p ++1 (2x - -2 + (zo (+1)
2 *tll
1
Σ
Eyp [1p] x++ (aa
( 1z+)) p2 + (2*
$
x++1
Σ
pl
x+ (a. 11
(x*)) pb(1))))
zt
-Egrops Drv (p) x-+1 (1 >1>> r+t ( + (2t
SDrv (pTv(1(6")110(6>>
Σ Eet ~mp:-1 Drv (vi (2*")=
Then this theorem holds for all n E N.
Lemma 3. Consider two distributions with pdf/pmf p(x) and g(z). where (II, Fnn RR". (:();), ((x)
Suppose and q can be factorized as: p(x) = -I
= -I qz(xz). Then we have:
Divlp(=)la(2)1 < Σ Dav (n(xa)laa
Also, if the distance is measured by KL-divergence, we have:
Dkulp(=))a(z)) = Σ (xLlp((a))ll(a...)....
18

---

Under review as a conference paper at ICLR 2022
Proof. We prove this result for discrete distributions, yet by replacing sum with integration, this result stays true in continuous case.
DTV (x))))
Σ (p(x) {(x)]
II g (xx))
2
Jmm
Jmn
Ph
II (=x)))(()))))))))))))))))))))))) (x:)) A=++1
(x
II eu (=x))(a:( -x)))) k=++1
[p((x;) (zx1)
DTV (rv(ps(s))llaaxss)))
In KL-divergence case, we have:
Σ p(xx) log p(x)
DxLlp(=))l(<>)] =
q(x)
log pz(2z))
Σ
p p Fnl
qs (x;)
log Ps (x()))
Pk (xx)
g: (xx)))
Σ Pa(a.) log (x;))
Σ
(z(2,)
(ru(p((=))la(t)))
Lemma 4. (N-step distribution distance) Suppose the expected TVD between two dynam- ics transitions is bounded as 6m, maX4N,00 Drv [p(s[[a,, ())s,((s( a.) and e., max, DTv (T. (a,(ss))) [ (s.))))))))) I < K, the N-step distribution distance bounded as:
N-1
Drv (s:)] <
Σ JEN
(Gry + Cmy))
t=0
Thus,
N-1
Drv (si, an)li (s)) s cn +
Σ Σ t=U
(CT, + Cmy).
JENS
Proof. Consider chain of regional state x² NN. Two chains of distributions p' p'(x',, p(x') denote the distributions of x under the environment and our model, respectively. First, because of the property of an INS, these two chains' transition dynamics be decomposed as:
19

---

Under review as a conference paper at ICLR 2022
p(a")a/~1) -1( po(5)(ov;).
II JENN
And because py(d//sv,) Ea, Pi az (ayss,,,, ). by the property of TVD, we know that:
Drv (nrp sn, + 6my
With Lemma 3 we have:
DTv "
11
z Σ
(Eng Emy).
JENN-
Then, by Lemma 2
we know that
Drv Drv(p (s:)lle (s:)) = Drv [p:N (x )1o (x^)]
N
(ETz + 6m3) JEN
1=1
N-1
(Ery + &my)s
JEN
which completes the proof of the first part. And by Lemma I the second part holds true.
Lemma 5. (Returns bound measured in branched rollout) Consider two MDPs p(s) and p(s). Sup- pose they both adopt -brancceed rollout scheme. Before the branch, suppose the dynamics dis- tributions are bounded as maX Drv (p (5'])N,, al)," (s] a:)) (
c and policy divergences are bounded as maXsN, DTV (Tv pre )llls, (arlsN,)) = e After the branch, post and exost are defined similarly. Then the (local) T-step returns are bounded as: rn
2T max
b1 ijl
post
Σ k+1
post
post
(re t
JEN
JENt
Proof. We prove this by estimating the state-action distribution divergence at each timestep. For notation simplicity, denote <xx Nx EeeN (etr + erre), and e analogously. If we divide the chains into two parts: pre-branch and post-branch, and apply Lemma on both parts, we have:
For < T:
Drv (1) s post
post N
and for >>> T:
T T-1
Drv ( as)l) s post
post
pre Nk
Nk
k=0
T=T
20

---

Under review as a conference paper at ICLR 2022
Then, the difference of discounted distribution can be bounded as:
Drv [pr(s, a.)l) Drv[p(ss.a::)) - -2
Drv a
r
< 7)
post
post
)+
Nu
1=0
k=0
T-1
(1- 7)
Σ
post
post N
pre CNy
1=
k=
k=T
T-1
post
+ (1 7)
post
(7 h+1 + g + ...)+
No
h=
20
pre
(2 k-1 + xx ...)
No.
k=T
post
post k+1 No
+
N 7
pre h+1
k=0
k=T
We can convert this bound into the returns bound:
In
mol
(r ai) - -r.(s).
t=0
2r max (1 7) Σ Drv (p) (1)l(((s))))))
<
2 max
DTV [ps(si, ai))lid(si, ai)
T-1
2F max post
cx;
post
No
k+1
+
No
pre N+1]
k=
Lemma 6. (Returns bound measured in full length rollout) Consider two MDPs p(s) and p(s). Suppose they both run their rollouts until the end of every trajectory, and the dynamic distributions are bounded as maxsx, .a DTV (pr(s)) NN, 0z) (s). az)) fm. while policy divergences are bounded as max.N, Drv (T.(aa) al
Cr.- Then the (local) returns bounded as:
2r max
8
In: no 5
Cx.
+
h+1 Σ (em, En2)]
JENT
Proof. We can think it as a special case of branched rollout, where post pre = c for every subscript, and T O. From this perspective, applying the result of Lemma compleeess the proof.
21


Reviews:
[{"review_id": "bl9xdFgWweN", "reviewer": "Reviewer_2Aak", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "It is certainly necessary to have decentralized multi-agent reinforcement algorithm to solve problems such as autonomous driving, wireless communications and multi-player games. There are a few places I believe that the authors can significantly improve their paper. \n\n1) The insight and essence of the DMPO algorithm are not adequately addressed. For the three key components: localized model, policy with one-step communication, and extended value function, other than the extended value function the purpose of the other two are not really explained well. As a consequence, Sec. 4.1 and 4.2 really very difficult to understand. Also, a complexity analysis of the algorithm is very desirable.\n2) As pointed out by the authors, the effective of theoretical bounds depends on the selection of the discount factor. This limits the selection of the rollout T, since when T become large, then the advantage of the expressions in Theorem 2 will go down significantly; This also limits the the effective of Theorem 3.\n#) In the numerical experiments,DMPO does not stand out as a significant improvement, maybe more experiments can be conduct to demonstrate the effectiveness of the algorithm. ", "summary_of_the_paper": "The authors proposed a decentralized multi-agent reinforcement learning algorithm, provide theoretical bounds on its performance, and conducted numerical experiments on its performance. ", "summary_of_the_review": "Overall, both the theoretical results and experiments can be strengthened to make a better case for the proposed algorithm. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9JsjKVTg0d", "reviewer": "Reviewer_QuxM", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Q1. The current study assumes that the target system is an independent networked system or \\ksi-dependent system. First of all, the used assumptions sound to be too strong to model realistic multi-agent systems. For example, the assumption that the reward function is only dependent on local state s_i and the local action a_i makes the entire system to be interacting through the joint state transition rather than interaction through the reward. Furthermore, the transaction of an individual state only depends on the action of the corresponding agent. Would you please discuss the problems or characteristics of the target system where the proposed assumptions hold? \n\nQ2. The proposed assumptions are held in the target problems (environments) used in this study? What are the common aspects of these environments, and why are these environments particularly selected? In other words, the used environments are representative environments where the proposed method can work nicely? As the authors mentioned, there is no single MARL algorithm that can solve all different problems. Therefore, it would be nice if the authors describe the characteristics or examples of the target problem where the proposed assumption and the proposed method work nicely.\n\nQ3. The idea of model-based MARL is loosely explained. Section 4.1 discusses constructing a local state transition model using GCN, and section 4.2 discusses the PPO algorithm with a truncated value function. First of all, the paper does not explain how to use the learned local dynamic model is used in training the value function and policy. Although the procedure is loosely explained in Algorithm 1, the notations used in Algorithm 1 are not fully explained. Furthermore, if the trained model is used to generate sample trajectory for model-free MARL, the proposed method's algorithmic novelty in developing model-based MARL is very limited. There should be more diversified ways to use the learned dynamic models to learn decentralized policy better. The author should investigate these approaches.\nQ4. The dynamic models in MARL are generally composed of (1) environmental transition given the current joint state and the joint action and (2) the behavior models predicting other agents’ action given the current state. The current study only focused on a limited version of (1) while ignoring (2). \n\n\nQ5. What are the relationships between sections 5.2 and 5.3? Each section seems to discuss independent analysis. For example, 5.2 discusses return bound when performing rollout, while section 5.3 discusses error bound for the truncated value function and policy gradient. Are these results are an extension of the previous study? If yes, what are the new aspects? In addition, how can these analyses be used to prove the effectiveness of the proposed model-based MARL? Is there any chance that these analysis results can be integrated and used to show that the proposed independent networked system assumption can effectively solve the target problem? Please elaborate on the significance and meaning of each theorem in terms of how the proposed method solves the target problem. \n\n\nQ6. The assumption used for modeling the independent dynamic model is not used for estimating the truncated value function. \n\n\nQ7. Experiment results are not sufficient to validate the effectiveness of the proposed method. Particularly, the proposed method does not excel other baselines when the target problem is complicated. The model-based approach should be beneficial, especially for complex problems. In addition, what is the intention of comparing the approximation errors for different environment models?\n", "summary_of_the_paper": "This paper proposes a decentralized model-based reinforcement learning algorithm for networked multi-agent systems where cooperative agents communicate locally with their neighbors. ", "summary_of_the_review": "Although the current study discusses a vital topic in MARL, the current study focuses very limited class of MARL with quite strong assumptions. The theoretical analysis can be possibly considered novelties for the current study; however, the importance and the meanings of the theoretical analysis are not fully explained in the present paper. Finally, the experiment results are too limited to validate the effectiveness of the proposed method.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-PkAIWhwol", "reviewer": "Reviewer_mC6k", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths: the theoretical analysis is solid.(the reviewer did not check the correctness).\n\nWeaknesses:\n1.\tThis paper incorporates several ideas to develop a decentralized RL algorithm. Compared with previous works on centralized, model-free, and tabular settings, this work investigates decentralized, model based, and deep learning model settings. However, from each single viewpoint, from centralized to decentralized, for instance, the problem has been addressed in prior literature. This makes the present study seem to be an ensemble of well-developed techniques. In this context, the authors are expected to justify their contributions by showing that the theoretical analysis is not a trivial integration of existing analysis schemes, if it is not. In other words, please clearly state the challenges and novelty of the paper.\n2.\tThe improvement of sampling efficiency comes at the cost of training predictive models. Do the sampling savings compensate for the training cost? Is it possible to show that the learning process with the proposed model-based approach is more efficient in terms of time?\n3.\tAs pointed out in the empirical study section, the predictive model might fail to learning the reward for CACC slow. What is the reason? Does this imply the proposed model-based scheme is not stable in some circumstances. The robustness of the method is also not verified. Maybe including more complicated RL tasks in the experiments will make the work more convincing and solid.\n4.\tTypos:\nabstract: exponential -> exponentially, \nParagraph 1 on page 3, Each agent possess a localized …, possesses\nParagraph 1 on page 3, … reward functions is …, are\nLast paragraph on page 4, Independent RL algorithms that observes only… , observe \n\n", "summary_of_the_paper": "This paper proposes a model-based decentralized RL algorithm. Theoretical analysis is presented, and the theoretical results are validated with empirical studies on several vehicle cooperative cruise control tasks.", "summary_of_the_review": "The novelty and the contributions in theory are not obviously presented. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: As pointed out by reviewers, the presentation needs to be improved to clarify the algorithmic and theoretical contributions.
Decision: Reject