Year: 2020

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.

heading: 1 INTRODUCTION
text: Reinforcement learning(RL) algorithms have shown amazing performance on many singleagent(SA) environment tasks (Mnih et al., 2013)(Jaderberg et al., 2016)(Oh 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(Nguyen et al., 2018) and network control(Chu et al., 2019).
In cooperative multi-agent tasks, each agent is 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(CTDE) is proposed(Oliehoek & Vlassis, 2007)(Jorge et al., 2016). 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 a local policy for decentralized execution. 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 assignment(Chang et al., 2004): in cooperative settings, joint actions typically generate only global rewards, making it difficult for each agent to deduce its own contribution to the team’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, 2017)(Mannion et al., 2018). Current policy based MARL methods generally realize credit assignment by introducing differentiate value functions or advantage functions(Foerster et al., 2018)(Lowe et al., 2017). However, these value functions or advantage functions are estimated asynchronously but decentralized policies are updated synchronously, as shown in figure 1(b), which results in natural estimation bias.
In this paper, we propose a novel policy based MARL method called multi-agent policy optimization with approximatively synchronous advantage estimation(ASAE). In our work, we first define the counter-factual scenes, in which MA advantage estimation can be converted to SA advantage estimation. For certain agent, each counter-factual scene is assigned with a SA advantage. Then
the marginal advantage function is defined as the expectation of SA advantages on distribution of counter-factual scenes, and credit assignment is realized by constructing different scenes’ distribution for different agents. Moreover, in 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-problems, which has a similar form to trust region policy optimization(TRPO) problem. And the sub-problems are finally solved by proximal policy optimization(PPO) 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 a 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.

heading: 2 RELATED WORK
text: A common challenge in cooperative multi-agent tasks is credit assignment. RL algorithms designed for single-agent tasks, ignore credit assignment and take other agents as part of partial observable environment. Such algorithms perform poorly in complex cooperative tasks which require high coordination(Lowe et al., 2017). 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 together(Sunehag et al., 2018). And in QMIX algorithm(Rashid et al., 2018), the global Q value is obtained by mixing local Q values with a neural network. In mean field multi-agent methods, local Q values are defined on agent pairs. The mapping from local Q values to 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 differentiated evaluation with CTED structure. Some naive policy based methods estimate local Q values for individual agents with a centralized critic(Lowe et al., 2017), resulting in large variance. Some other methods try to introduce advantage function in MARL. Counter-factual multi-agent policy gradient(COMA) method(Foerster et al., 2018) is inspired by the idea of difference reward(Wolpert & Tumer, 2002) and provides a 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 u under state s. And the advantage for agent a is defined as
Aa(s,u) = Q(s,u)− ∑ u′a πa(u′a|τa)Q(s, (u−a, u′a)) (1)
where τ and π represent trajectory and policy respectively. a and -a denote current agent and the set of other agents respectively. COMA introduces a counter-factual baseline, which assumes that
other agents take fixed actions, as 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.

