Title: ON SOLVING COOPERATIVE DECENTRALIZED MARL PROBLEMS WITH SPARSE REINFORCEMENTS

Abstract: Decentralized decision makers learn to cooperate and make decisions in many domains including (but not limited to) search and rescue, drone delivery, box pushing and fire fighting problems. In these cooperative domains, a key challenge is one of sparse rewards, i.e., rewards/reinforcements are obtained only in a few situations (e.g., on extinguishing a fire, on moving a box) and in most other situations there is no reward/reinforcement. The problem of learning with sparse reinforcements is extremely challenging in cooperative Multi-Agent Reinforcement Learning (MARL) problems due to two reasons: (a) Compared to the single agent case, exploration is harder as multiple agents have to be coordinated to receive the reinforcements; and (b) Environment is not stationary as all the agents are learning at the same time (and therefore change policies) and therefore the limited (due to sparse rewards) good experiences can be quickly forgotten.
One approach that is scalable, decentralized and has shown great performance in general MARL problems is Neural Fictitious Self Play (NFSP). However, since NFSP averages best response policies, a good policy can be drowned in a deluge of bad best-response policies that come about due to sparse rewards. In this paper, we provide a mechanism for imitation of good experiences within NFSP that ensures good policies do not get overwhelmed by bad policies. We then provide an intuitive justification for why self imitation within NFSP can improve performance and how imitation does not impact the fictitious play aspect of NFSP. Finally, we provide a thorough comparison (experimental or descriptive) against relevant cooperative MARL algorithms to demonstrate the utility of our approach.

2. INTRODUCTION:

