Advantage Constrained Proximal Policy Optimization in Multi-Agent Reinforcement Learning
Authors: Weifan Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: Multi agent
reinforcement learning
neural network
deep learning
trust region.

Abstract: We explore the value-based method and policy gradient combination in multi-agent reinforcement learning (MARL). In value-based MARL, {\itshape{Individual-Global-Max}} (IGM) principle plays an important role, which maintains the consistency between joint and local action values. At the same time, IGM is difficult to guarantee in multi-agent policy gradient methods due to stochastic exploration and conflicting gradient directions. In this paper, we propose a novel multi-agent policy gradient algorithm called {\itshape{Advantage Constrained Proximal Policy Optimization}} (ACPPO). Based on {\itshape{multi-agent advantage decomposition lemma}}, ACPPO introduces an advantage network for each agent to estimate current local state-action advantage. The coefficient of each agent constrains the joint-action advantage according to the consistency of the estimated joint-action advantage and local advantage. Unlike previous policy gradient-based MARL algorithms, ACPPO does not need an extra sampled baseline to reduce variance. We evaluate the proposed methods for continuous matrix game and Multi-Agent MuJoCo tasks. Results show that ACPPO outperforms the baselines such as MAPPO, MADDPG, and HAPPO.

Under review as a conference paper at ICLR 2023
ADVANTAGE CONSTRAINED PROXIMAL POLICY OPTIMIZATION IN MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We explore the combination of value-based method and policy gradient in multi- agent reinforcement learning (MARL). In value-based MARL, Individual- Max (IGM) principle plays important role, which maintains the consistency between joint and local action values. At the same time, IGM is difficult to guar- antec in multi-agent policy gradient methods due to stochastic exploration and conflicting gradient directions. In this paper, we propose a novel multi-agent pol- icy gradient algorithm called Advantage Constrained Proximal Policy Optimiza- tion (ACPPO). Based on multi-agent advantage decomposition lemma, ACPPO takes an advantage network for each agent estimate current local state-action advantage. The coefficient of each agent constrains the joint-action advantage according to the consistency of the estimated joint- action advantage and local ad- vantage. Unlike previous policy gradient- based MARL algorithms, ACPPO does not need an extra sampled baseline to reduce variance. We evaluate the proposed methods for continuous matrix game and Multi-Agent MuJoCo tasks. Results show that ACPPO outperforms the baselines such as MAPPO, MADDPG, and HATRPO.
INTRODUCTION
Many complex sequential decision-making problems in the real world that involve multiple agents can be described by Multi-Agent Reinforcement Learning (MARL) problem, including autonomous vehicles (Chang et al. 2021), logistics management (Wang et al. 2017). and electric transportation
(Chen & Wang 2020 MARL in real-world environments usually requires systems with scalabil- ity and distributed execution capabilities (Shao et al. (017). centralized controller will suffer from the exponential growth of the action space with the number of agents increasing (Hu et al.) 202T]. Based on the parameter sharing, decentralized policies can reduce the complexity tasks and enable scalable structures (Shao et al. 2019b). However, directly deploying single-agent rein- forcement learning in MARL suffers from a non-stationary issue. To stabilize the training process, MARI introduces monotonic improvement from trust region methods and Centralized training and Decentralized Execution (CTDE) from value-based methods.
Trust region learning has played major role in recent policy gradient methods (Shao et al. 2019a
Kakade 2001). Trust Region Policy Optimization (TRPO) (Schulman et al.) 2015) and Proximal Policy Optimization (PPO) (Schulman al.] (017)) methods have achieved outstanding performance in single-agent reinforcement learning. The Key point of effectiveness of the trust region methods is based on the theoretically-justiinne
guarantee of monotonic performance improvement each step. With KL divergence constraint, parameters can be updated within trust region that avoids the gradient being too aggressive. Based on parameter sharing, centralized critic, and PopArt (Hessel et al., 2019). MAPPO (Yu et al., (021) achieves good performance in multi-agent environments. Unfortunately, the value function of MAPPO is affected by the exploration of other agents, mak- ing the convergence of MAPPO unstable. Kuba et al. (2021) introduce the optimal baseline for more accurate estimate the state value function in MAPPO. The optimal baseline is based on an estimated hypothesized joint action value, which may introduce potential estimation errors. How- ever, examples (Kuba et al., 2022) show that MAPPO does not guarantee consistent improvement with correct gradients. To obtain the guarantee of monotonie improvement in MARI,, Kubal

---

Under review as a conference paper at ICLR 2023
et al. (0022) introduces HATRPO. HATRPO implements heterogeneous agents and stochastic up- date schemes of agent gradient directions to obtain guarantee monotonic improvement. At the same time, HATRPO does not apply centralized critic but transmits the updated information of previous agents by compound policy ratio. However, the time complexity of the sequential update method is too high, and it is difficult scale to the scenarios with large number of agents.
In this paper, we propose Advantage Constrained Proximal Policy Optimization (ACPPO), a novel multi-agent policy gradient method based on the advantage decomposition lemma. ACPPO adopts a policy subset, and each agent updates its policy according to their subset. The policy subset avoids the inefficiency caused by sequential updates and the instability caused by important sampling while ensuring improvement consistency gradient updates. A fictitious joint-action advantage function is estimated by summation of set of local advantages which is learned by each agent. Based on the current advantage and previous advantage, each agent can estimate the consistency of change be- tween their local advantage and joint advantage of the policy subset. The local advantage of each agent will be scaled ensure that each local policy gradient update improves the performance of the policy subset. In practice, we propose three variants of ACPPO. Advantage Constrained Proximal Policy Optimization with Hard Threshold (ACPPO-D) is the combination of the proposed constraint coefficient and PPO. However, the hard threshold is too sensitive to errors. Therefore, we propose ACPPO with soft threshold, including Advantage Constrained Proximal Policy Optimization with Kurameter-Sharinne (ACPPO-PS) and Advantage Constrained Proximal Policy Optimization with Heterogeneous (ACPPO-HA). The main contributions of this paper are summarized as fol- lows:
We present a constraint coefficient to the local advantage, which is estimated by the dif- ference between the local and fictitious joint advantage functions, to ensure the consistent improvement of joint policy.
We propose policy subset to heterogeneous estimate constraint coefficient to ensure mono- tonic improvement while avoid inefficiency caused by sequential updates and numerical overflow of important sampling.
We evaluate ACPPO on benchmarks of Multi-Agent MuJoCo against strong baselines such HATRPO, MAPPO, and MADDPG. The results show that ACPPO achieves state-of-the- art performance across all tested scenarios and demonstrate that the parameter sharing agent without centralized mixing network performs well in Multi-Agent MuJoCo environments.
2 BACKGROUND AND PRELIMINARIES
2.1 COOPERATIVE MARL PROBLEM
A fully cooperative multi-agent problem can be described a six elements tuple < P, S,
>. The N = [I....,n] n. is the set of agents, S donates the finite state space,
A= ii=1- A' is the joint action spaces of all agents, P :: S x A x S is the transition probability function, r x A- + R is the reward function, and 7 E [0, 1) is the discount factor. At each time step t N. the agents takes an action af E A' state S E S. The combination of each agent's ' action can be described as joint action a, = (a),.., a.) E A, drawn from the joint policy T (-1s:) = n (-1ss). Based on the A and 8t, the agents receive reward r; =((se a.) E R, and move to state 8t+1 according to the probability P(st4a (8t, ). Po is the distribution of the initial state so, and the marginal state distribution time t denoted by P The state value function and the s] >r = 8, = a). The advantage function can be
state-action value function are defined as follows: (s) = Bao. -0. PP dc 7're|50
and (x, a) = described as Art a) = (r,s, a) Vz (s).. The objective of the agents in cooperative problem is to maximise the expected return J(TT) = E appr av:s ~ 2e= >+re]- The set of all agents excluding agents (i,, im) is represented by -(1,,.,,,m)
E 20
Their local joint state-action value (f [Q=]. which is the expected return for the action a (f1...)dm)) chosen by the set of agents (i1, ..., im). The local advantage function defined as follows: Ax a (1)))))))
function are defined as Qn (ii....))))) = E. - (4--)1))))))m......
Qm (s. a (lm)))))) a (f....mm)) Q= a -(1)....mm))
In additional, the notations Q, V. ग =< n¹ ..... TO" > are used to represent updated Q, V, π =<
n
2

