Title: SCHOLASTIC-ACTOR-CRITIC FOR MULTI AGENT RE-INFORCEMENT LEARNING

Abstract: The Actor-Critic framework of multi-agent reinforcement learning(MARL) is gathering more attention nowadays. Centralized training with decentralized execution allows the policies to use extra information to ease the training while enhancing overall performance. In such a framework, the quality of critic profoundly impacts the final average rewards. Thus we present a method, called Scholastic-Actor-Critic(SMAC), that involves a more powerful critic to maintain efficiency in ample knowledge acquisition. The headmaster critic is designed to group agents with proper size and proper timing, while other critics update simultaneously at the decision time. The learning rule includes additional terms account for the impact of other agents within a group. Our method receives higher payouts compared to other state-of-the-art methods and is robust against the explosion of dimension during training. We apply our method to the Coin Game, the Cooperative Treasure Collection(CTC) (Lerer & Peysakhovich, 2017) and a dynamic battle game, MAgent(Zheng et al., 2018). Experiment results are all satisfying.

1. INTRODUCTION:

MARL(Multi-Agent Reinforcement Learning) is gathering more attention in deep learning researches.

Artificial agents thus perform better to interact both with other agents and humans in complex partially competitive or sequential dilemma occasions. MARL is a big topic with fully cooperative settings, competitive settings and mixed settings. It is still challenging to make decisions with inadequate information in applications, such as playing games, advertising and self-driving cars.

The ability to maintain cooperation and competition in a variety of complicated situations is essential in MARL. Early works focus on improving policy or value constructing methods (Foerster et al., 2018b) (Silver et al., 2016) (Sukhbaatar et al., 2017) (Gupta et al., 2017) , promoting more effectively opponent modeling methods (He et al., 2016) (Foerster et al., 2018a) (Metz et al., 2016) (Tesauro, 2004) and enhancing communication between opponents (Foerster et al., 2017) (Lerer & Peysakhovich, 2017) (Das et al., 2017) (Foerster et al., 2016) (Mordatch & Abbeel, 2018) (Sukhbaatar et al., 2016 ) (Lauer & Riedmiller, 2000) (Matignon et al., 2007) (Omidshafiei et al., 2017) .

In cooperative-and-competitive settings, Iterated Prisoners' Dilemma is a traditional problem, in which selfish actions usually lead to an overall bad result. At this time, cooperation maximizes social welfare, which leads to an average best outcome. In this setting, the measurement is the total of rewards of all agents, while randomly initialized agents usually pursue independent gradient descent on the specific value function. Lerer & Peysakhovich (2017) and Leibo et al. (2017) point out that reciprocity among agents results in a higher average reward. Peng et al. (2017) and Evans & Gao (2016) find that even in strongly adversarial settings, reciprocity shows its nontrivial value.

In traditional Q methods, each agent's policy changes over time, resulting in a non-stationary environment. In a non-stationary environment, agents are not able to make good use of naive experience replay. Recent years Lowe et al. (2017) propose the actor-critic framework(also called MADDPG), which combines offline and online learning, which enhances the ability for multi-agent learning. Then, (Yang et al., 2018) (MF-MARL), Iqbal & Sha (2018) (MAAC) and Jiang & Lu (2018) explore policy and communication optimizations within the Actor-Critic framework.

We here propose the Scholastic-Multi-Actor-Critic method(SMAC), which aims to improve the ability of the critic. We want to train a more powerful critic, the headmaster critic that enables actors to communicate more efficiently during training. The SMAC learns to control when and how an agent receives information from others. That is, the access of observations of an agent depends on the critic. This optional additional term when applied to a group of agents, leads to extra reciprocity and cooperation. The policy gradient is consistent with prior works presented by Sandholm and Crites Sandholm & Crites (1996) and Foerster et al. (2018a) .

Our approach enables high dimensional settings. We deploy experiments on the Coin Game4.1.1, the Cooperative Treasure Collection4.1.2 and the MAgent (Zheng et al., 2018) . Our algorithm leads to the overall highest average return on these games. All agents using our method achieve the stable equilibrium with less training resources.

2. RELATED WORKS:

As mentioned above, interactions between agents can either be cooperative, competitive or usually both. Model-free reinforcement learning algorithms in this domain could be concluded to value-based methods, policy-based methods and actor-critic methods.

MADDPG (Lowe et al., 2017) combines offline and online learning that enhances the ability of multi-agent learning. It allows the policies to use extra information to ease the training. The critic is enlarged with extra information about the policies of other agents, while each actor only has access to local information. Local actors are used at the execution phase after training.