heading: 3 BACKGROUND
text: We consider a most general setting of partially observable, full cooperative multi-agent tasks, which can be described as a stochastic game defined by a tuple G =< S,U, P, r, Z,O, n, γ >. The true state of environment s ∈ S is unavailable to all agents. At each time step, n agents identified by a ∈ A (A = {1, 2, · · · , n}) receive their local observations za ∈ Z, and take actions ua ∈ U simultaneously. The joint observation Z = Zn is acquired by the observation function O(s, a) : S × A → Z. The next state is determined by joint action u ∈ U (U = Un) and the transition function P (s′|s,u) : S×U×S → [0, 1]. The reward function r(s,u) : S×U→ R is shared by all agents, so as the discounted return Gt = ∑∞ t+i γ
trt+i. γ ∈ [0, 1) is a discount factor. In policy based MARL with CTED architecture, each agent has a local trajectory τa consists of historical observation and action {(za0 , ua0), (ua1 , za1 ), · · · }. And an independent policy πa(ua|τa) is constructed for each agent on their local trajectory. Action-state value function Qπ(s,u) and state value function V π(s) are used to evaluate joint policy. The advantage function is Aπ(s,u) = Qπ(s,u)−V π(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 functionEπθ [Qπθ ]. Similarly, for MAPO with CTDE structure, each agent optimize its local policy individually with estimated Q values from centralized critic. Under this circumstance, the overall objective is
for agent a = 1 to n :
max θa E(πθa ,π−a)
[ Qa(πθa ,π−a) ] (2) Where Q values can be substituted by advantages to reduce the variance.

heading: 4 APPROXIMATIVELY SYNCHRONOUS ADVANTAGE ESTIMATION IN MULTI-AGENT SYSTEM
text: 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.

heading: 4.1 MARGINAL ADVANTAGE ESTIMATION
text: In this subsection, we are going to solve the challenge of credit assignment through the proposed marginal advantage estimation. We first consider an counter-factual way where advantages are estimated asynchronously but policies are updated synchronously, as shown in figure 1(b). In this case, a 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 ua under state s is derived based on the joint action’s value(or joint Q value) function Q(s,u)
Aa(s,u) = Aa(s, (ua, u−a)) = Q(s,u)− ∫ ua Q(s, u−a, ua) dπa(ua|τa)
(3)
From the view of agent a, the counter-factual advantage depends on other agents’ joint action u−a, which is a random variable and u−a ∼ π−a. In order to remove the dependency, the marginal Q value function of agent a is defined as
Qa(s, ua) = Eu−a∼π−a [ Q(s, (ua, u−a)) ] (4)
Notice that in CTED structure, policy πa(ua|τa) and π−a(u−a|τ−a) are independent. By replacing joint Q value function with marginal Q value function, the marginal advantage function is derived
Aa(s, ua) = Qa(s, ua)− ∫ ua Qa(s, ua) dπa(ua|τa)
= ∫ u−a Q(s, ua, u−a)dπ−a(u−a|τ−a)− ∫ ua ∫ u−a Q(s, ua, u−a) dπ−a(u−a|τ−a)dπa(ua|τa)
= ∫ u−a [ Q(s, ua, u−a)− ∫ ua Q(s, ua, u−a) dπa(ua|τa) ] dπ−a(u−a|τ−a)
= ∫ u−a
Aa(s,u) dπ−a(u−a|τ−a) (5)
Such replacement will not change the result of advantage estimation because the substitution of joint Q value is 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-factual advantage Aa(s,u) is an unbiased estimation of joint Q value Q(s,u), then marginal advantage is also an unbiased estimation of marginal Q value(Appendix I).
In a counter-factual scene, from the view of agent a, other agents and their fix joint actions u−a can be regarded as part of the environment. Let (s,u−a) = sctf and counter-factual advantage function can be written as
Aa(s,u) =Aa(sctf , ua)
=Q(sctf , u a)− ∫ ua Q(sctf , u a) dπa(ua|τa) (6)
In counter-factual scenes, counter-factual advantage function is identical to advantage function in SARL, which means the counter-factual advantage in equation(5) can be replaced by any form of advantage function used in SARL. For example, considering using TD residual δat = r(st, u a t ) + γV (st+1)−V (st) as an estimation of joint advantage Aa(st,ut), the marginal advantages could be written as
Aa(st, ut) : = Eu−a∼π−a [ ∞∑ l=0 γlδat+l ] Aa(st, ut) : = Eu−a∼π−a [δ a t ]
(7)
The former is unbiased estimation, but has high variance. The latter is biased estimation for any V 6= V π , but has much lower variance. These two methods can be combined for compromise between bias and variance(Schulman et al., 2015b).
As agents’ policies are independent, the expectation in equation(5) can be split into a (n− 1)-layer integration, which is complicated. For simplicity and efficiency, the Monte-Carlo(MC) sampling can be applied as a substitution.
Aa(st, ut) = ∫ u−a Aa(st,ut)dπ−a ≈ 1 m m∑ u−a Aa(st,ut) (8)
Where m 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 st, m joint action samples are sampled. These samples are then reorganized. Take agent 1 as example, action u1,t from Sa1 is combined with other agents’ action samples from Sa2 to Sam respectively. As a result, m reorganized new samples are acquired. Based on these new samples, one step simulations are executed and m 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 counter-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, we consider using centralized critic to predict jointQ values, and the marginal advantages can be directly calculated with theseQ values, which avoids interactive simulation.

heading: 4.2 APPROXIMATIVELY SYNCHRONOUS ADVANTAGE ESTIMATION
text: In marginal advantage estimation, actions are sampled from the agents’ past policies. The estimation is 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 1(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 i is π−ai (u
−a|τ−a). Synchronous marginal advantage is given by
Aai,syn(s, u a) = Eu−a∼π−ai
[ Aai (s, u a, u−a) ]
(9)
To calculate the synchronous marginal advantage, we first introduce an approximation that Aai (s,u) ≈ Aai−1(s,u). The reliability of this approximation is ensured by a restriction KL [ πai , π a i−1 ] < δSchulman et al. (2015a). For simplicity, we use πa to represent πa(ua|τ). In marginal advantage estimation, we have introduced Monte Carlo(MC) sampling and samples form others’ joint policy π−ai are needed. However, only polices before iteration i are available. So the second approximation is introduced as π−ai−1 ≈ π −a i . Similarly, in order to ensure the approximation is reliable, a KL divergence restriction between π−ai and π −a i−1 is applied asKL [ πai , π a i−1 ] < δ. The objective of policy optimization problem with synchronous advantage estimation for agent a is
max πai Eua∼πai−1
[ Aai−1,syn(s, u a) · π a i
πai−1 ] = max
πai Eu∼πai−1
[ Aai−1(s,u) ·
πai πai−1 ] subject to : KL [ π−ai , π −a i−1 ] < δ1
KL [ πai , π a i−1 ] < δ2
(10)
The first restriction involves other agents’ polices, which requires joint optimization of all agents’ policies. The integral objective of multi-agent policy optimization with n agents is
max πai n∑ a Eu∼πi−1 [ Aai−1(s,u) · πai πai−1 ]
subject to : n⋃ a KL [ π−ai , π −a i−1 ] < δ1
n⋃ a KL [ πai , π a i−1 ] < δ2
(11)
It can be proved that KL [ π−ai , π −a i−1 ] < ∑−a o KL [ πoi , π o i−1 ] (Appendix II). For simplification, a
tighter form of the restriction KL [ π−ai , π −a i−1 ] < δ1 can be written as
KL [ πoi , π o i−1 ] <
δ1 n− 1 = δ′1, for o in
−a⋃ (12)
By replacing the restriction KL [ π−ai , π −a i−1 ] < δ1 with the tighter form, the first restriction in equation(11) is simplified: n⋃ a −a⋃ o {KL [ πoi , π o i−1 ] < δ′1}a (13)
Notice that there are n − 1 duplicate restrictions for each KL [ πai , π a i−1 ] < δ′, remove redundant duplicates and the first restrictions in equation(11) finally equals to n⋃ a KL [ πai , π a i−1 ] < δ′1 (14) Set δ1 = (n − 1)δ′1 = (n − 1)δ2 and the two restrictions in equation(11) can be combined into⋃n a KL [ πai , π a i−1 ] < δ2.
The integral problem of MAPO in equation(11) consists of n individual policy optimization problems with n sub-restrictions. In CTED structure, policies of different agents are updated independently. For agent a, only the sub-restriction KL [ πai , π a i−1 ] < δ2 is effective. Thus, for further simplification, the integral objective can be split into n sub-objectives:
for a in 1, 2, · · · , n :
max πai Eu∼πi−1
[ Aai−1(s,u) ·
πai πai−1 ] subject to : KL [ πai , π a i−1 ] < δ2
(15)
The sub-objectives above are similar to the objective in trust region policy optimization problemSchulman et al. (2015a). It’s proved that the KL divergence restriction can be effectively replaced by a clip operation(Schulman et al., 2017). The sub-objectives of MAPO with ASAE is finally acquired
for a in 1, 2, · · · , n :
max πai m∑ 1 [ Aai−1(s,u) · clip( πai πai−1 , 1− , 1 + ) ]
(16)

heading: 5 EXPERIMENTS
text: In this section, we use COMA advantage as counter-factual advantage to estimate the approximatively synchronous advantage. And we compare our method with baseline algorithms on the benchmark StarCraft multi-agent challenge(SMAC).

heading: 5.1 EXPERIMENT SETTINGS
text: StarCraft II is a Real Time Strategy(RTS) game. And SMAC is 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. In 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 a higher-level of cooperation and a specific micromanagement trick to defeat the enemy, which is the most difficult.
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 of 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 4 moving directions, k attack actions where k 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 calculated with the average Q values of these reorganized samples, which avoids interactive simulations. The number of sample m is set to be 50 and the clip range is 0.1.
We compare our method with baseline algorithms including IQL(Tan, 1993), VDN, QMIX and COMA. In these baselines, only COMA is policy based and most similar to 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 is set to be 32 and discount factor is 0.99. The learning rates for critic and actors are both 0.0005.

heading: 5.2 EXPERIMENT RESULTS
text: The test wining rates during training are shown in figure 3. Compared to other baseline algorithms, our algorithms converges fastest and perform best in most of the tasks. Particularly, compared to
the other policy based MARL algorithm COMA, our algorithm shows considerable improvement in 7 tasks of 8. According to the results, in homogeneous & symmetric tasks such as 3m and 8m, our algorithm converges after 1 million steps of training and reach approximate 100 percent test wining rate. For homogeneous & asymmetric tasks(10m vs 11m) and simple heterogeneous & symmetric tasks such as 3s5z and 1c3s5z, our 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 vs 11m, MMM2 and 2m vs 1z, COMA algorithm shows no performance. The wining rate after training is tested and shown in table 2. Our algorithm also shows the best performance in most of the tasks.
An interesting phenomenon is that, the wining rate curve shows less fluctuation in tasks with homogeneous ally units, such as 3m, 2m vs 64zg, 2m vs 1z, etc. It’s inferred that, in such tasks, different agents are functionally replaceable, which provides a higher fault tolerance rate for individual agent’s action. As a result, the performance fluctuation of certain agent during training has less influence on group’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 4. Agents in red are ally units. In The first task 2s3z, cooperative agents learn to focus fire after training.
While the enemy agents tend to attack the units nearby. After few rounds of crossfire, enemy group quickly lose the first unit. In the second task MMM2, 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 of map features and units’ differences. As shown in the third sub-graph, in task 2m vs 64zg, only ally units are 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.

heading: 6 CONCLUSION
text: In this work, we propose a 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 advantage 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 is decomposed into multiple sub-problems of SA policy optimization and finally solved by PPO method. Our algorithms are evaluated on battle tasks of SMAC benchmark. Compared to baselines, our algorithms perform best in both training and testing. Moreover, visualized battle processes show that our 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 to cooperate to accomplish complicate work. Moreover, because our method provides a channel for SA advantage function expanding to multi-agent system, it’s also interesting to investigate the application of various policy based RL algorithms on multi-agent scenarios.

heading: A APPENDIX I
text: Assume that joint advantage Aa(s,u) is a unbiased estimation of joint Q value function Q(s,u). Then
Aa(s,u) = Q(s,u)− bs where : ∇θbs ≡ 0
(17)
Then Aa(s, u) = E−aπ [A
a(s,u)] = E−aπ [Q(s,u)− bs] = E−aπ [Q(s,u)]− E−aπ [bs]
(18)
E−aπ [Q(s,u)] is exact the marginal Q value function and∇θE−aπ [bs] = E−aπ [∇θbs] ≡ 0

heading: B APPENDIX II
text: Consider two agents, whose policies of episode i are represented by π1i and π 2 i respectively.
KL [ π1i π 2 i , π 1 i−1π 2 i−1 ] = ∫ π1i π 2 i log π1i π 2 i
π1i−1π 2 i−1
du
= ∫ π1i π 2 i ( log
π1i π1i−1 + log π2i π2i−1
) du
< ∫ π1i log
π1i π1i−1 du+
∫ π2i log
π2i π2i−1 du
=KL [ π1i , π 1 i−1 ] +KL [ π2i , π 2 i−1 ]
(19)
The relation can be expanded to joint distribution of other agents’ policies
KL [ π−ai , π −a i−1 ] = ∫ −a∏ o πoi log ∏−a o π o i∏−a o π o i−1 du
< −a∑ o KL [ πoi , π o i−1 ] (20)

Review summaries:
The 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.