Cooperative Multi-Agent Reinforcement Learning (MARL) is an important framework for learning agent policies in multiple domains including but not limited to disaster rescue Nanjanath et al. (2010) ; Parker et al. (2016) , fire fighting Oliehoek et al. (2008) and box pushing Seuken & Zilberstein (2012) . In these problems, a team of agents (or robots) coordinate to accomplish tasks (find people, extinguish fires, and push boxes to destinations) in uncertain domains. There are multiple key challenges in these problems of interest: (a) Uncertainty in movement or in accomplishing tasks; (b) Coordination of decentralized entities to accomplish tasks (e.g., big fires require multiple fire engines or pushing a large box may require multiple robots; (c) Affected global state: Global state (representing status of tasks) can be impacted by agent actions; and most importantly (d) Sparse rewards: rewards are obtained by an agent only when tasks are accomplished and there are only a few tasks.

Due to its relevance in many team problems, research in cooperative MARL is extensive. There are multiple threads of relevant research in cooperative MARL. First, we have team learning approaches Haynes et al.; Haynes & Sen (1995) ; Sen & Sekaran (1995) ; Boutilier (1996) ; Claus & Boutilier (1998) where a single learner learns policies for a team of agents. Since there is a single learner, approaches from single agent learning can be employed for optimizing performance of the team. However, team learning approaches suffer from curse of dimensionality, where state and action space increases exponentially with number of agents. Furthermore, it may not be realistic to assume centralization of information, especially if the agents are decentralized.

The second thread of research has focussed on concurrent learning Agogino & Tumer (2006) ; Tampuu et al. (2017) , where agents learn concurrently to avoid the curse of dimensionality and central-ization of information. However, this is challenging as the RL problem faced by an individual agent is no longer stationary, especially as other agents can also change their policies.

In order to address the non-stationarity issue due to concurrent learning of multiple agents, a thread of research has focussed on methods with a centralized critic. One of the leading approaches in this space is called COMA Foerster et al. (2018) that employs an actor critic model with a centralized critic (which takes state, action information from all agents) and decentralized actors that are trained independently using local information of individual agents. Another leading approach is by Nguyen et al. (2017) to solve cooperative problems with large numbers of homogenous agents and anonymous interactions. However, it relies on having non-global states and transition function decomposability given number of agents. This is not feasible in domains of interest in this paper and since it is based on actor critic architecture, it will have same issues as other MARL approaches with sparse rewards.

The last thread of relevant research has employed game theory to develop decentralized learning methods Hu & Wellman (2003) ; Heinrich et al. (2015) ; Heinrich & Silver (2016) . One of the leading approaches is the neural fictitious self play method Heinrich & Silver (2016) , which employs ideas from the well known fictitious play Brown (1951) method. Given the focus on equilibrium for game theoretic methods, these approaches can get stuck in bad local optima in the case of cooperative problems. The key advantage of these approaches, specifically NFSP is decentralized learning at scale.

Even though the research in cooperative MARL is extensive, existing work is unable to provide good policies (as demonstrated in experimental results) in the presence of sparse rewards. The issue of sparse rewards is also present in single agent RL Oh et al. (2018) , however, the problem is exacerbated in multi-agent problems due to two reasons: (1) Exploration is harder as multiple agents have to be coordinated to receive the rewards; and (b) Environment is not stationary since multiple agents are learning together. Due to difficulty in exploration finding good policies is difficult and non-stationarity can make the algorithms forget good policies.

Since NFSP is adept at handling non-stationarity, we provide a new approach called Neural Fictitious Self Imitation and Play (NFSIP), that extends on NFSP in two major ways to handle sparse rewards: (a) We incorporate self imitation into NFSP, so as to replay past good experiences and ensure effective exploration; (b) All agents employ an average best response policy to deal with non-stationarity in NFSP. However, with sparse rewards, number of good policies are very few and averaging can make a good policy irrelevant. We provide supervised reinforcement based policy averaging to ensure good policies remain relevant.

We demonstrate that our approach is able to get significant improvement in performance over leading MARL approaches on three different problem domains from literature.

3. BACKGROUND: NEURAL FICTITIOUS SELF PLAY (NFSP):

In Fictitious play (FP), a popular game-theoretic model of learning, agents repeatedly play a game, choosing the best response against average strategies of their opponents at each iteration. The average strategies converge to a Nash equilibrium for zero-sum games, potential games and identical interest games (i.e., cooperative multi-agent problems). FP is a theory on a normal-form representation, where each agent acts only once per one game, which is not suited to real problems at scale.

To overcome the scalability issue, Heinrich et al. (2015) ; Heinrich & Silver (2016) proposed an appropriately approximated (hence scalable to large-scale games) method for FP referred to as Neural Fictitious Self Play (NFSP). As with FP, agents in NFSP repeatedly play a game, storing their experiences in memory. Instead of computing the full-width best response strategy (i.e., compute best response by playing the entire game), they learn an approximate best response using Deep Q-Networks (DQN) Mnih et al. (2015) . And instead of averaging their full-width strategies, they learn an approximate average strategy by using supervised learning (SL). Heinrich & Silver (2016) on deep neural networks.

Deep Q network with parameters θ Q is trained using the following loss function: 

L(θ Q ) = E (s,a,r,s )∼M RL r + max a Q(s , a |θ Q ) -Q(s, a|θ Q )

L(θ π ) = E (s,a)∼M SL -log(Π(s, a|θ Π )

where M RL and M SL refer to the stored Reinforcement Learning and Supervised Learning experiences respectively.

3.1. IMITATION LEARNING:

Imitation learning (IL) enables a learner to imitate expert behavior given expert demonstrations. A wide variety of IL methods have been proposed in the last few decades. The simplest IL method among those is Behavioral Cloning (BC) Pomerleau (1991) which learns an expert policy in a supervised fashion without environment interactions during training. BC can be the first IL option to consider when enough demonstrations are available. Since it is often hard to obtain a large number of demonstrations in real-world environments, BC is often not the best choice for real-world IL scenarios. IL requires experts to generate the expert demonstrations, which may not be feasible in large scale problems. Oh et al. (2018) provided a Self Imitation Learning (SIL) approach where (good) experiences generated during exploration are stored in a prioritized buffer based on cumulative reward achieved.

During training it samples the experiences from this buffer and trains the neural networks only if the current Q/Value network is predicting a lower value for these experiences. This ensures that we only utilize good experiences in places where there is scope for improvement. It does so by computing the following value for experiences:

(max(0, R(s, a) -V (s)))

where R(s, a) = cumulative reward, is sum of immediate rewards from that state,action till end of episode and V(s) is state based baseline value.

4. NEURAL FICTITIOUS SELF IMITATION PLAY, NFSIP:

In this section, we describe our main algorithm, NFSIP for learning in the presence of sparse reinforcements. Algorithm 1 provides the pseudo code and Figure 1 ) provides the flow and dependencies. For each agent, in NFSIP and NFSP, we update the average policy network and Q-network parameters based on all the experiences. Since there are sparse reinforcements, it is imperative that updates from "good" experiences (i.e., ones that improve social welfare) are not overwritten by "bad" experiences. Therefore, in NFSIP, we have a separate self imitation loop at the end of each episode to not forget the learning from "good" experiences. In this self imitation loop, we update both the average policy and Q-network parameters based on difference in the reward obtained from the episode and the current value function estimate.

All agents in NFSIP also learn based on experiences generated from simultaneous play with other agents. An NFSIP agent interacts with its fellow agents and memorizes its experience of state transitions and its own best response behaviour in three memories, M RL , M SL and M SI . NFSIP treats these memories as three distinct datasets suitable for deep reinforcement learning, supervised policy learning and self imitation respectively.

The NFSIP agent trains a neural network (Q), to predict action values from data in M RL and M SI using off-policy reinforcement learning. The resulting network defines the agents' approximate best response strategy, b (Q), which selects a random action with probability and otherwise chooses the action that maximizes the predicted action values. The agent trains a separate neural network (Π), to imitate its own past best response behaviour using supervised classification on the data in M SL and M SI . This network maps states to action probabilities and defines the agent's average strategy while appropriately taking into account of good experiences stored in M SI . During execution, the agent chooses its actions from a mixture of its two strategies, b (Q) and Π.

In lines 4-11 of algorithm 1, each agent executes actions, stores the experiences in M RL and also in M SL , and uses the stored experiences to train the Q-network (action-value network) and policy networks. Once episode ends, in lines 12-17, we update the self imitation buffer, M SI with experiences if social welfare (welfare of the entire system, including all agents) is higher than the set threshold for social welfare (best reward achieved so far). These experiences are updated to include cumulative rewards. In lines 18-24, Q and Π networks are trained with experiences from self imitation buffer, M SI if Q-network is predicting a lower value for these experiences as compared to their actual (cumulative) reward.

We now provide two key insights employed in our algorithm to ensure improved performance.

4.1. WEIGHTED GENERALIZED WEAKENED FICTITIOUS PLAY:

Leslie & Collins (2006) have defined a generalization of fictitious play for approximate best responses as follows:

π t+1 ∈ (1 -α t+1 )π t + α t+1 • b t (Q t )

where

α t → 0, t → 0, ||Q t -R(π t )|| → 0 as t → ∞

NFSP employs maximum log likelihood (using Loss as negative log likelihood) for learning the above mixture of past policy, π t and current approximate best response policy, b t (Q t ) based on the observed samples (i.e., best response actions taken at each iteration). The standard maximum likelihood principle implicitly places equal weight on each of the observations in the sample, but depending on the extent to which the model and the true data generating process deviate this can be improved upon. Taking the example of coin toss, if after 1000 iterations, if we observed 700 heads and 300 tails, maximum likelihood will predict a biased coin with 0.7 and 0.3 probability. However, this is incorrect as the sampled data was biased. This issue happens frequently in sparse reinforcement setting as sparse but good experiences come by rarely. So, samples data is bound to have rare occurrences of them, causing maximum likelihood (for average policy network) to result in bad local optima.

One of the ways to improve the model is to use weighted maximum likelihood (such methods has been employed in many domain such as risk management in Finance Steude (2011) , image denoising for image processing Deledalle et al. (2009) ). Steude (2011) to minimize the risk, down weighted the observations that bear a high probability of being destructive outliers. they show that it can considerably improve the forecast accuracy for a variety of data sets and different time series models can be realized. Deledalle et al. (2009) derived the weights in a data driven manner. The weights are iteratively refined based on both the similarity between noisy patches and the similarity of patches extracted from the previous estimate.

For solving MARL with sparse reward setting, we build on similar ideas. Specifically, we increase weight for better experiences in both policy and Q-networks. These weights are dynamically up-dated based on the current state of learning. Since we only want to increase the weight of good experiences, we will not have negative weight in the process. For average policy network, we employ the following additional loss based on experiences in self imitation memory:

E (s,a,R)∼M SI -log(Π(s, a)) • [R(s, a) -V (s)] + where [R(s, a) -V (s)] + = max(0, R(s, a) -V (s))

On similar lines, we also add an additional weight to the Q-network loss based on self imitation memory r(s, a)

+ γ max a Q (s , a ) -Q(s, a) 2 + α • [R(s, a) -V (s)] + 2 4.2 SELF IMITATION LEARNING FOR COOPERATIVE MULTIPLE AGENT PROBLEMS

Self imitation learning in single agent case imitates past "good" experiences and prioritizes learning with those "good" experiences. However, in multi-agent problems, due to simultaneous learning of agents, past good experience for an agent may not be a "good" experience if other agents have changed their policy. More importantly, in a cooperative setting, individual good experiences may not be maximizing social welfare. So we make following changes:

• We judge the goodness of any experience not just based on its own reward but also based on social welfare. We only store experiences for self imitation if social welfare is above a certain threshold value. We start with a very low threshold value and gradually increase it as we explore better experiences (providing higher social welfare). • Presence of multiple learning agents makes the environment non stationary and therefore in order to avoid utilizing old experiences (that may not be valid any more), we periodically remove expert data (self) generated for self imitation process. We do so when we encounter a better social welfare solution and adjust the threshold value accordingly. This will ensure that there always expert experiences to train with that are not too old and provide higher social welfare. • We train only with those experiences where neural network is predicting a lower value than the actual value (cumulative reward) obtained by the agent. Therefore, the max operator is given by: In this section, we provide a discussion on key challenges that exist typically in cooperative MARL problems and how NFSIP addresses these challenges.

First, we discuss about a problem faced by many centralized learners Sen & Sekaran (1995) ; Boutilier (1996) for every time step do 6:

Simulate agents for 1 step 7:

Store experiences in M RL 8:

Store experiences in M SL if agent took best response action (b (Q))

9:

for all agents do 10:

Sample from M RL , train action-value network:

L(θ Q ) = E (s,a,r,s ) r + max a Q(s , a |θ Q ) -Q(s, a|θ Q ) 2 11:

Sample from M SL , train policy network: L(θ π ) = E (s,a) -log(Π(s, a|θ Π )

12:

if Episode reward > best reward achieve so far then 13:

Reset prioritized experience buffer 14:

best reward achieve so far = Episode reward 15:

if Episode reward >= best reward achieve so far then 16:

Compute cumulative reward, R 17:

Store experiences in prioritized experience buffer prioritized on R 18:

for some iteration do for all agents do 20:

Sample from prioritized replay buffer 21:

Train action-value network:

L(θ Q ) = E (s,a,R) ([R(s, a) -V (s|θ Q , θ Π )] + ) 2 22:

Train policy network:

L(θ π ) = E (s,a,R) -log(Π(s, a|θ Π )) • [R(s, a) -V (s|θ Q , θ Π )] + )

23:

[R(s, a) -V (s)] + = max 0, R(s, a) -V (s)

24:

V (s) = a π(s, a) • Q(s, a)

25:

Update target action-value network periodically Second, we consider the credit assignment problem. Since agents receive reward as a team, a key challenge while learning is understanding how much each agent contributed to receiving the reward.

A leading approach Foerster et al. (2018) , employs marginal utilities, i.e., difference in reward with the agent included and reward without the agent included. However, in problems of interest in this paper, agents have to coordinate to complete tasks (i.e, extinguishing a fire, pushing a box). That is to say, if n agents are required to accomplish a task, then n -1 agents will not be able to complete the task. So, marginal utility for every agent will be equal to the total reward to be received by the entire team of n agents. Since that would be inaccurate, we do not go for marginal utility based credit assignment. Instead, we employ the reward strategy described by Panait et al. Panait & Luke (2005) , where rewards are divided equally among all agents.

Third, we consider the non-stationarity introduced due to multiple agents learning at the same time.

We employ the NFSP type of policy averaging and short experience buffers to reason with nonstationarity.

Finally, the issue of sparse reward has not received much attention in MARL literature, even though it has been studied extensively in single agent literature Oh et al. (2018) ; Zhu et al. (2018) ; Večerík et al. (2017) ; Hester et al. (2018) . Through a synergistic combination of Neural Fictitious Self Play (NFSP) and Self Imitation Learning (SIL)1 , NFSIP is able to provide significant improvements on complex domains with sparse reinforcements. We now provide more details on the specific problem domains:

Box pushing problem Seuken & Zilberstein (2012) : Multiple agents need to coordinate and push boxes of different sizes to their goal locations in a grid world. Each agent has 6 possible actions to take: {move left, move right, move up, move down, act on the task, stay}. To successfully push a box, certain number of agents need to push the box simultaneously. For this domain, we created simpler instances with smaller grid sizes as benchmark algorithms were unable to learn at all on larger problem instances. We considered a 4x4 grid with 5-agents in box pushing. There are 4 boxes. We created different versions of this problem by changing the number of agents required to push the boxes: (V1) Any single agent can push the box; and (V2): To push any box at least 2 agents need to cooperate and simultaneously act on it. Firefighting problem Oliehoek et al. (2008) : In this problem setting we have a 6x6 grid with 10 agents (fire trucks), fires are spread over different locations. Fire trucks need to act on fires to put them out, number of trucks needed to put out the fire depends on its intensity (low/high).

We created different versions of the problem as follows: (V1): 2 agents can put out the fire with probability 0.9, more than 2 agents can put out the fire with probability 1; and (V2): Intensity of fire will increase from low to high with probability 0.2 at every time step. Low intensity fire: "2

:

NFSP handles non-stationarity to ensure SIL is able to learn from the right experiences. SIL ensures good experiences are not forgotten so that NFSP can move to higher quality equilibria.

Figures and Tables:

Figure 1: NFSIP

Figure 2: Credit assignment

Figure 3: Box pushing v1, v2 and Fire Fighting v1

Neural Fictitious Self Imitation and Play, NFSIP 1: Initialize policy network(θ Π ), action-value network(θ Q ) and target action-value network(θ Q ) networks 2: best reward achieve so far = -∞ 3: while Not Converged do

Table content: <table><tr><td>Algorithm 1: 4: policy =</td><td>b (Q) with probability η Π with probability 1 -η</td></tr><tr><td>5:</td><td/></tr><tr><td/><td>; Claus &amp;</td></tr><tr><td colspan="2">Boutilier (1998); Lowe et al. (2017); Foerster et al. (2018), i.e.,</td></tr><tr><td colspan="2">curse of dimensionality. As the size of state and action spaces</td></tr><tr><td colspan="2">grows exponentially with number of agents, centralized learn-</td></tr><tr><td colspan="2">ers can face severe scalability issues. Since NFSIP (like NFSP)</td></tr><tr><td colspan="2">is a decentralized method, the curse of dimensionality does not</td></tr><tr><td colspan="2">pose a challenge as each learning agent can run on a different</td></tr><tr><td colspan="2">computing thread. Another approach that has been employed</td></tr><tr><td colspan="2">for addressing curse of dimensionality is by exploiting homo-</td></tr><tr><td colspan="2">geneity and anonymity in agent models Nguyen et al. (2017).</td></tr><tr><td colspan="2">However, in problems of interest in this paper, due to the pres-</td></tr><tr><td colspan="2">ence of a global state (task states) that is affected by individ-</td></tr><tr><td colspan="2">ual agent actions, the method employed to generate counts of</td></tr><tr><td colspan="2">agents becomes inapplicable.</td></tr></table>

Peer review (iclr2020):
In this paper, the authors propose a technique NFSIP to augment state-of-the-art Neural Fictitious Self Play (NFSP) with self-imitation learning, and show that this approach can achieve performance improvement compared to other Multi-agent RL baselines on 3 different problem domains in literature. The key idea of this paper is applying the self-imitation loop at the end of each episode s.t. the agent will not forget learning from good experience. The idea is simple, but the experimental results show that for the tasks (e.g. V2) that require collaborations from multiple agents, the proposed approach outperforms other baselines including NFSP on both firefighting and search & rescue domains. Questions: 1. it seems that for simpler task V1, the result of NFSIP are very close to NFSP in Fig 3, 4. How to explain this phenomenon? 2. why there are some baselines not having the same number of iterations in Fig 3, 4? e.g. COMA_SIL in Firefighting v2 seem only have results until 70k iterations. Also, for the task Box Pushing, NFSIP doesn*t seem to have advantages?