COMA(Counterfactual Multi-Agent Policy Gradients) raised by Foerster et al. (2018b) is aimed to solve multi-agent credit assignment in cooperative settings. Before, each agent trains with his own critic so that the information sharing between them is insufficient, resulting in poor cooperation between agents. Therefore, the centralized critic firstly introduced in COMA to give a preliminary solution to this problem. MF-MARL, the Mean Field Multi-Agent Reinforcement method developed by Yang et al. (2018) try to model opponents by the use of Mean Field Theory under Q-learning and Actor-Critic methods. It uses numerical techniques that greatly reduce the cost of modeling opponents. Somewhat like COMA (Foerster et al., 2018b) , MAAC (Iqbal & Sha, 2018 )(Multi-Actor-Attention-Critic) considers to make full use of information and takes the attention mechanism within the centralized critic network. The experiment result shows that as the scale is growing, this method demonstrates its great effect. However, the requirement of computing is too high. On the other hand, ATOC (Jiang & Lu, 2018) (Learning Attentional Communication) decides to find a good communication group for the initiator agents by attention methods, too. Nevertheless, the determination of the initiator is very vague, and as the decisive role, if the initial selection is not appropriate, the entire model will collapse.

3. METHODS:



3.1. BACKGROUND:



3.1.1. STOCHASTIC GAME AND DEEP Q-NETWORKS:

A multi-agent stochastic game G is formulated by a tuple G = S, A, P, O, R, n, γ . S denotes the state space, the configurations for all agents. Each agent takes a i ∈ A at every time step, forming joint actions a ∈ A ≡ A n . To choose actions, each agent uses a policy π θi : O i × A i , which produces the next state according to the state transition function. P (s |s, a) :

S × A × S → [0, 1]

denotes transition probabilities of states, and o i ∈ O denotes observations. The reward function r i (s, a) : S × A → R specify rewards and γ ∈ [0, 1) is the discount factor, and for each agent,

R i t = ∞ l=0 γ l r i t+l .

Policy gradient methods update an agent's policy, parameterised by θ i .

Provided and initial state s, the value function of agent i under the joint policy π could be formulated as:

EQUATION

We define the Q-function within the framework of N-agent games based on the Bellman equation in

(1) such that the Q-function Q i π for agent i under policy π could be recursively formulated as

Q π (s, a) = E s [r(s, a) + γE a ∼π [Q π (s , a )]]

(2) , and deep Q-networks learn the action-value function Q * by minimizing the loss in (3):

EQUATION

and

EQUATION

where Q * is the target Q function and its parameters update periodically with the most recent θ, which stabilize the learning. Besides, the experience replay buffer D = (s, a, r, s ) also used to stabilization. However, because agents are independently updating their policies as learning progresses, the environment appears non-stationary from the view of any one agent, violating Markov assumptions required for convergence of Q-learning. Foerster et al. ( 2017)'s approach point out, another difficulty is that the experience replay buffer cannot be used in such a setting since in general.

3.1.2. POLICY GRADIENTS:

Policy gradient techniques (Sutton et al., 2000) aims to estimate the gradient of an agent's expected returns with respect to the parameters of its policy. This gradient estimate takes the following form as

(5):

∇ θ J (π θ ) = E a∼π θ ∇ θ log (π θ (a t |s t )) ∞ t =t γ t -t r t (s t , a t ) (5) 3.1.3 ACTOR-CRITIC METHODS

The term ∞ t =t γ t -t r t (s t , a t ) in the policy gradient estimator leads to high variance, as returns can vary drastically between training episodes. The Actor-critic method (Konda & Tsitsiklis, 2000) aims to ameliorate this issue by using a function to approximate the expected returns. Moreover, it replacs the original return term in the policy gradient estimator with this function. Siven a state and action, an agent under actor-critic methods learns a function to estimate expected discounted returns as:

Q ψ (s t , a t ) = E ∞ t =t γ t -t r t (s t , a t )

, it updates by minimizing the regression loss of:

EQUATION

where

EQUATION

in which Q ψ is the target Q-value function. A recent approache (Haarnoja et al., 2018) applies a soft value function by modifying the policy gradient to incorporate an entropy term to encourage exploration and avoid converging to non-optimal deterministic policies. It could be formulated as:

EQUATION

) where b(s) is a state-dependent baseline. The loss function for temporal difference learning is also revised with a new target, that is:

EQUATION