---

Under review as a conference paper at ICLR 2023
2.2 TRUST REGION METHODS REINFORCEMENT LEARNING
To monotonically improve the performance of the agent at each iteration, TRPO (Schulman et al. 2013) and PPO (Schulman et by the following theorem.
2017) were proposed in single-agent RL. TRPO can be described
Theorem 1. (Schulman er
2015) Let Dmax (T, max, (=L( (+1s)) and L
[Tx + Ex-p,,,aa (8) (). Then the following bound
(
(T)
CDRL (T,
holds, where C
4ry max.. [A. (s.a]
(1-2)²
T,,(T) is the estimation of the actual performance of the sampled policy л. When the distance between current policy and sampled policy मे decreases, the accuracy of [T)(T) increases. Based on above theorem, the agent updates its policy within trust region step & + according to
T arg max ( (T) CDRL KL (Tk T))-
Within trust region, the above update guarantees a monotonic improvement of the policy. practice, parameterized policies n is updated as follows:
0k+1 arg max Lio,, L (Te), subject to Es-po, [D (TeL Ro)l S
At each iteration k TRPO uses heuristic algorithm to search target policy Tx+1 within trust region. To reduce the et al., which uses only first-order derivatives. PPO optimizes the parameters of policy by maximizing PPO-clip surrogate objective
Ex-pe, [Dx k (To,: Ta]] when updating To, PPO was proposed by Schulman
L PP0 (TT) Ea-wyg PMp mop
min
Tel (a s)
Ane, (s, a), clip( T0 (a|s) 1 1 e) (s.a)).
Te
(4)
.To (a|s)
The ratio (a(a))) beyond the threshold interval c clipped to constraint the size of policy updates. Tot (als)
2.3 VALUE DECOMPOSITION METHODS
CTDE is popular cooperative MARL framework. The agent is trained by centralized critic who has access to the global state and the actions other agents. IGM principle requests consistency between joint and local greedy action values:
arg max (s a) = (arg max, Q(s, a"), .'),,.,, arg max, Q(saa)))
(5)
To implement the IGM principle value-based multi-agent reinforcement learning, QMIX proposed non-negative parameters mixing network. The mixing network ensure the monotonic relationship between a joint-action Q (s, a) and each (=,s,
aQ*(s,a)
2 0, E AA' (s,
2.4 TRUST REGION METHODS MULTI-AGENT REINFORCEMENT LEARNING
In recent years, a series of trust-region methods were proposed in multi-agent reinforcement learn- ing. A typical parameter sharing approach MAPPO, where the policy parameter 0 considers the trajectories collected by all agents and is updated by maximizing the objective of
min (a(a'ss) To (a'ls)
To (a ())
I, MAPPO (IO)
Ee wot prep
ATe, (s,a'), clip( No, (a (clls)" 1 + c) c)ATT, (s, as)
HATRPO Kuba al. 2022 is heterogeneouu--ggent TRPO method based the multi-agent
advantage decomposition lemma, which shows that the joint-action advantage function can be de- composed into summation of each agent's local advantages.
3

---

Under review as a conference paper at ICLR 2023
Lemma (Multi-Agent Advantage Decomposition). (Kuba al. 2022) Given a joint policy π, for any state s, the following equation holds for any subset of 11:m agents in Markov games,
A (s, (t:m
Σ
(s, (s
j=1
Based on multi-agent advantage decomposition lemma, HATRPO generalizes Theorem I to multi- agent systems as follows:
( 2 J(TT)
Σ
Tl) CDRL (T' ,
The above equation provides the key idea of HATRPO, which is the sequential update scheme. Each policy can guarantee incremental updates. In practice settings, parameterized multi-agent policies im E TT frim is updated as follows:
" (a'm "s, a), where M Mirm fimm- (a [s) A(s, a)
O2+1
(a'm Is)
11 (attmm-1 18)
(10)
subject to IE Mepporr, [DL (T (+ss), (-1s)) S 6,
where n (-Is) is designating policies for each state, A(s, a) is an estimate of the advantage func- tion. To reduce the computation cost of Hessian of the expected KL divergence, HATRPO can be simplified to HAPPO by considering using first-order derivatives as follows
TT (a 8)) tm
aa(a (s|s
Ea SrupT
min
M (s, a), clip( #0 (a'ls)
1 1 c)M (s, (t))) a))
(11)
20 (a'ls)
Due to the update schemes, each agent has to wait for the other agents to finish updating. To take full advantage of update schemes, HATRPO introduces heterogeneous parameters that increase the total weight of agents to make it able to express complex joint policies.
3 METHOD
In this section, we propose a novel MARL policy gradient method called ACPPO. ACPPO combines the value decomposition method and policy gradient satisfy monotonic consistency between joint and local advantage. Subsection 3.2 we present advantage constrained policy gradient, and in Subsection 3.2 we propose practical applications of ACPPO, including ACPPO-D, ACPPO-PS, and ACPPO-HA.
3.1 ADVANTAGE CONSTRAINER POLICY GRADIENT
Based Lemma D similar to QMIX, the estimated joint-action advantage function be repre- sented by the summation of the local advantage function. By imposing a monotonic constraint on the relationship between A (s, a) and A(s, a's, the global arg max on joint-action yields the same results as a set of arg max individual action as follows/ Wang et al. 2021):
arg max A a) (arg max,) A(s, a ... arg max." A(s, (s).a))).
(12)
In CTDE method, the decentralized advantage A(s, a²) satisfying the IGM principle is estimated by centralized mixing network. If all agents satisfy the IGM principle, the non-empty subset of N also satisfies the IGM principle. Therefore. the advantage function of the current subset can be estimated as follows:
Axtrnm (8, a ft:m
Σ
ai A (8,
(13)
Without an unbiased centralized critic, difficult to get the accurate a;,- At the same time, the local policy gradient based on decomposition advantage does not guarantee the monotonic improve- ment of joint policy. To guarantee the monotonic improvement of the joint policy, we evaluate the consistency of the current local and global gradients based on the updated joint policy performance.

---

Under review as a conference paper at ICLR 2023
Given designating policies it, its sampled action be expressed According Theorem the advantage of policies ग can be described by A(s, a²m) when the distance between policies and current policies π is small. The correlation of the local advantage Agim to the change of joint-action advantage A A can be described as follows:
aQ m (s, a allmm)
@# (s, a
Q (s, f1:m
lim サ
=Q (s, afm)
Qa
(x, a²m)
@a (8, (s,at (
V*(()) -Q (8. (..aaim)) (s)
lim #
Q= a'm)
V*(s) Qx((s, + V+(s)
(14)
A #llm (8, a lim サ-
A (8, a a
Ax (s
A amm)
AAC
(s, a (fmm))
A (s, (s.a'm)
-m (s, a afum)) is obtained by subtracting the previous (s) from the current (= atum). Ac- cording to the requirement of consistency between joint advantage and local advantage, the con- straint coefficient of the agent ij is defined as follows:
AA a Myy (s,a
>
sts (s:a'5)
0i
Ar" t1.5 (s,a))s)
(15)
A AA,
213 (#,a'))
The constrained advantage for updating policy is described as follows:
A. = a,,
(16)
Oi, ensures that only the sampled set of actions that satisfy IGM principle is used to update policy. The decomposition operation avoids sequential updates and the conduction of compound policy ratios. The policies are updated by constrained advantage follows:
ACPG L L (T))) Ea- sarppn Top (a'(s)A (s.a')) no.
(17)
The structure of ACPG introduces value decomposition without centralized critic. This makes it more suitable for MARL tasks with large numbers that exceed the capabilities of centralized critics.
3.2 ADVANTAGE CONSTRAINED PROXIMAL POLICY OPTIMIZATION
Target agent
Agent
Agent M
A ( (8, all a (s,
A A (e, (im)) (x,
Ags (a, (,,(),)) (2,0t)
Agai (s, mm)) Agin "
Agtm (s
gradient
gradient
Agent
Agent M
Current agent
Figure 1: The ACPPO setup. The current network is used to sample data and estimate local advan- tage. The target network is used to estimate previous advantage.
As shown in Figure [ to apply equation 17 in practice, we use a actor-critic framework with an additional local advantage function in ACPPO. A target network is introduced ACPPO to record
5

---

Under review as a conference paper at ICLR 2023
the current network for precise estimating KL divergence and previous advantage. At each step, the current advantage function of each agent is optimized by gradient descent to minimize the following loss
I Eyen( (Ags (s, a²))) Ags (s, a²)))
(18)
where Age, a²) could be any kind of estimated advantage, such GAE. According to Ags (8, a²)), a fictitious joint-action advantage function A (s, am)m)))))))) could be estimated by
summation of the local advantage function as follow:
A filmi (8, a (a
Σ (8,0
(19)
Based on the requirements of cooperative task, fictitious summation-based joint-action advantage function can represent the trend of joint policy performance. At each epoch, the target network provides the previous local advantage of current sampled action, and is used to calculate the tar- get joint-action advantage. According to the current advantage function and the target advantage function, the constraint coefficient O'i, can be estimated equation 15 Since it is hard-threshold variant, we record as ACPPO-D.
In the early stages of training, the advantage function is inaccurate. Inaccurate estimation may prevent the agent from updating, resulting in too few agents to be updated. Therefore, we introduce a soft threshold that allows more agents update while maintaining consistency as follows:
A Flig (s, a alis) - A - (s, (s.a
= clip(cxpp
().
(20)
A サッ (s. a²)) - A ;, (s.
We introduce exponential functions and clip operation to get of The exponential function relaxes IGM principles to allow more agents to be updated. The clip operation prevent af, from overflow underflow. Bringing the advantage An (s, a) and af, into equation I6 yields the constrained advantage. The policy network of ACPPO is trained by PPO follows:
12
min To(a')s) Ano, a') clip( To(a'ls) Tox (a'ls) c)ATo, (s.a")
I TAPPPO Mo
(TO)
Eainao Pak
no. (a'ls)
where Ann, (s, = oi ATH, (s, a),
(21)
The critic network is optimized to minimize the following loss:
Ejen
Eag
2'relso = Vi [s)]
(22)
According to whether the method of parameter sharing is adopted, ACPPO is divided into parame- ter sharing variant called ACPPO-PS and heterogeneous parameters variant called ACPPO-HA. To summarize, Algorithm is proposed follows:
Algorithm Advantage Constrained Proximal Policy Optimization
1: Initialize the joint policy æTo = (m).... m()).
2: for == 0, 1,... do
3: Collect sets of trajectories (st, a,, $1+1. r2) by running policy in the environment.
4: Backup current network with target network.
5: Update current advantage network by minimizing loss I,A_
6: If soft threshold is true
7:
Compute af, based on equation 20) If hard threshold is true
8:
9:
Compute at, based on equation [5]
Update policy network by minimizing maz
ACPPO
11:
Update critic network by minimizing V.
12:
end for

---

Under review as a conference paper at ICLR 2023
4 RELATED WORK
There exists a series of methods that extend policy gradient methods into MARL. IPPO (de Witt al., 2020) implements vanilla PPO in MARL problem, achieves better results on simple MARL tasks. However, the results show that naively applying PPO in MARL can not guarantee conver- gence. Yu et al. (202T) proposed MAPPO, which shows the hyper-parameter factors are critical to the performance of MAPPO. MAPPO has to maintain small KL divergence to avoid policy collapse, severely restricting times of searching iteration. Foerster et al. (2018) proposed the coun- terfactual baseline improve efficiency in policy gradient learning. [Kbba al. (02II) proposed optimal baselines in MAPPO to reduce variance in gradient. These methods require additional sam- pling and repeated estimation, which is difficult to ensure accuracy in practice. |Kuba al. (2022) proposed HATRPO that is guaranteed to monotonic improve the performance of policy and gave de- tailed proof for the first time. However, each agent has wait for previous agents to finish updating to get the important sampling ratio as an input factor. For tasks with a large number of agents, the cost of optimization time will be unacceptable and the factor of HAPPO will exponentially increase as the number of agents increases.
Value-based reinforcement learning another classical MARL method. [Sunehag al. (0188) pro- posed VDN which represents joint action value function as summation of local action value function to achieve Centralized Training Decentralized Execution. Based on VDN, (Rashid et al. 2018) pro- posed QMIX, which introduces non-negative mixing network to the centralized critic. The mixing network enforces monotonic consistency between the joint and local action values. To further reduce the learning difficulty, QPLEX (Wang et al. (021)) uses a dueling mixing network to decompose the joint action value into a joint-action advantage and a joint state value. These algorithms require a centralized critic and cannot be directly applied for policy gradient.
EXPERIMENTS AND RESULTS
In this section, we benchmark ACPPO against the baseline algorithms on continuous matrix game and Multi-Agent MuJoCo (Peng et al.) (021), including HATRPO, HAPPO, MAPPO, MADDPG, and IPPO. The scenario of continuous matrix game is proposed by Peng et al. (002T) to demonstrate the convergence performance of ACPPO and MAPPO on cooperative tasks. Multi-Agent MuJoCo tasks require a set of agents to control different joints of the robot to learn an optimal motion as shown in Figure 5a in Appendix A..3 The number of body joints could be quite large in Humanoid and ManyAgentS wimmer. which increases the costs of learning optimal policy. Table Tin Appendix A.2 lists the common hyper-parameters used for IPPO, MAPPÓ, ACPPO-PS, ACPPO-HA, HAPPO, and HATRPO. Table 2 in Appendix [A.2 lists the different hyper- parameters. The Adam optimizer constrains the update step size by history gradient variance, so it has the characteristics of stability and has been widely used in the previous methods. However, the Adam optimizer does not fully utilize outlier data, which affects the update efficiency in mueti- reinforcement learning, so ACPPO uses the RMSprop instead.
5.1 CONTINUOUS MATRIX GAME RESULTS.
Experiment results are shown in Figure 4b of Appendix A. MAPPO fails converge stably within 200k, while ACPPO-PS and ACPPO-D converge to the optimal policy.
5.2 MULTI-AGENT MuJoCo RESULTS
Figure demonstrates that, in all scenarios, ACPPO outperforms the selected compare methods, including parameter sharing methods and parameter-independent methods. Experiments show that ACPPO can achieve the best performance in Multi-Agent MuJoCo. With a heterogeneous agent structure, ACPPO-HA can further enhance ACPPO optimization efficiency and stability, but the final performance improvement is not significant. When the number of joints is greater than 10, the time cost of a heterogeneous agent structure with a sequential scheme is unacceptable, including Humanoid and ManyAgentS wimmer. We limit the number of epochs of ACPPO-H HA in Humanoid and MlayyAgeSSwimmee which severely limits its practical performance. In most scenarios, the performance of ACPPO-D and ACPPO-PS are comparable. As the number of agents increases the
7

---

Under review as a conference paper at ICLR 2023
ACTRO-HA
ACPPOND
ACPRO-PS
HATRIO
HAPPO
MAPPO
MADDPG
IPPO
Ant2x4
Ant4x2
Ant8x1
Average Episode Reward
Average Epitode Reward
Averaage Episode Reward
4000
4000
6000
2000
0.00
0.25
0.75
1,00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Environment steps
Environment steps
x10"
Environment steps
(a)
(b)
(c)
HalfCheetah-v2-233
HalfChestah-2--44
HalfCheetah-22-6zl
Averago Episade Reward
Average Episade Reward
Average Episade Reward
4000
4000
2000
2000
2000
Environment steps
x10
Environment steps
x10"
Environment steps x10
(d)
Walker2x3
Walker3x2
Walker6x1
Average Episods Reward
6000
Averaage Episode Reward
5000
Average Episode Reward
6000
4000
2000
2000
2000
2000
1000
0.00
0.25
0.50
0.75
1,00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0:75
1.00
Environment steps
XII
Environment steps
x10"
Environment steps
x100
gg)
(h)
ii)
Humanoid17x1
HumanoidStandup177l
ManyAgentSwimmer1000
Average Episode Reward
Average Episode Reward
Average Episode Reward
300
4000
1,50000
3000
100
2800
1000
50000
-200
Environment steps
Environment steps (k)
Environment steps
x10"
Figure 2: Performance comparison on multiple Multi-Agent MuJoCo tasks. ACPPO-PS and ACPPO-HA outperform selected algorithms in all MuJoCo scenarios. Mean and standard devia- tion are shown across 3 runs.
task becomes more complex, the variance of the performance of ACPPO-D increases. In Humanoid 17x1, ACPPO-D is worse than HATRPO, indicating that hard threshold truncation is hard to meet the needs of complex tasks.
8

---

Under review as a conference paper at ICLR 2023
Amt442
Time-performance Compare
Average Episode Reward
4000
Episode Reward Rate
2000
1000
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Environment steps
100
Time rafe
(a)
(b)
Figure 3: Performance with varying levels of ACPPO-PS policy sample reuse. Time and perfor- mance compare rate between HATRPO and ACPPO-PS. The calculation uses the final performance of HATRPO as the denominator. The higher the episode reward rate, the better the performance of ACPPO-PS. The lower the time rate, the faster ACPPO-PS can optimize.
5.3 SAMPLE EFFICIENCY
In practice, whether the marginal benefits of independent parameter and sequential update schemes are worth the exponential increase training time cost is question worthy of discussion and anal- ysis. First, we evaluate how performing additional epochs during the policy update impacts perfor- mance. Figure Sajshows the performance ACPPO with different numbers of epochs from to 80, As we can see, with more policy epochs, ACPPO can achieve higher data efficiency. It is crucial to improve the performance by increasing the number of epochs to reuse the information of each sampled data. However, due to the potential unstable gradient direction, MAPPO and IPPO do not use a larger number of epochs to avoid policy collapse. Methods with sequential schemes guarantee the monotonic improvement properties of MARL,, such as HAPPO and HATRPO. Yet, HAPPO does not use large number of epochs due to the exponential growth of the compound policy ratio. A growing compound policy ratio could cause overflow to interrupt training. At the same time, HA- TRPO uses the linear programming method to search gradient, and the number of searches is about 200 times. The update step size of ACPPO is constrained by the advantage function and does not use compound policy ratio, so there is no risk of overflow.
5.4 TIME EFFICIENCY
We now compare the time costs between sequential updates and synchronous updates. We wonder whether the increase in time cost can bring enough performance improvement, FigureB3b shows the comparison of efficiency and performance between ACPPO and HATRPO. The abscissa is the time comparison. The total training time of HATRPO is used as the denominator, and the total training time ACPPO is used as the numerator. The ordinate is the performance comparison, The final performance of HATRPO is used the denominator, and ACPPO is the numerator. As the number of times per agent increases, the overall optimization time increases exponentially in the method with sequential schemes. Therefore, the time cost of the sequential update scheme in multi-agent reinforcement learning is very high.
6 CONCLUSIONS
In this paper, propose novel MARL policy gradient method based on advantage decomposition. The key idea of the algorithm is to introduce constraint coefficients to ensure that the update direc- tion of the local policy is consistent with the joint policy. Based this, introduce practical deep MARL algorithm: ACPPO. Experimental results show that ACPPO achieves state-of the-art performance in continuous control task Multi-Agent MuJoCo.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint /606.01540, 2016.
Huan Chang, Yicheng Chen, Baochang Zhang, and David Doermann. Multi-uat mobile edge com- puting and path planning platform based on reinforcement learning. IEEE Transactions on Emerg- ing Topics in Computational Intelligence, 2021.
Yize Chen and Hao Wang. Intelligentcrowd:: Mobile crowdsensing via multi-agent reinforcement learning. IEEE Transactions on Emerging Topics in Computational Intelligence, 5(5):840-845, 2020.
Christian Schroeder de Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip HS Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi-agent challenge? arXiv preprint a.X55:201..09533, 2020.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 33, pp. 3796-3803, 3803, 2019.
Guangzheng Hu, Yuanheng Zhu, Dongbin Zhao, Mengchen Zhao, and Jianye Hao. Event-triggered communication network with limited-bandwidth constraint for multi-agent reinforcement learn- ing. IEEE Transactions Neural Networks and Learning Systems, 2021.
Sham M Kakade. A natural policy gradient. Advances in neural information processing systems, 14, 2001.
Jakub Grudzien Kuba, Muning Wen, Linghui Meng, Haifeng Zhang, David Mguni, Jun Wang, Yaodong Yang, et al. Settling the variance of multi-agent policy gradients. Advances in Neu- ral Information Processing Systems, 34:13458-13477 2021.
Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. In International forum?
Conference on Learning Representations, 2022. #d=F.GGFFNNTxol
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Fierre-Alexande Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Facmae: Factored multi- multi-agent agent centralised policy gra- dients. Advances in Neural Information Processing Systems, 01:11280-1222.1 2021.
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.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.0634 2017.
Kun Shao, Yuanheng Zhu, and Dongbin Zhao. Cooperative reinforcement learning for multiple units combat in stareraft. In 2017 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1-6, 2017.
Kun Shao, Zhentao Tang, Yuanheng Zhu, Nannan Li, and Donghin Zhao. A survey of deep rein- forcement learning in video games. arXiv preprint arXiv: 100499/2109444,, 10944, 2019a.
Kun Shao, Yuanheng Zhu, and Dongbin Zhao. Stareraft micromanagement with reinforcement learning and curriculum transfer learning. IEEE Transactions on Emerging Topics in Computa- fional Intelligence, 3(1):73-84, 2019b.
10

---

Under review as a conference paper at ICLR 2023
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Valossteoonnooition networks for cooperative multi-agent learning based team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgen gent Systems, pp. 2085-2087. Inter- national Foundation for Autonomous Agents and Multiagent Systems, 2018.
Jianhao Wang. Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. {QPLEX): Duplex dueling
multi-agent q-learning. In International Conference on Learning Representations, 2021. URL
httpss:/gpenrevil ew net / forum?i d=r
Shir Li Wang, Kamran Shafi, Theam Foo Ng. Chris Lokan, and Hussein A Abbass. Contrasting human and computational intelligence based autonomous behaviors in a blue-red simulation en- vironment. IEEE Transactions on Emerging Topics in Computational Intelligence, 1(1):27-40, 2017.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arX1v:2103.01955, 2021.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 MATRIX GAME
Continuous Matrix Game
Episode Returns
ACPRO ACPICIPS
MAPPO
50
100
1.00
200
T(k)
-3% -036 -031 633
033 230
236
1.00
(b)
Figure 4: The continuous matrix game.
Figure shows a simple continuous cooperative matrix game with two agents. One agent can only control the abscissa position, and the other controls the ordinate position. There is reward function describe a narrow path from origin to maximum reward point (1, 1). Otherwise, there is small punishment for moving away from the origin as follow:
xx x ,>0, >
r(a' r(at,a²) -0.1z= +12)
H2--
(23)
otherwise
A.2 HYPER- PARAMETERS OF ACPPO
Table I: Common
used for IPPO, MAPPO, HAPPO, HATRPO, ACPPO-PS, and
ACPPO-HA in Multi-Agent MuJoCo tasks
hyper-parameters
value
hyper-parameters
value
critic
5e-3
std x coef
activation
ReLU
std y coef
0.5
gamma
0.99
max grad norm
hidden layer
network num mini-batch
mlp
hidden layer dim
64
batch size
4000
training threads
rollout threads
4
episode length 1000
entropy coefficient
0.01
eval episode 32
Table 2: Different parameesss used for IPPO, MAPPO, HAPPO, HATRPO, ACPPO, and ACPPO-HA in Multi-Agen MuloCo tasks
IPPO HАPPО
ACPPO ACPPO-HA
HATRPO
Algorithms
MAPPO
actor ppo epoch
5c-6
5c-6
5
50
kl-threshold
/
/
5e-3
ppo-c
0.2
0.2
/
accept ratio
/
/
0.5
optimizer
Adam
RMSprop
Adam
A.3 MUJoCo ENVIRONMENT
12

---

Under review as a conference paper at ICLR 2023
Legend
t.y
Lx
Hinejsist
(abbel)
Hingejile (txel) (alebal)
Hing
H)
Figure 5: Agent partitionings for Multi-Agent Mujoco environments: A) 2-Agent Swimmer [2x1], B) 3-Agent Hopper [3x1], C) 2-Agent HalfCheetah [2x3], D) 6-agent HalfCheetah [6x1], E) 2- Agent Humanoid and 2-Agent HumanoidStandup (each [1x9, Ix8]), F) 2-Agent Walker G) 2-Agent Reacher [2x1], H) 2-Agent Ant [2x4], 2-Agent Ant Diag [2x4], J) 4-Agent Ant [4x2]. Colours indicate agent partitionings. Each joint corresponds to single controllable motor. Split partitions indicate shared body segments. Square brackets indicate [nnmmerr of agents) (joints per agent)).
Joint IDs are in order of definition in the corresponding OpenAI Gym XML asset files (Brockman cct al. 2016). Global joints indicate degrees of freedom of the center of mass of the composite robotic agent.
13


Reviews:
[{"review_id": "qNvvA9svH_", "reviewer": "Reviewer_U46S", "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": "The authors propose a novel multi-agent policy gradient algorithm called Advantage Constrained Proximal Policy Optimization (ACPPO).", "summary_of_the_review": "I don't think this paper deserves to be accepted.", "strength_and_weaknesses": "Strength:\n1. The author presents a constraint coefficient to the local advantage, which is estimated by the difference between the local and fictitious joint advantage functions, to ensure the consistent improvement of a joint policy.\n2. The author proposes a policy subset to heterogeneous estimate constraint coefficient to ensure monotonic improvement while avoiding inefficiency caused by sequential updates and numerical overflow of importance sampling.\n3. The structure of Figure 1 is more clearly represented.\n\nWeakness:\n1. The author seems to have tested only on the matrix game and MAmujoco environments, and as far as I know, there are other environments, including SMAC, Google Football, etc. I think the author's experiments are too single-minded and do not support well the innovation stated in the article.\n2. The authors mention several derivatives of ACPPO, including ACPPO-PS, ACPPO-HA, and ACPPO-D, but the descriptions in the text are too omitted, making it very confusing to read. Also based on the experimental results in Figure 2, I could not see any difference between these three algorithms, and also in the Mamujoco environment, there are no distinguishing experimental results.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "aOP7Ietqlyt", "reviewer": "Reviewer_ghg2", "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": "The paper studies trust region multi-agent policy gradients. The core contribution is a normalization term when calculating the advantage function. The authors compute the partial derivatives of global Q functions with respect to local utility functions to identify actions subject to the IGM condition. Only those \"IGM actions\" will be used to calculate advantage functions.", "summary_of_the_review": "The paper studies an important problems, but there are many issues about the proposed method.", "strength_and_weaknesses": "The reviewer is mainly concerned about the soundness of the proposed method. The use of partial derivatives in masking out action in the calculation of advantage functions is not well supported. In practice, the sign of the derivatives may change abruptly and is vulnerable to gradient noise, which may render the learning unstable.\n\nThe background section is clearly written, but the method section has various issues (discussed in the following sections) and is somewhat difficult to follow. The reviewer had to ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "W50uIMH9jna", "reviewer": "Reviewer_gE8o", "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": "The paper proposes a policy optimization method for MARL. To reduce the cost of sequential updates in HATRPO, it uses a network to estimate the local advantage, so agents can be updated efficiently. The consistency between the joint advantage and local advantages is constrained by coefficients, both hard/soft coefficients are explored. Experiments are mainly performed in multi-agent MuJoCo and the proposed method shows better performance than existing work. ", "summary_of_the_review": "It seems the paper is not ready to be published. The method is not sound in its current form, and the method section should be rewritten. Experiments on SMAC should also be included. ", "strength_and_weaknesses": "### About novelty\n\n- This paper seems to be the combination of HAPPO and linear value decomposition. What is the difference between eq. 11 and 21 if we apply the linear value decomposition on the critic of HAPPO? I think the idea of this paper is not quite novel.\n\n### The method section is hard to understand.\n- I do not understand how eq. 13 can be reached. What did I miss? The derivation should be given at least in Appendix. Or is it an assumption?\n- There are even more issues in eq. 14. Why the partial derivation $\\frac{\\partial Q_{ \\tilde{\\boldsymbol{\\pi}}^{i_{1:m}}  }}{\\partial Q_{ \\tilde{\\pi}^{i_{1:m}}  }}$ equals to a limit as $\\tilde{\\boldsymbol{\\pi}}$ approaches $\\boldsymbol{\\pi}$ in the first line? Why the limit in the third line equals to $\\frac{\\Delta A^e_{ \\tilde{\\boldsymbol{\\pi}}^{i_{1:m}}  } (s,\\boldsymbol{a}^{i_{1:m}})   }{\\Delta A_{ \\tilde{\\pi}^{i_{1:m}}  } (s,a^{i_{m}})}$ and what is the definition of $\\Delta A^e_{ \\tilde{\\boldsymbol{\\pi}}^{i_{1:m}}  } (s,\\boldsymbol{a}^{i_{1:m}})$ and $\\Delta A_{ \\tilde{\\pi}^{i_{1:m}}  } (s,a^{i_{m}})$? Moreover, what is the relation between $\\frac{\\Delta A^e_{ \\tilde{\\boldsymbol{\\pi}}^{i_{1:m}}  } (s,\\boldsymbol{a}^{i_{1:m}})   }{\\Delta A_{ \\tilde{\\pi}^{i_{1:m}}  } (s,a^{i_{m}})}$ and $\\alpha_i$ or what is your intuitive idea for the heuristic method in equation (15)?\n\n\nIn this section, many equations, such as 13, 14, 15, and 18, are not well supported, at least not well described. This makes the method hard to understand in its current form. It seems this section should be rewritten. \n\n### More experiments are needed. \n- In multi-agent MuJoCo, the proposed method outperforms baselines, but is based on only three seeds, which is not statistically sufficient. \n- **SMAC should also be included.** \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "O31mEIjK_J", "reviewer": "Reviewer_HtQd", "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": "This paper studies cooperative multi-agent reinforcement learning under the setting of centralized training and decentralized execution (CTDE). The authors propose a new algorithm based on two algorithm ideas --- PPO and IGM. In particular, PPO specifies how to update the policy in a single-agent RL setting, and IGM yields a decomposition of the Q function that enables the update of the joint policy to be factored into local policy updates in each agent. This paper combines these two approaches, but instead of using the Q function, advantage function is used, which is built on a result about advantage function decomposition proposed in a recent work. ", "summary_of_the_review": "This paper can be improved at least in four aspects: improving the novelty, add better motivation/explanation of the method for estimating the advantage function, more rigorous presentation, and correct typos/notations that cause confusion.  ", "strength_and_weaknesses": "Strength: The main strength of this paper seems that it proposes a new algorithm for MARL under the CTDE setting. It achieves comparable empirical performances to SOTA methods. \n\nWeakness: It seems that there are some aspects in which this paper could potentially improve. \n\na.\tNovelty. My main concern is about the novelty of this work. The proposed method seems a direct combination of existing methods --- PPO, QMIX, and the decomposition lemma in [Kuba et al, 2022]. \nb.\tDecomposition of Advantage Function. It seems unclear to me the role played by the decomposition lemma. First, in the lemma statement (Lemma 1), what are $ i_{1:m}$? This notation seems not introduced. If this is $i_1, \\ldots, i_m$, how do we these agents? Second, what is the advantage of using such a decomposition of advantage? Or where is it used in the algorithm? In (13), the authors construct another set of advantage function by treating the left-hand side as the $Q$ in IGM and finding some factorizations that ensure monotonicity. The left-hand sides of (13) and (8) are the same function, right? \nc.\tMathematical rigor. This paper seems to lack some level of mathematical rigor, which makes it hard to understand the merit of the algorithm. For example, when introducing the algorithm in Section 3, the authors handwavingly derive the constraint coefficient $\\alpha$ in (14). It is unclear to me how the limit is taken and what $\\Delta$ stands for. Is $\\Delta$ the derivative? If so, it seems that its computation is both computationally costly and sensitive to errors. \nd.\tTypos or Bad notation. There seem many typos or bad notation that can potentilly cause confusion. For example, in (12), the $A$ function on the right-hand side should be $A_{\\pi}$. In (14), there are $V_{\\pi}$ with $\\pi$ in boldface font and $\\pi$ in a standard font. The indices of agents being $i_1, \\ldots, i_m$ are also very confusing. \n", "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": {}}]

Author rebuttal:

Decision: Reject