Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation
Authors: Lipeng Wan
Xuwei Song
Xuguang Lan
Nanning Zheng
Venue:  (2021)
Keywords: multi-agent reinforcement learning
policy optimization
advantage estimation
credit assignment

Abstract: Cooperative multi-agent tasks require agents to deduce their own contributions with shared global rewards, known as the challenge of credit assignment. General methods for policy based multi-agent reinforcement learning to solve the challenge introduce differentiate value functions or advantage functions for individual agents. In multi-agent system, polices of different agents need to be evaluated jointly. In order to update polices synchronously, such value functions or advantage functions also need synchronous evaluation. However, in current methods, value functions or advantage functions use counter-factual joint actions which are evaluated asynchronously, thus suffer from natural estimation bias. In this work, we propose the approximatively synchronous advantage estimation. We first derive the marginal advantage function, an expansion from single-agent advantage function to multi-agent system. Further more, we introduce a policy approximation for synchronous advantage estimation, and break down the multi-agent policy optimization problem into multiple sub-problems of single-agent policy optimization. Our method is compared with baseline algorithms on StarCraft multi-agent challenges, and shows the best performance on most of the tasks.

Under review as a conference paper at ICLR 2021
MULTI-AGENT POLICY OPTIMIZATION WITH APPROX- IMATIVELY S SYNCHRONOUS ADVANTAGE ESTIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
Cooperative multi-agent tasks require agents deduce their contributions with shared global rewards, known as the challenge of credit assignment. General methods for policy based multi-agent reinforcement learning to solve the chal- lenge introduce differentiate value functions or advantage functions for individual agents. multi-agent system, polices of different agents need to be evaluated jointly. In order to update polices synchronously, such value functions or advan- tage functions also need synchronous evaluation. However, current methods, value functions or advantage functions use counter-factual joint actions which are evaluated asynchronously, thus suffer from natural estimation bias. this work, we propose the approximatively synchronous ad advantage estimation. We first de- rive the marginal advantage function, an expansion from single-agent advantage function to multi-agent system. Further more, introduce policy approxima- tion for synchronous advantage estimation, and break down the multi-agent policy optimization problem into multiple sub-problems of single-agent policy optimiza- tion. Our method is compared with baseline algorithms on StarCraft multi-agent challenges, and shows the best performance on most of the tasks.
INTRODUCTION
Reinforcement learning(RL) algorithms have shown amazing performance on many single- agent(SA) environment tasks (Mnih et al.] (aderbbgg al.] (0h6)) et al. 2018). However, for many real-world problems, the environment is much more complex where RL agents often need to cooperate with other agents. For example, taxi scheduling (gguuyn et al. 2018) and network cCht et al. 2019).
In cooperative multi-agent tasks, each agent treated as an independent decision-maker, but can be trained together to learn cooperation. The common goal is to maximize the global return in the perspective of a team of agents. To deal with such tasks, the architecture of centralized training and decentralized executions(CTDDS is proposed(Oliehoek & Vlassis 200g) et al.) (016)). The basic idea of CTDE is to construct a centralized policy evaluator, which only works during training and is accessable to global information. At the same time, each agent is assigned with local policy for decentralized exccution. The role of the evaluator is to evaluate agents' local policies differentially from the global perspective.
A challenge in construction of centralized evaluator is multi-agent credit SaiignmentCChapg et al. 2004): in cooperative settings, joint actions typically generate only global rewards, making diffi- cult for each agent to deduce its own contribution to the team's 's success. Credit assignment requires differentiate evaluation for agents' local policies, but designing individual reward function for each agent is often complicated and lacks of generalization Grzes) rent policy based MARI. methods generally realize credit assignment by introducing differentiate value functions or advantage functions( (Foesstr al.) 2018 (Loee et al. (017). However, these value functions or advantage functions are estimated asynchronously but decentralized policies are updated synchronously, as shown in figure ((b), which results in natural estimation bias.
(007)(Mannion) et al.) (018). Cur-
In this paper, we propose a novel policy based MARL method called multi-agent policy optimiza- tion with approximatively synchronous advantage astimation(ASAE) In our work, we first define the counter-factual scenes, in which MA advantage estimation can converted to SA advantage estimation. For certain agent, each counter-factual scene is assigned with SA advantage. Then

---