3.2 SCHOLASTIC-ACTOR-CRITIC Our method obeys the same paradigm of training critics centrally and executing learned policies distributedly. That is proposed to overcome the challenge of non-stationary environments. The main idea behind our approach is group discussion, which encourages agents to emulate those better than themselves with high efficiency. We design a more powerful critic, the headmaster critic, to learn how to group agents and determine when to communicate, that has the same effect of the attention mechanism. The additional critic has a global perspective of all agents and focuses on agents with highest and lowest rewards. Accounting for the impacts from opponents, observations and actions incorporate information into the estimation of each agent's value function in the same group.

3.2.1. ASSIGNMENT OF GROUPS:

Expand the setting of MAAC (Iqbal & Sha, 2018) , we introduce a headmaster critic to assign communication groups. The critic randomly selects n collections with random size s and changes every k epchos. After selecting n collections, we take the average contirbutions from each group(super agent, sa), and apply the following loss function:

EQUATION

where

EQUATION

The action-value Q ψ i (o, sa) function estimates outcomes in group i from 1 to n, which receives observations and actions of agents. To avoid the degradation, we set threshold for n as n/2 and s as s > 1.

3.2.2. CIRTICS IN GROUPS:

Critics within the same group updated together to minimize a joint regression loss function:

EQUATION

Note that Q ψ i (o, a),the action-value estimate for agent i, receives observations and actions for partial agents. Where,

EQUATION

in which ψ and θ are the parameters of the target critics and target policies, respectively.

3.2.3. AGENTS IN GROUPS:

To calculate the Q-value function Q ψ i (o, a) for agent i, the critic receives the observations o = (o 1 , . . . , o N ) and actions a = (a 1 , . . . , a N ) for all agents in a group. Then other agents' contributions could be formulated as 15. where g i is a two-layer MLP(multi-layer perceptron) embedding function and f i is a softmax function. It could be formulated as:

EQUATION

As shown in Foerster et al. (2018b) , an advantage function using a baseline that only marginalizes out the actions of the given agent from Q. It helps in credit assigning. In other words, by comparing the value of specific actions to an average action, an agent could learn whether the action he made would cause an increase in expected return. Thus the individual policies are updated with the following gradient:

EQUATION

b(o, a) is the multi-agent baseline that used to calculate the advantage function.

We implement a more general and flexible form of a multi-agent baseline. We do not apply a global reward, but naturally decompose an agent's encoding observations and the average of encodings of other agents.

EQUATION

As shown above, we output the value for every action and add an observation-encoder as

E i = g i (o i ).

For each agent, using these encodings in place of the E i = g i (o i , a i ) described above, and modify f i such that it outputs a value for each possible action. We can estimate the expectation by sampling actions from our policy and averaging their Q-values. So we do not need to add any parameters in the case of continuous policies.

4. EXPERIMENTS 4.1 SETUP:

We operate our algorithms in various settings, including the Coin Game 4.1.1, Cooperative Treasure Collection(CTC) (Lerer & Peysakhovich, 2017) 4.1.2 and MAgent (Zheng et al., 2018 ) (a cooperativecompetitive battle game in the Open-source MAgent system) that tests capabilities of our approach and baselines. The three games we raised, from simple to complex, are all facing iterated prisoners dilemmas (Luce & Raiffa, 1958) . For each setting, we study the scalability of different methods as the number of agents grows and evaluate their ability to attend to information relevant to rewards.

4.1.1. COIN GAME:

The Coin Game is a higher dimensional alternative of IPD (iterated prisoners dilemma), which is convenient to make comparisons to previous works. As shown in 1, two agents with red and blue colors are tasked to collect coins which are either red or blue on the grids. A new coin with random color appears randomly after the last one is picked up. Agents move to a coin's position and both receive a point after picking it up while the agent with a different color loses 2 points. When they only pick up coins with their own color, the total return is maximized. While players usually pick up different ones. Therefore the maximum achievable collective return is approximately 50 in expectation if neither agent chooses to defect and both agents collect all coins of their own color. In this game we define niceness as n (s t , a t ) to be part of the measurement. If an agent takes action a i t , picks up a coin which penalizes the other players, n (s t , a t ) = -1. We use recent defections as the measure of niceness N (T ) = t i=1 λ t-i n (s i , a i ) at time T .

4.1.2. COOPERATIVE TREASURE COLLECTION:

Cooperative Treasure Collection(CTC), as shown in 1, is a variant of Coin Game in which agents play roles as hunter or bank. "Hunter"s are tasked to collect the treasure of any color and deposit them into the corresponding colored bank. The "Bank"s are tasked to gather as much treasure as possible from the "Hunter"s simply. Agents could see each others' positions and concern their own. "Hunter"s receive a global reward for the successful collection of treasure, and all agents receive a global reward of the depositing amount. "Hunter"s will additionally penalized for colliding with each other. As such, the task contains a mixture of shared and individual rewards. It requires different "modes of attention" which depends on the agent's state and other agents' potential actions that affects its rewards.

4.1.3. MAGENT:

The mixed cooperative-competitive battle game, MAgent (Zheng et al., 2018) ,is a more complex multi-player environment. Agents are devided into armies, and required to take a series of actions while exact discounted reward cannot be assessed. Each army consists of homogeneous agents, and the goal of them is to get more rewards by collaborating with teammates to defeat all opponents. Agents can take actions to either move to or attack others on nearby grids. Ideally, the agents are able to learn skills such as chasing to hunt, escaping from enemies or working with teammates.

4.2. BASELINES:

We have compared our method to recently proposed state-of-art methods in the multi-agent learning field: (1)DDPG (Lillicrap et al., 2015) , ( 2)MADDPG (Lowe et al., 2017) , (3)MF-MARL (Yang et al., 2018) , ( 4)MAAC (Iqbal & Sha, 2018) (5)ATOC (Jiang & Lu, 2018) .

As mentioned in MAAC (Iqbal & Sha, 2018) , we do some modifications on some algorithms for experiments. Since deterministic policies are not possible, we use the Gumbel-Softmax reparametrization trick for learning in discrete action spaces for both MADDPG (Lowe et al., 2017) and DDPG(Lillicrap et al., 2015) . The modified versions are referred to as MADDPG (Discrete) and DDPG (Discrete).

For a detailed description of this reparametrization, we use a soft actor-critic method (Haarnoja et al., 2018) to optimize. We implement MADDPG with Soft Actor-Critic, named as MADDPG+SAC. Then the baselines are (1)DDPG (Discrete) (2)MADDPG (Discrete) (3)MADDPG+SAC (4)MF-MARL

(5)ATOC.

Hyperparameters are tuned based on performance and kept constant across all variants of critic architectures. All methods are re-implemented such that their approximate total number of parameters (across agents) is close to our approach. These models are trained with eight random seeds each. 

4.3. RESULTS AND DISCUSSION:

We first compare the average rewards attained by all approaches. We normalized by the range of awards achieved in an environment, as the number of agents changes. The proposed approach (SMAC) is competitive with other state-of-the-art approaches as shown in 4.3. In the Coin Game, most algorithms show a pleasing result while the MARL method shows less poorly performance.

MAAC is competitive with our approach in both the Coin Game and the CTC environment. On the other hand, DDPG(Discrete), MADDPG (Discrete), MADDPG+SAC and MARL don't perform well on CTC. We infer that due to the simplicity of action modes and the limited scale of agents, it's not hard for agents to learn tricks. Moreover, each agent's local observation provides enough information to make a decent prediction of its expected rewards.

However, agents within MAgent (Zheng et al., 2018) dynamics over time so that it's not capable for DDPG(Discrete), MADDPG (Discrete), MADDPG+SAC break down. Thus we compare our method to MF-MARL(mean field-MARL, Yang et al. (2018) , MAAC (Iqbal & Sha (2018) ) and ATOC (Jiang & Lu, 2018) . For all methods, rewards firstly are under zero, but along with the process of training, the reward gradually grows and finally stop in different levels. In this game, subgroups of agents are interacting and performing coordinated tasks with separate rewards while the components are Under review as a conference paper at ICLR 2020 changing over time. Thus it exemplifies why dynamic attention can be beneficial. MAAC (Iqbal & Sha (2018) and ATOC (Jiang & Lu, 2018 ) take more iterations to reach a stationary state.

Further, we explore the improvements with growing scale as shown in Table 1 . DDPG(Discrete)