Under review as a conference paper at ICLR 2021
Tia
Tna
Ti.
Tn.
Taa
Tna
op
cp
cp
cp
cp
cp
7
Tn.ttl
T
(a) usynchromous update
(b) synchronous updute & asynchronous estimation
(c) synchronous update & synchronous estimation
asynchronous estimation
Figure I: Comparison among three different manners of advantage estimation & update. Ra, repre- sents the policy of agent a at iteration i and there are n agents in total. Lines with arrow represent policy updates and ep denotes the update epoch. In single iteration, synchronous update takes only one epoch while asynchronous update takes epochs. In advantage estimation, policies need to be estimated jointly, and the dashed boxes contain joint polices used for advantage estimation in corresponding update. Particularly, synchronous estimation requires other agents' future polices.
the marginal advantage function defined the expectation of SA advantages on distribution of counter-factual scenes, and credit assignment is realized by constructing different scenes' distri- bution for different agents. Moreover, order to achieve synchronous advantage estimation, an approximation of other agents' joint future policy is introduced. To ensure the approximation is reliable, a restriction is applied to the original multi-agent policy optimization(MAPO) problem. The approximate optimization problem is simplified and broken down into multiple sub-probles sub-problems, which has a similar form to trust region policy optimization (TPOO) problem. And the sub-problems finally solved by proximal policy optimization(PPOO) method.
We have two contributions in this work: (1) A novel advantage estimation method called marginal advantage estimation, which realizes credit assignment for MARL is proposed. More importantly, this method provides channel for various SA advantage functions expanding to multi-agent system. (2) A simple yet effective method for approximatively synchronous advantage estimation is firstly proposed.
2 RELATED WORK
common challenge in cooperative multi-agent tasks is credit assignment. RL algorithms designed for single-agent tasks, ignore credit assignment and take other agents part of partial observable environment. Such algorithms perform poorly complex cooperative tasks which require high coordination(Lowe et al. (017). To deal with the challenge, some value based MARL methods estimate a local Q value for each agent, and the shared global Q value is then constructed through these local Q values. Value decomposition network( VDN) constructs the global Q value by simply adding all local Q values (Sgneher et al., 2018). And in QMIX algorithm(Rashe Rashid et al., 2018), the global Q value is obtained by mixing local Q values with neural network. In mean field multi-agent methods, local Q values are defined on agent pairs. The mapping from local Q values the global Q value is established by measuring the influence of each agent pair's joint action to the global return Yang et al. 2018).
Similarly, for policy based MARL methods, credit assignment is generally realized through differ- entiated evaluation with CTED structure. Some naive policy based methods estimate local Q values for individual agents with centralized critie et al. 2017). resulting in large variance. Some counter-factual multi-agent policy
other methods try to introduce advantage function in MARL. gradient(COM.. method(Foerster et al. (018) is inspired by the idea of difference reward (Wolprt] & Tumer 2002) and provides naive yet effective approach for differentiated advantage estimation in cooperative MARL. In COMA, a centralized critic is used to predict the joint Q value function Q= (s. u) of joint action under state And the advantage for agent is defined
(s, u) Q(s, u) Σ T ( (Q(s, (u ",""))
where T and π represent trajectory and policy respectively. a and - denote current agent and the set of other agents respectively. COMA introduces counter-factual baseline, which assumes that
2

---

Under review as a conference paper at ICLR 2021
other agents take fixed actions, shown in figure 1(b). COMA performs synchronous updates with asynchronous estimation, which leads to lagging and biased advantage estimation. In contrast, asynchronous estimation & asynchronous updating is more reliable yet more complicated. An ideal approach is synchronous estimation & synchronous updating. However, it requires prediction of other agents' future policies.
3 BACKGROUND
We consider most general setting of partially observable, full cooperative multi-agent tasks, which can be described as stochastic game defined by a tuple state of environment E S is unavailable to all agents. At each time step. agents identified by a E A (A = 11,2, ,,,,,, nn)) receive their local observations 2 E Z, and take actions u E Ú simultaneousll. The joint observation Z z" is acquired by the observation function O(s, x A + Z. The next state is determined by joint action u E U (U= U*) and the transition function P(s'|s, (s, u) S x U agents, so as the discounted return G. = Eitt 7'rete E [0, 1) is discount factor.
S. U, P.r. Z, O, n, >. The true
[0, 1]. The reward function r(s, u) x lK is shared by all
In policy based MARL with CTED architecture, each agent has local trajectory 7 consists of historical observation and action {(28. uτ), (f). ....,, And an independent policy n² (=("[7>) constructed for each agent their local trajectory. Action-state value function (T u) and state value function (s) are used to evaluate joint policy. The advantage function is (s, u)
Q (S For clarity, symbols in bold are used to denote the joint variable of group agents.
In single-agent policy optimization problems(Schulman et al. 2015a), the objective is to maximize the expected action state value function Ex, [x,]] Similarly, MAPO with CTDE structure, each agent optimize its local policy individually with estimated Q values from centralized critic. Under this circumstance, the overall objective
for agent a to n
max Fiso, ((TU)
8,
Where Q values be substituted by advantages reduce the variance.
APPROXIMATIVELY SYNCHRONOUS ADVANTAGE ESTIMATION IN MULTI-AGENT SYSTEM
In this section, we first introduce marginal advantage estimation which expands advantage functions of SARL to MARL as well to realize credit assignment. And then, we describe how to realize approximatively synchronous advantage estimation based on the marginal advantage function in MAPO problem.
4.1 MARGINAL ADVANTAGE ESTIMATION
In this subsection, we are going to solve the challenge of credit assignment through the proposed marginal advantage estimation. We first consider counter-factur way where advantages are esti- mated asynchronously but policies are updated synchronously, as shown figure (b)). In this case, counter-factual scene can be defined as: at certain state, for agent a, other agent always take fixed actions. In partially observable, full cooperative multi-agent settings, the counter-factual advantage of agent a's action tt under state derived based on the joint action's value(or joint Q value) function Q(s, u)
A u) = (s, (u,, ())
Q( - /f Q(, (u (1
From the view of agent the counter-facture advantage depends other agents' joint action u um which is a random variable and u ~ π a order to remove the dependency, the marginal Q value function of agent defined as
(* u²) Fa--Naa [Q(s, (u" " [))]
(4)
3

---

Under review as a conference paper at ICLR 2021
Notice that in CTED structure, policy I² (""(("") and π "="("=/7=~)) are independent. By replacing joint Q value function with marginal Q value function, the marginal advantage function is derived
/ Q" do (u
(s, u²) = (9(s,
Q18, u,, (udd="ddaaa (1=1/7=-)-
Q1s u. , a a) do "(u"( ""dd""""""" ")dd d (u" (*))
Q Q((,,u,, ,0o, Qlo,u, a) du (1 dx
us, du
(5)
Such replacement will not change the result of advantage estimation because the substitution of joint Q value its expectation. Form equation(5), for different agent, the value of marginal advantage is different, which realizes credit assignment. It can be easily proved that if counter- advantage (s, u) is an unbiased estimation of joint Q value ( u), then marginal advantage is also an unbiased estimation of marginal Q value(Appendix I).
In counter-factual scene, from the view of agent a, other agents and their fix joint actions u- can be regarded as part of the environment. Let (s, u-) = Setf and counter-factual advantage function can be written as
A u) =A (Setf,
=Q(sat; u²) f. Q(eatt "eeee,," u² dm (u
In counter-factual scenes, counter-factual advantage function is identical to advantage function in SARL, which means the counter-factual advantage in equation(S) can be replaced by any form of advantage function used in SARL. For example, considering using TD residual of = r(st. uf + ($(+2) - (s;) as an estimation of joint advantage A A"(s, u,), the marginal advantages could be written
(8t; us) Eu-anat
7 1
(st, u.) : Eu-ana-a [6,]]
The former is unbiased estimation, but has high variance. The latter is biased estimation for any V * V", but has much lower variance. These two methods can be combined for compromise between bias and variance(Schulman et al. 20155).
As agents' policies are independent, the expectation in equation(S) can be split into a (n - 1)llayer integration, which is complicated. For simplicity and efficiency, the Morle)Carlo(MC) sampling can be applied as a substitution.
A" uz) un)= A up dT x Σ A" (st,
(8)
Where is the number of other agents' joint action samples. The principle of one step process to calculate marginal advantage with TD residual is shown in figure 2. Firstly, based on the last true state 8t, m joint action samples are sampled. These samples are then reorganized. Take agent as example, action #1,t from S.1 is combined with other agents' action samples from S.2 to Sam respectively. As result, m reorganized new samples are acquired. Based on these new samples, one step simulations executed and counter-factual rewards and states are acquired, which are used to calculate the estimation of marginal advantage. At last, the next true state is selected form factual states.
Both methods in equation(7) use V value predictor and require interactive simulation. Agent needs to interact with environment to get extra samples. In this work, consider using centralized critic to predict joint Q values, and the marginal advantages can be directly calculated with these Q values, which avoids interactive simulation.
4

---

Under review as a conference paper at ICLR 2021
U1.t
U2.
Un,t
TeLL1
Sa
St-..1
reorgnized Wl
T
Saz
St-122
reorgnized U2
It+L.m
Sam!
S
sample
reorgnized
Un step
sample t+1
simulations
Figure 2: One step process of marginal advantage (S, Sa, (U1,)))ss estimation with TD residual. S, represents true state of time step Sam represents mith joint action sample and Un.t denotes the action of agent n in corresponding sample. Blue solid lines connect the reorganized joint action samples. Based on these samples, one step simulations are executed and S1+1.m- 7t+1, represent counter-factual state and reward acquired in simulation respectively. Finally, the next true state is selected from these counter-factual states.
4.2 APPROXIMATIVELY SYNCHRONOUS ADVANTAGE ESTIMATION
In marginal advantage estimation, actions are sampled from the agents' past policies. The estimation still asynchronous because it assumes the invariance of others' policies. However, synchronous advantage estimation requires the prediction of other agents' future action, as shown in figure I(c).
In marginal advantage estimation, problem of action prediction becomes policy prediction.
Direct prediction of others' future policies is very difficult. In iterative training, only others' policies of next iteration are needed. Assume others' joint policy of iteration n. " "0 "). Syn-
chronous marginal advantage is given by
A sggn (8, u²t) (== F,, ann, [A) u², u a)]
To calculate the synchronous marginal advantage, we first introduce approximation that us (s, The reliability of this approximation KL mf Tp < &chuulmn et al. (2015a). For simplicity, we use nh to represent л (u))). In marginal advantage estimation, have introduced Monte Carlo(MC) sampling and samples form others' joint policy ग. are needed. However, only polices before iteration i are available. So the second approximation is introduced as क, & म, Similarly, in order to ensure the approximation is reliable, a KL divergence restriction between ग, and π= is applied as KL [_],T]_]]]] u < 6. The objective of policy optimization problem with synchronous advantage estimation for agent is
ensured by a restriction
max Eaeenyyy
13 1,smm 1, (8,
T
max Euway "
A (s,
(10)
T&-1
subject to KL
[T ;
81
L
< 82

---

Under review as a conference paper at ICLR 2021
The first restriction involves other agents' polices, which requires joint optimization of all agents' policies. The integral objective multi-agent policy optimization with n agents
max
E
Af-((s.u)
subject to V KL (T [ [
<d
(1I)
UKL
a T <
It can be proved that KL " m-- Eo tighter form of the restriction KL mi ;
KL [=]:
II). For simplification,
can be written as
51 81, for in U
KL m111
<
(12)
By replacing the restriction equation(1] I) simplified:
KL (..
x-11
81 with the tighter form, the first restriction in
" -a UUIKL [ x < 8/3a
(13)
Notice that there are n 1 duplicate restrictions for each KL [T] m < 8', remove redundant duplicates and the first restrictions in equation( (1) finally equals
UKL [3 < 84
(14)
Set 8, (n 1)6 (n 1)62 and the two restrictions in equation(11) can be combined into KL
KL [T. m < 82.
The integral problem of MAPO in equation(11) consists of n individual policy optimization prob- lems with sub-restrictions. In CTED structure, policies of different agents are updated indepen- dently. For agent a, only the sub-restriction K (T. -ー- < 82 is effective. Thus, for further simplification, the integral objective can be split into sub-objectives:
for in 1,2, 1,2
max Eu-w- (s,
(15)
subject to KL |
52
The sub-objectives above are similar the objective in trust region policy optimization prob- lemSSchulman et al. (2015a). It's proved that the KL divergence restriction can be effectively re- placed by a clip operation (SerutionnSchulman Schulman al., 2017). The sub-objectives of MAPO with ASAE finally acquired
for in 1,2, ... n:
max R
Σ
m
A A (8. (
π dipp
6, 1 +6)
(16)
EXPERIMENTS
In this section, COMA advantage counter-factual advantage to estimate the approxima- tively synchronous advantage. And we compare our method with baseline algorithms on the bench- mark StarCraft multi-agent Challenge(SMAC).

---

Under review as a conference paper at ICLR 2021
5.1 EXPERIMENT SETTINGS
StarCraft II is a Real Time Strategy(RTS) game. And SMAC a popular benchmark for cooperative MARL algorithms which provides an interface for RL agents to interact with StarCraft II, getting rewards, observations and sending actions. In our experiments, we consider different types of tasks of battle games involving both mixed and single type of agents. Specifically, our experiments are carried out on 8 tasks of different difficulty level, as shown in table 1. In, homogeneous tasks, agents are of the same type. symmetric battle scenarios, each army are composed of the same units, agents need to learn to focus fire without overkill. The asymmetric scenarios are more challenging because the enemy army always outnumbers allied army by one or more units. In micro-trick tasks, agents' are required higher-level of cooperation and specific micromanagement trick to defeat the enemy, which is the most difficult.
Table 1: Information of SMAC tasks in experiments
name
Ally Units
Enemy Units
Type
3m
3 Marines
3 Marines
homogenecosssksymmeriii
8m
8 Marines
8 Marines
homoggneouskksymmerric
3 Stalkers
3 Stalkers
3s5z
beterogeneoussksymmerrii
5 Zealots
Zealots
Colossi
Colossi
lc3s5z
3 Stalkers
3 Stalkers
heterogeneouukk-ymmetri
5 Zealots
Zealots
2m vs 1z
2 Marines
1 Zealot
micro-trick
10m_vs_1 1m
10 Marines
11 Marines
honnogeneouskaayymmerri
2c_vs_64zg
Colossi
64 Zerglings
micro-trick
1 Medivac
1 Medivac
MMM2
Marauders
3 Marauders
heterogennouus@ayymmeerii
7 Marines
8 Marines
In our experiment settings, only ally units are considered to be MARL agents. The environment is set to be partially observable and each agent has a sight range, which is set to be a circular area around the agent. Only specific attributes units in sight range are observable. These attributes include distance, relative x coordinate, relative y coordinate, health and shield. Agents can also observe the terrain features surrounding them. And in addition, the last actions of ally units are accessable for all agents. The global state including information about all units on the map and it's only available in centralized training. The action space is discrete and consists of moving directions, h attack actions where h is the number of the enemy units in map, stop and none-operation. The SMAC environment provides both sparse reward and shaped reward settings, we only consider the shaped reward situation where reward are much denser.
In ASAE, we use COMA advantage as counter-factual advantage to calculate the approximatively synchronous advantage. We adopted the CTED architecture and the structure of actors and critic in our methods is the same to other policy based MARL methods, such as COMA. The centralized critic is used to predict the joint Q value function of reorganized samples. The state value is calcu- lated with the average Q values of these reorganized samples, which avoids interactive simulations. The number of sample is set be 50 and the clip range is 0.1.
We compare our method with baseline algorithms including IQL 1993). VDN, QMIX and COMA. In these baselines, only COMA is policy based and most similar our method. For all algorithms, good samples are added to replay buffer in initializing stage for early policy training. And all algorithms are trained for 3 million time-steps. The training batch-size set be 32 and discount factor is 0.99. The learning rates for critic and actors are both 0.0005.
5.2 EXPERIMENT RESULTS
The test wining rates during training are shown in figure 3. Compared to other baseline algorithms, algorithms converges fastest and perform best in most of the tasks. Particularly, compared to
7

---

Under review as a conference paper at ICLR 2021
COMA
QMIX
VON
JOL
Tct65o
1.0
0.3
0.4
0.2
0.0
0.5M
1M
1.5M 2M
2.5M. 3M
0.5M IM 1.5M 2M 2,53 3M
0.550 IM 1.5M 2M
2,50 SM
0.5M LM
1.5M
2M 2.5M SM
2m vo_
10m vo. 17m
De ve 64rg
MMM2
1.0
0.6
0.4
0.5M 1M 1.5M 2M 2.5 3M
0.5 IM 1.5 2M 2.5M
0.5M
1.M 2M 2,5 5M
0.5M IM 1.M 2M 2.5M
Steps
Figure 3: Test wining rate vs. training steps of various methods on SMAC benchmarks
the other policy based MARL algorithm COMA, algorithm shows considerable improvement in tasks of According to the results, homogeneous symmetric tasks such as 3m and 8m, algorithm converges after million steps of training and reach approximate 100 percent test asymmetric tasks(10m (11mm100mmmmmm) 11mm and simple heterogeneous &
wining rate. For homogeneous symmetric tasks such as 3s52 and 1c3s52, algorithms converges slower, and the wining rate fluctuates slightly during training. However, our algorithm also reaches approximate 100 percent test win rate after 3 million steps of training. For different micro-trick tasks, the performance and convergence speed of our algorithm varies greatly. While in harder tasks as 10m_es_1 Im, M M M2 and 2m_us_lz, COMA algorithm shows no performance. The wining rate after training tested and shown in table 2. Our algorithm also shows the best performance in most of the tasks.
interesting phenomenon is that, the wining rate curve shows less fluctuation tasks with ho- mogeneous ally units, such 3m. 2m_rs_642g, 2m_es_12, etc. It's inferred that, in such tasks, different agents are functionally replaceable, which provides higher fault tolerance rate for indi- vidual agent's s action. As a result, the performance fluctuation of certain agent during training has less influence on group's 's joint policy.
In order to analyse the cooperative strategies learned by agents, we render the battle process between default AI and agents trained by our algorithms. Some key frames are showed in figure Agents in red are ally units. In The first task 2s32, cooperative agents learn to focus fire after training.
Table 2: Test wining rates
Algorithms QMIX
ENV
ours
COMA
IQL
VDN
3m
1.0
0.81
1.0
1.0
1.0
8m
0.97
0.97
1.0
0.91
1.0
385z
0.95
0.2
0.84
0
0.72
1c3s5z
1.0
0.83
0.97
0.72
0.94
2m_vs_1z
1.0
0
1.0
1.0
1.0
10m_vs_
0.98
0
0.97
0.31
0.97
2c vs 64zg
0.97
0.25
0.88
0.78
0.91
MMM2
0.78
0
0.72
0.03
0
8

---

Under review as a conference paper at ICLR 2021
target
target
Focus
(2a3x)
Adjust Formation (MMM2)
under attack
away
Utilize Terrian
move accros obstacle
Features
terrain obstacle
(2m, vs. (4kg)
Figure 4: Display of learned cooperative strategies.
While the enemy agents tend to attack the units nearby. After few rounds of crossfire, enemy group quickly lose the first unit. the second task MMM. M2, besides focus fire, cooperative agents also learn to adjust formation and use skill to avoid being destroyed. Particularly, in micro-trick tasks, cooperative agents learn to take advantage map features and units' differences. As shown in the third sub- sob-graph, in task 2m_ only ally units able to move across terrain. Take advantage of this, ally units can attack enemy and move across the terrain when enemy approaching thus avoid being attacked.
6 CONCLUSION
In this work, we propose novel method of advantage estimation which address credit assignment and synchronous estimation in cooperative multi-agent systems. By introducing marginal Q value function, we derived the marginal advantage function and it's relationship with counter-factual ad- vantage function. Then, we define the counter-factual scene where counter-factual advantage can be replaced by single agent advantage. So we acquire a method for single agent advantage function expanding to multi-agent systems. Based on marginal advantage, we propose the approximatively synchronous advantage estimation. Through policy approximation and constrain simplification, the problem of MAPO decomposed into multiple sub- problems of SA policy optimization and finally solved by PPO method. Our algorithms evaluated on battle tasks of SMAC benchmark. Com- pared to baselines, our algorithms perform best both training and testing. Moreover, visualized battle processes show that agents acquire heuristic cooperation strategies after training.
For future work, we are interested in applying our algorithm to cooperative robot tasks. For example, two arms' cooperation tasks where two arms are treated as individual agents and need cooperate to accomplish complicate work. Moreover, because our method provides a channel for SA advan- tage function expanding to multi-agent system, it's also interesting to investigate the application of various policy based RL algorithms on multi-agent scenarios.
REFERENCES
Yu-Han Chang, Tracey Ho, and Leslie Kaelbling. All learning is local: Multi-agent learning in global reward games. In Advances in neural information processing systems, pp. 807-814, 2004.
Tianshu Chu, Sandeep Chinchali, and Sachin Katti. Multi-agent reinforcement learning for net-
worked system control. In International Conference on Learning Representations, 2019.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon White- son. Counterfactual multi-agent policy gradients. In Thirty-second AAAI conference on artificial intelligence, 2018.

---

Under review as a conference paper at ICLR 2021
Yasuhiro Fujita and Shin-ichi Maeda. Clipped action policy gradient. In International Conference on Machine Learning, pp. 1597-1606, 2018.
Evan Greensmith, Peter L Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. Journal of Machine Learning Research, 1(Nov):1471-1530 2004.
Marek Grzes. Reward shaping in episodic reinforcement learning. 2017.
Max Jaderberg, Volodymyr Mnih, Wojciech M. Czarnecki, Schaul Tom, Leibo Joel 7.,, Silver David, and Kavukeuoglu Koray. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611.05397, 2016.
Emilio Jorge, Mikael Kägebäck, Fredrik D Johansson, and Emil Gustavsson. Learning to play guess who? and inventing grounded language as a consequence. arXiv preprint 1611v:1611.0322 2016.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver. and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint 1rXiv:1509.0220 2015.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed cooperative-compeiine environments. In Advances in neural infor- mation processing systems, pp. 6379-6390, 2017.
Patrick Mannion, Sam Devlin, Jim Duggan, and Enda Howley. Reward shaping for knowledge- based multi-objective multi-agent reinforcement learning. The Knowledge Engineering Review, 33, 2018.
Volodymyr Mnih, Kavukcuoglu Koray, Silver David, Graves Alex, Antonoglou Ioannis, Wierstra Daan, and Riedmiller Martin. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602. 2013.
Due T. Nguyen, Kumar Akshat, and Hoong Chuin L. Credit assignment for collective multiagent rl with global rewards. volume 1806.05635, pp. 8102-8113, 2018.
Junhyuk Oh, Guo Yijie, Singh Satinder, and Lee Honglak. Self-imitation learning. volume 1806.05635, pp. 1878-3887 2018.
Frans A Oliehoek and Nikos Vlassis. Q-value functions for decentralized pomdps. In Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, pp. 1-8, 2007.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv: /803. 1485, 2018
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference machine learning, pp. 1889-1897, 2015a.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: 02438, 2015b.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojciech Marian Czarnecki, Vinícius Flores Zam- baldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In AAMAS, 2018.
pp.
Ming Tan. Multi Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
10

---

Under review as a conference paper at ICLR 2021
Pawel Wawrzyński. Real-time reinforcement learning by sequential actor-critics and experience replay. Neural Networks, 22(10):1484-14) 1494, 2009.
David H Wolpert and Kagan Tumer. Optimal payoff functions for members of collectives. In Modeling complexity in economic and social systems, pp. 355-369, World Scientific, 2002.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning, In International Conference on Machine Learning, pp- 5571-5580, 2018.
A APPENDIX
Assume that joint advantage (8, u) is unbiased estimation of joint Q value function Q(s, u).
Then
(s, u) Q(s, b, where: Vob, =0
(17)
Then
A u) = E (s u)]
F (Q( u) bx] E (0(s, u)] Eyy [bc]
(18)
Fry [Q(s, is exact the marginal Q value function and V F [ba] F [Vbb.] =
B
APPENDIX II
Consider agents, whose policies of episode i are represented by nt and n? respectively.
KL n
a 1]
log T, π 7
du
22
1 1 7
log
Ti
+ log
du
2
TT
π
(19)
T
n. log
du
log
du
=KL
[ T + KL
The relation can be expanded to joint distribution of other agents' policies
KL प.
II log
du
(20)
0 0 KL
1
11


Reviews:
[{"review_id": "XizmkzrM0Yy", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of claims and contributions:\nThe paper introduces two improvement for the centralised-learning and decentralised-execution architecture for multiagent reinforcement learning algorithms: i) a per-agent marginal advantage estimator that marginalises other agents' actions out; ii) motivates a trust-region method. The authors claim the former alleviates the credit-assignment problem, while the later reduces bias in the approximation of the advantage function due to assuming other agents' policies stationary. \nNumerical experiments show that the proposed algorithm match or outperforms some state of the art baselines.\n\nStrong points:\nThe marginal advantage estimator is derived in two different ways---first and last line of (5)---, and both make intuitive sense. This estimator seems a natural extension of the counter-factual advantage estimator due to Foerster et al. (2018). \n\nThe connection with trust-region methods to reduce bias is also interesting, I personally tend to think on trust-region constraints as a method to reduce variance in the parameter update (due to stochastic gradient), while here it is motivated to reduce bias. It is also practical, since it can be easily implemented by using PPO for every agent.\n\nSimulation results show that the proposed improvements perform well in practice.\n\nWeak points:\nThe writing requires much improvement in order to be publishable. Notation is unclear if not loose and sometimes incomplete (e.g,, indexes in summations and unions are difficult to follow, policy parameter is never introduced, exponent instead of Cartesian product on the observation and action sets wasn't obvious...) There are multiple typos (mainly in text but also some in maths). The draft must be proof-read for English style and grammar issues. This is the main reason for my rejection. \n\nMany experimental details are missing hindering reproducibility.\n\nThe draft is 9 pages long. But the paper format could be much improved such that it fits in 8 pages, so I haven't considered this a deal breaker. \n\nQuestions:\n1. Why in the centralised-learning decentralised-execution are the agents' policies independent of each other?\n2. The concept of the counter-factual scene is not clear. Are the authors assuming the agents behave stationarily? Hence, the trust-region constraint bounds the relaxation on this assumption?\n3. First line in Sec. 5 says \"we use COMA advantage as counter-factual advantage to estimate the approximately synchronous advantage.\" What does it mean? Don't the authors use the marginal advantage?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KnW5S5EUtr2", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This works follows the footsteps of other centralized value function approaches for multi-agent learning, building directly on the counterfactual value function proposed in COMA. \n\nThe main idea is to sample additional joint actions to variance-reduce the advantage estimate for each of the agents at each time step.\nThe paper also introduces a KL penalty that is supposed to ensure that the policies are updated slowly, making the advantage estimate more accurate. \n\nA few comments:\n1) \", we consider using centralized critic to predict joint Q values, and the marginal advantages can be directly calculated with these Q values, which avoids interactive simulation.\". This directly contradicts Figure 2, where it is mentioned that \"one step simulations are executed\" for each of the samples. This point is relevant since extra simulation steps would drastically change the sample requirements for the method. Furthermore, this assumes that there is a simulator that can be set to arbitrary state transitions, which is different from the standard RL assumption. \n2) \"which means the counter-factual advantage in equation(5) can be replaced by any form of advantage function used in SARL.\". This is generally true. How to estimate the advantage is orthogonal to single agent vs multi-agent learning. In particular, the COMA critic (Q-function) could easily be replaced with a GAE or similar. On a related note, while using a critic that depends only on the Q(s,u) (ie. the central state and joint action) is common practice in this line of work, it is not generally appropriate. Clearly, in Dec-POMDPs, the future actions will depend on the action-observation histories (AOHs), $\\tau$ of all the agents. As a consequence, in general the critic should condition on these AOHs.\n3) \"And in addition, the last actions of ally units are accessable for all agents.\" This is different form the standard SMAC setting, where only the last actions of the *visible* agents are observable by each of the agents. Please clarify this rationale.\n4) Please specify what advantage estimation is being used in this paper. My understanding is that the paper uses the joint-Q function similar to the COMA paper. Is this accurate? \n5) Overall the results look competitive, but are currently not very informative due to missing ablations. It's impossible to tell if the PPO-like KL penalty or the multi-sample variance reduction are responsible for the improved performance. \n6) The training curves look very odd. In particular, they look unstable but have very narrow errorbars, indicating that many of the runs drop at the same time. This suggests that the experiments may have accidentally reused the same random seed.  \n7) MMM2 is the only \"superhard\" scenario used from SMAC. Did the method fail on the other ones? \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "C4EgCKLnA_", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThe authors address the multi-agent learning issue of agents needing to infer other agents' policies to estimate their expected reward correctly. This can be done synchronously (agents see other policy models), or asynchronously (agents cannot see other agents' policies) -- if I understand the authors' nomenclature/illustrations correctly.\n\nCertainly improving the stability of multi-agent learning with just first-order methods and without the need to infer other agent policies is an important and interesting problem. However, I found the manuscript hard to follow and experimental proof unconvincing.\n\n- Clarify issues: It seems that the authors end up with a multi-agent variation of TRPO in Eq 16. They seem to basically assume that agent policies are independent, so they can rewrite the advantage A(s, u^a) of agent a as marginalization of A(s, u^joint) over the actions/policies of the other agents. From this, they then apply TRPO to each agent individually, using the most conservative trust region radius among the N agents. I'm not convinced this is that novel.\n- The dashed lines in Figure 1 make the relationships between agents a bit hard to read. \n- There are minor English grammar and syntax issues throughout, e.g., ' each agent has a local trajectory τa consists of historical observation and action'. \n- The authors should visualize and better explain why in certain situations their algorithm seems to do better or not (e.g., 2c_cs64zg vs 2m_vs_1z: what's the difference? The authors only mention that 2m_vs_1z is \"hard\").\n- The results in Figure 3 seem to use only 1 seed? The authors should repeat experiments with more (5 or more) random seeds to show how significant the gains are. \n\nI encourage the authors to add more experimental proofs and make the presentation clearer.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7Kp8Kg_Fm8v", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThe paper deals with the problem of credit assignment and synchronous estimation in cooperative multi-agent reinforcement learning problems. The authors introduce marginal advantage functions and use them for the estimation of the counterfactual advantage function. These functions permit to decompose the Multi-Agent Policy Optimization Problem in Single Agent Policy Optimization subproblems, which are solved using TRPO.\n\n\nStrengths\n\nThe paper proposes elegant derivations to deal with the multi-agent policy optimization problem.  The marginal advantage function gives the possibility to solve the credit assignment problem. Instead, the synchronous advantage estimation assumes that the current policy is close to the previous one. To rely on this approximation, the authors propose to add KL constraints to the optimization problem, which lead to derivations similar to TRPO. \nThe approach is interesting and the experimental results confirm that the method performs better than COMA.\n\n\n\nWeakness\n\nThe paper is only experimental and gives no theoretical guarantees. \nIn the results of the experiments, it seems that QMIX has excellent performance, sometimes better than the proposed method, but in the Experimental Results, there are no comments on this fact. Could you give some insight into why QMIX, in some cases, performs better than the proposed method?\nIs it possible to perform an ablation study on the clipping parameter? It seems the most relevant hyperparameter of the proposed method since it regularized the assumption of using the past policy as the current one.\n\n\nMinor:\n- figure 6 reorgnized $\\rightarrow$ reorganized\n- missing space in second line under equation 9\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers expressed interest in this promising approach, but raised questions that were not addressed by the authors during the discussion period. As concerns raised included insufficient repeats of empirical experiments to draw conclusions and the paper appearing to be in an early draft format, we cannot support acceptance for publication at this time. I strongly encourage the authors to act on the feedback given to improve the paper for a future submission.  
Decision: Reject