and MADDPG(Discrete) could not handle a hige dimentional learning. MADDPG with SAC and MF-MARL(mean field-MARL, Yang et al. (2018) are barely satisfactory. But MAAC (Iqbal & Sha (2018) ), ATOC (Jiang & Lu, 2018) and SMAC(ours) steadily performs when the number of agents increases. In future research, we will continue to improve the scalability when the number of agents further increases by sharing policies among agents and performing attention on sub-groups (of agents).

We anticipate that in complicated scenarios, our method could work well.

5. CONCLUSIONS:

We propose an algorithm, the SMAC(Scholastic-Actor-Critic) for training decentralized policies in multi-agent settings. We design a more powerful critic, the headmaster critic to learn how to group agents and when to communicate besides conventional ones. We also adapt useful advantage functions that avoid converging to non-optimal deterministic policies. We analyze the performance of the proposed approach compared the state-of-the-art methods on the Coin Game, CTC (Lerer & Peysakhovich, 2017) , and MAgent (Zheng et al., 2018) , concerning the number of agents. Thanks to the flexible setting, our results are promising in dynamic occasions with small training expenses. We intend to explore more to highly complex and dynamic environments.

:



Figures and Tables:

Figure 1: The Coin Game and the Cooperative Treasure Collection Game

Figure 2: Results of our methods and others. In Coin Game(a) and CTC(b), methods involve DDPG(Discrete)4.2, MADDPG(Discrete)4.2, MAAC(Iqbal & Sha (2018)) , MF-MARL(Iqbal & Sha (2018)) and ATOC(Jiang & Lu, 2018). In MAgent(c)(Zheng et al., 2018), we compare our method toMF-MARLYang et al. (2018), MAACIqbal & Sha (2018)  and ATOC(Jiang & Lu, 2018).

The average rewards compared to other methods with growing of the scale in the convergent training stages.

Table content: <table><tr><td>Game</td><td colspan="6">Agents MADDPG+SAC MARL MAAC ATOC Ours(SMAC)</td></tr><tr><td/><td>8</td><td>-3.9</td><td>3.4</td><td>-4.7</td><td>3.1</td><td>2.8</td></tr><tr><td/><td>16</td><td>17.6</td><td>11.7</td><td>0.8</td><td>1.5</td><td>3.4</td></tr><tr><td>CTC</td><td>32</td><td>32.1</td><td>14.8</td><td>10.1</td><td>13.0</td><td>13.2</td></tr><tr><td/><td>64</td><td>41.2</td><td>18.9</td><td>23.3</td><td>24.2</td><td>24.5</td></tr><tr><td/><td>128</td><td>77.3</td><td>29.5</td><td>64.1</td><td>65.8</td><td>78.1</td></tr><tr><td/><td>8</td><td>-</td><td>3.4</td><td>4.9</td><td>-2.7</td><td>0.8</td></tr><tr><td/><td>16</td><td>-</td><td>14.7</td><td>27.9</td><td>26.5</td><td>27.0</td></tr><tr><td>MAgent</td><td>32</td><td>-</td><td>32.5</td><td>29.5</td><td>28.6</td><td>30.7</td></tr><tr><td/><td>64</td><td>-</td><td>34.8</td><td>35.4</td><td>39.1</td><td>41.5</td></tr><tr><td/><td>128</td><td>-</td><td>35.6</td><td>56.1</td><td>40.6</td><td>57.7</td></tr><tr><td colspan="7">*Note that the number of agents for each group in MAgent is half of the total. And all values are</td></tr><tr><td colspan="2">normalized into 0 to 100.</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
1. Summarize what the paper claims to do/contribute. Be positive and generous. The paper claims to propose a new semi-centralized method for optimizing multi-agent RL problems. It does this by creating random groupings of agents to pass messages between each other in a centralized critic fashion, similar to MADDPG. The method is interesting but I find the paper rather confusing. The method is not well described. While there is a lot of math in the paper it is rather common math that is not specific to the method until section 3.2.3. There are no details on how the method supports random groupings of agents in different amounts. Discussion on how important the random groupings off agents are should also be included. In the papers present state, I will have to vote for rejecting this paper. More detailed comments: - The abstract for the paper is rather confusing. There are a number of terms used that are not defined (headmaster, group, timing, etc). This makes it difficult to understand the proposed motivation and solution. - The use of terms and vernacular in the introduction is rather loose. If more of these terms are defined clearly and in order it would greatly help the reader - The claim that the method support “high dimension settings” is not well supported via experiments or design. Much more analysis related to this claim is necessary. - For equation 1. It seems j is used for indices where in the next you refer to i. - There is more detail than necessary in section 3.1. Most of this can be moved to the appendix. This space should be used to better explain, in detail, how the method functions. - How does the network model cope with variable sized random groups over time? Is there some kind of attention model or sequence model being used in the critic? - The tasks used in this work all seem to be new. Is there a reason they were all created and few already created environments were used for evaluation? - The description in the caption for Figure 1 is very sparse. What are the coloured blocks for int he Coin game? What do the disks of different sizes and colours indicate in the treasure collection game? - In Table 1 there does not appear to be any results for MADDPG on MAgent. Can these be computed and added? - The description of the results in Figure 2 is also very sparse. How many random seeds are these plots averaged over? Was a similar network structure used across each model? SMAC does not appear to significantly improve over prior methods. - I do not understand the claim that the dynamics over time for MAgent causes DDPG based methods to break down. Much more reasoning and experimentation are needed to show that DDPG-based methods truly have trouble in these environments.