## Health-Informed Policy Gradients for Multi-Agent Reinforcement Learning

Ross E. Allen MIT Lincoln Laboratory Lexington, Massachusetts ross.allen@ll.mit.edu

Jayesh K. Gupta Computer Science Stanford University jkg@cs.stanford.edu

Jaime Pena MIT Lincoln Laboratory Lexington, Massachusetts jdpena@ll.mit.edu

Yutai Zhou MIT Lincoln Laboratory Lexington, Massachusetts yutai.zhou@ll.mit.edu

Javona White Bear MIT Lincoln Laboratory Lexington, Massachusetts jwbear@ll.mit.edu

## ABSTRACT

This paper proposes a definition of system health in the context of multiple agents optimizing a joint reward function. We use this definition as a credit assignment term in a policy gradient algorithm to distinguish the contributions of individual agents to the global reward. The health-informed credit assignment is then extended to a multi-agent variant of the proximal policy optimization algorithm and demonstrated on particle and multiwalker robot environments that have characteristics such as system health, risk-taking, semiexpendable agents, continuous action spaces, and partial observability. We show significant improvement in learning performance compared to policy gradient methods that do not perform multiagent credit assignment 1 .

Mykel J. Kochenderfer Aeronautics &amp; Astronautics Stanford University mykel@stanford.edu and control policies is still challenging. Decision-making in multiagent systems can be modeled as a decentralized partially observable Markov decision process (Dec-POMDP) [15]. In general, computing an optimal policy is NEXP-complete [3]. While various solution techniques based on heuristic search [22, 30, 33] and dynamic programming [1, 4, 10] exist, they tend to quickly become intractable as the number of agents, states, and actions increase.

## KEYWORDS

Multi-Agent Reinforcement Learning (MARL), Continuous Control, Multi-Robot Systems, Risk-Taking

## 1 INTRODUCTION

Autonomous robotic systems are commonly employed for tasks described as dull, dirty, and dangerous. Multi-robot systems are particularly well suited for dirty and dangerous tasks as they are robust to single-agent degradation and failures. Such degradation can arise from damage to an agent's sensors or actuators, thus limiting the agent's ability to observe the environment and constricting the actions it may take. We will use the term system health to refer to an agent's current state of degradation relative to its nominal capabilities.

While multi-agent systems may be an attractive solution for a range of real-world tasks, developing distributed decision-making

1 DISTRIBUTION STATEMENT A. Approved for public release. Distribution is unlimited.

This material is based upon work supported by the Under Secretary of Defense for Research and Engineering under Air Force Contract No. FA8702-15-D-0001. Any opinions, findings, conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Under Secretary of Defense for Research and Engineering.

©2020 Massachusetts Institute of Technology.

Delivered to the U.S. Government with Unlimited Rights, as defined in DFARS Part 252.227-7013 or 7014 (Feb 2014). Notwithstanding any copyright notice, U.S. Government rights in this work are defined by DFARS 252.227-7013 or DFARS 252.2277014 as detailed above. Use of this work other than as specifically authorized by the U.S. Government may violate any copyrights that exist in this work.

One approach to approximate solutions to such problems is to use deep reinforcement learning (deep-RL) [7, 9, 18, 24, 37]. However, a fundamental challenge is the multi-agent credit assignment problem . When there are multiple agents acting simultaneously toward a shared objective, it is often unclear how to determine which actions of which agents are responsible for the joint reward. There may be strong inter-dependencies between the actions of different agents and long delays between joint actions and their eventual rewards [39].

This work fuses the concept of system health with deep reinforcement learning and provides three contributions to the field of multi-agent decision-making. First, we outline a definition and properties for the concept of system health in the context of Markov decision processes. These definitions provide the framework for a subset of Dec-POMDPs that can be used to analyze multi-agent systems operating in hazardous and adversarial environments. Second, we use the definition of health to formulate a multi-agent credit assignment algorithm to be used to accelerate and improve multiagent reinforcement learning. Third, we apply the health-informed crediting algorithm within a multi-agent variant of proximal policy optimization (PPO) [29] and demonstrate significant learning improvements compared to existing algorithms in simulated environments involving legged and particle robots with continuous action spaces.

## 2 RELATED WORK

Applying deep-RL to multi-agent decision-making is an active area of research. Hernandez-Leal, Kartal, and Taylor [12] provide a comprehensive survey of the field. Gupta et al. [9] demonstrated how algorithms such as TRPO, DQN, DDPG, and A3C can be extended to a range of cooperative multi-agent problems. Lowe et al. [18] developed multi-agent deep deterministic policy gradients (MADDPG) that was capable of training in cooperative and competitive environments.

Multi-agent reinforcement learning is challenging due to the problems of non-stationarity and multi-agent credit assignment . The non-stationary problem arises when a learning agent assumes all other learning agents are part of the environment dynamics. Since the individual agents are continuously changing their policies, the environment dynamics from the perspective of any one agent are continuously changing, thus breaking the Markov property [11]. While Lowe et al. [18] attempt to address the non-stationary problem, MADDPG is still shown to become ineffective at learning for systems with more than three or four agents.

Gupta et al. [9] partially address the non-stationary problem through parameter sharing whereby groups of homogeneous agents use identical copies of parameters for their local policies. Terry et al. [35] provide a theoretical analysis of how information centralization offered by parameter sharing alleviates some of the nonstationarity problem. However, parameter sharing techniques don't resolve the second fundamental challenge of multi-agent learning: multi-agent credit assignment-i.e. the challenge of identifying which actions from which agent at which time were most responsible for the overall performance (i.e. returns) of the system. Gupta et al. avoid explicit treatment of this problem by focusing on environments where the joint rewards can be decomposed into local rewards. However, in general, such local reward structures are not guaranteed to optimize joint returns [39].

Wolpert and Tumer [39] developed the Wonderful Life Utility (WLU) and Aristocrat Utility (AU), which are forms of 'difference rewards'. Both WLU and AU attempt to assign credit to individual agents' actions by taking the difference of utility received versus utility that would have been received had a different action been taken by the agent. The comparison between actual returns and hypothetical returns is sometimes referred to as counterfactual learning [7]. Predating most of the advancements in deep reinforcement learning, Wolpert and Tumer's work was restricted to small decision problems that could be handled in a tabular fashion [36, 39].

Foerster et al. [7] formulated an aristocrat-like crediting method that was able to leverage a deep neural network state-action value function (Q-value) within a policy gradient algorithm, referred to as counterfactual multi-agent (COMA) policy gradients. Using deep neural networks, they enabled crediting in large or continuous state spaces. Subsequent work on the multi-agent credit assignment led to the QMIX and Maven algorithms which factorized the Q-value across agents and demonstrated improved performance over COMA [19, 25]. However COMA, QMIX, and Maven required enumeration over all actions and were thus restricted to problems with discrete action spaces.

Others have posed multi-agent, health-aware decision problems similar to the one we give in Section 3 [21, 23]. These prior works use a planning-based approach which assumes detailed, a priori knowledge of the underlying Dec-POMDP's dynamics. This is fundamentally different from the learning-based approach we present in Section 4.

## 3 PROBLEM STATEMENT

The problems presented in this work can be modeled as decentralized partially observable Markov decision processes (Dec-POMDPs), which are defined by the tuple (I S A , , 𝑖 , Z 𝑖 , 𝑇 , 𝑅 ) . The set I represents a finite set of 𝑛 agents. The set S is the joint state space of all agents (finite or infinite). Assuming states are described in a vector form, let s ∈ S ⊆ R 𝑚 be a specific state of the system. The set A ( ) 𝑖 s is the action space of the 𝑖 th agent in joint state s . The vector u 𝑡 = GLYPH&lt;0&gt; 𝑎 1 ,𝑡 , 𝑎 2 ,𝑡 , . . . , 𝑎 𝑛,𝑡 GLYPH&lt;1&gt; represents a joint action at time 𝑡 where 𝑎 𝑖,𝑡 ∈ A ( 𝑖 s 𝑡 ) . The set Z ( ) 𝑖 s is the set of observations for the 𝑖 th agent in joint state s . The vector o 𝑡 = GLYPH&lt;0&gt; 𝑧 1 ,𝑡 , 𝑧 2 ,𝑡 , . . . , 𝑧 𝑛,𝑡 GLYPH&lt;1&gt; represents a joint observation at time 𝑡 where 𝑧 𝑖,𝑡 ∈ Z ( 𝑖 s 𝑡 ) . The transition function 𝑇 ( s ′ | s u , ) is the probability density associated with arriving in state s ′ given the joint action u was taken in state s . The reward function 𝑅 ( s u , ) gives the immediate reward for taking the joint action u while in state s . The vector 𝜏 𝑖,𝑡 = GLYPH&lt;0&gt; 𝑧 𝑖, 1 , 𝑎 𝑖, 1 , 𝑧 𝑖, 2 , 𝑎 𝑖, 2 , . . . , 𝑧 𝑖,𝑡 GLYPH&lt;1&gt; represents the observation-action history for agent 𝑖 up to time 𝑡 . Using notation similar to Foerster et al. [7], we represent group-wide joint variables in bold and joint quantities that exclude a particular agent with the term ¬ 𝑖 .

In order to solve the Dec-POMDP we seek a joint policy π θ ( u | s ) , composed of a set of local policies 𝜋 𝜃 𝑖 ( 𝑎 𝑖 | 𝜏 𝑖 ) , that maximizes the discounted joint returns 𝐺 𝑡 = ˝ 𝑡 𝑓 -𝑡 𝑙 = 0 𝛾 𝑟 𝑙 𝑡 + 𝑙 , where 𝛾 is the discount factor, 𝑟 is the empirical joint reward, and 𝑡 𝑓 is the final time step in an episode or receding horizon. The local policies, parameterized by 𝜃 𝑖 , map an agent's observation-action history to its next action at each time step. For a group of 𝑛 agents that follow independent stochastic policies 2 [7], we have

$$\pi \left ( \mathbf u \, | \, \mathbf s, \theta \right ) = \prod _ { i = 1 } ^ { n } \pi _ { i } \left ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } \right ). \quad \quad \left ( 1 \right )$$

Using the common definition of the state value function of policy π , we define 𝑉 π ( s 𝑡 ) = E s 𝑡 + 1: 𝑡 𝑓 , u 𝑡 𝑡 𝑓 : [ 𝐺 𝑡 ] [28]. Similarly, we define the joint state-action value function as 𝑄 π ( s 𝑡 , u 𝑡 ) = E s 𝑡 + 1: 𝑡 𝑓 , u 𝑡 + 1: 𝑡 𝑓 [ 𝐺 𝑡 ] .

## 3.1 System Health

Here we introduce a concept we refer to simply as system health , though there are alternative definitions used in the field of prognostic decision making (PDM) [2, 26]. If we represent the current state of the system with vector s , then the system health, h ∈ R 𝑛 , constitutes a subvector of s . Without loss of generality, we can define the state vector as s = ( h p , ) , where p is the non-health components of the state. Each element of the the health vector corresponds to the health of an individual agent and is in the interval [ 0 1 , where 1 , ] represents full health and 0 represents a fully degraded agent. We define the following properties associated with reduction of system health:

Property 1. Non-recoverable minimum health. Let s ℎ 𝑖 = 𝑐 represent any state vector where the health of agent 𝑖 is given as 𝑐 ∈ [ 0 1 . , ] We define the non-increasing nature of the health once minimum health has been reached (i.e. agent death) as follows

$$T \left ( s _ { h _ { i } = \beta } ^ { \prime } \, | \, s _ { h _ { i } = 0 }, \mathbf u \right ) = 0 \text{ for } \beta > 0 \text{ \quad \ \ } ( 2 )$$

Property 2. Constriction of reachable set in state space. Define the reachable set of joint state s and constriction of reachable set as

2 Independent policies implies that agent 𝑖 's action at time 𝑡 is not conditioned on the actions of any other agent at time 𝑡 . Note that, in the case of parameter sharing where all agents have identical copies of parameters, 𝜃 𝑖 = 𝜃 , the local policies can still be independent.

follows

$$\text{Let} \colon \mathcal { R } ( s ) = \{ s ^ { \prime } \in \mathcal { S } \ | \ \exists \, \mathfrak { u } \, \colon T \left ( s ^ { \prime } \ | \ s, \mathfrak { u } \right ) > 0 \} \\ \therefore \, \, \mathcal { R } ( s _ { h _ { i } = \beta } ) \subseteq \mathcal { R } ( s _ { h _ { i } = \alpha } ) \ \text{for} \, \alpha > \beta \quad \begin{pmatrix} 3 & \text{To} \, \cdot \\ \text{sys} \end{pmatrix}$$

Property 3. Constriction of available actions in action space. Let A ( ) 𝑖 s ⊆ A 𝑖 represent the available action set for agent 𝑖 when the system is in state s . Therefore the constriction of the available action set can be described as

$$\mathcal { A } _ { i } ( s _ { h _ { i } = \beta } ) \subseteq \mathcal { A } _ { i } ( s _ { h _ { i } = \alpha } ) \text{ for } \alpha > \beta \text{ \quad \ \ } ( 4 ) \text{ \quad jec }$$

Property 4. Constriction of observable set in observation space. Let Z ( ) ⊆ Z 𝑖 s 𝑖 represent the set of possible observations for agent 𝑖 when the system is in state s . Therefore the constriction of observable set can be described as:

$$\mathcal { Z } _ { i } ( s _ { h _ { i } = \beta } ) \subseteq \mathcal { Z } _ { i } ( s _ { h _ { i } = \alpha } ) \text{ for } \alpha > \beta \text{ \quad \ \ } ( 5 ) \text{ \quad } \text{ a } \text{ }$$

To provide real-world intuition about system health, we can consider multi-agent systems composed of physical robots. In such a case, system health can be thought of the state of damage or degradation of a physical robot. A health of zero implies a robot has completely 'crashed' or been otherwise terminated and Property 1 asserts that the robot will not become operational again. Properties 2 and 3 describe the effect of damaging a robot's actuators, thus partially or completely 'crippling' its motion. Property 4 describes the effect of damaging a robot's sensors, thus limiting the observations it can make of the world.

In this paper, we pay particular attention to the case of binary health states , i.e. ℎ 𝑖 ∈ { 0 1 , } , where zero health represents a complete constriction of an agent's action space. In this case, agents are either fully functional or completely non-operational, where nonoperational agents are incapable of selecting actions to interact with the environment. This is a natural formulation for many multiagent problems, such as multi-agent computer games, where agents maintain their full functionality up until the moment they are nonoperational.

## 4 APPROACH

This section proposes a counterfactual learning algorithm that seeks to address the multi-agent credit assignment problem for systems that embody the characteristics of system health. We choose to restrict our scope to policy gradient methods because of their scalability to large and continuous state and action spaces [6]. We develop a health-informed policy gradient in Section 4.1 and use it to propose a new multi-agent PPO variant in Section 4.2.

In general, each agent may be learning its own individual policy 𝜋 𝜃 𝑖 , however this can lead to a non-stationary environment from the perspective of any one agent and confound the learning process [11]. Instead, for this paper, we assume that agents are executing identical copies of the same policy 𝜋 𝜃 in a decentralized fashion, referred to as parameter sharing [9, 13, 35]. We adopt a centralized learning, decentralized execution architecture whereby training data can be centralized between training episodes even if no such centralization of information is possible during execution-a common approach in the multi-agent RL literature [7, 9, 18].

## 4.1 Health-Informed Multi-Agent Policy Gradients

To develop a policy gradient approach for health-based multi-agent systems, we begin with the policy gradient theorem [31]

$$\nabla J ( \theta ) \, \infty \, \sum _ { s } \mu ( s ) \sum _ { u } q _ { \pi } \, ( s, u ) \, \nabla \pi \, ( u \, | \, s, \theta ) \, \quad \, ( 6 )$$

Equation 6 gives an analytical expression for the gradient of the objective function with respect to policy parameters θ , where 𝑞 π ( s u , ) is the true state-action value and 𝜇 ( s ) refers to the ergodic state distribution. To develop a practical algorithm, we need a method for sampling such an analytical expression that has an expected value equal or approximately equal to Equation 6. Eq. (7) gives a multi-agent form for sampling the policy gradient considering local policies 𝜋 𝜃 𝑖 that map an individual agent's local trajectory 𝜏 𝑖,𝑡 to actions 𝑎 𝑖,𝑡 :

$$g _ { \Psi } = \mathbb { E } _ { \pi } \left [ \sum _ { i = 1 } ^ { n } \Psi _ { i, t } \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \, | \, \tau _ { i, t }, \theta _ { i } ) \right ] \quad \quad ( 7 )$$

where the term Ψ can be formulated to affect the bias and variance of the learning process; see Appendix A for derivation [7, 28]. Typically Ψ takes the form of the return or discounted return 𝐺 𝑡 (i.e. REINFORCE algorithm [38]); the returns baselined on the state value function 𝑉 π ( s 𝑡 ) (i.e. REINFORCE with baseline [32]); the state-action value function 𝑄 π ( s 𝑡 , u 𝑡 ) ; the advantage function 𝐴 π ( s 𝑡 , u 𝑡 ) = 𝑄 π ( s 𝑡 , u 𝑡 ) -𝑉 π ( s 𝑡 ) ; or the generalized advantage function 𝐴 GAE [28, 29]. π

If all agents have the same policy parameters, receive identical rewards throughout an episode, and employ the same Ψ function, then Equation 7 renders the same gradient at each time step for all agents' actions. This uniformity in policy gradients is problematic because it results in all actions at a given time step being promoted equally during the next training cycle-i.e. the multi-agent credit assignment problem.

To overcome this problem, we use the term Ψ 𝑖,𝑡 to distinguish gradients between different agents' actions at the same time step. One option is to set Ψ 𝑖,𝑡 = 𝑄 𝜋 GLYPH&lt;0&gt; 𝜏 𝑖,𝑡 , 𝑎 𝑖,𝑡 GLYPH&lt;1&gt; , which defines an observationaction function referred to as a local critic . Since all agents are expected to receive distinct observations at each time step, 𝑄 𝜋 GLYPH&lt;0&gt; 𝜏 𝑖,𝑡 , 𝑎 𝑖,𝑡 GLYPH&lt;1&gt; is expected to be distinct for each agent at a given time step. However, this approach relies on making value approximations based on limited information, which can significantly impact learning, as we demonstrate in Section 5. If we instead leverage our prior assumption of centralized learning [7, 9, 18], then we can make direct use of the central value functions, 𝑉 π ( s 𝑡 ) and 𝑄 π ( s 𝑡 , u 𝑡 ) ; however, this still does not resolve the multi-agent credit assignment problem.

We can use the concept of system health in an attempt to address the credit assignment problem. Our technique stems from the concepts of counterfactual baselines [7] or difference rewards [20], and is further motivated by the Wonderful Life Utility (WLU) [39]. The idea is that credit is assigned to an agent at a given time step by comparing the true joint return from time 𝑡 , with the expected return from a hypothetical or 'counterfactual' scenario where agent 𝑖

had been terminated at time 𝑡 . We propose the following minimumhealth baseline for multi-agent credit assignment

$$\Psi _ { i, t } & = h _ { i, t } \left ( G _ { t } - V _ { \pi } \left ( s _ { t } ^ { - h _ { i, t } }, h _ { i, \min } \right ) \right ) \\ & = h _ { i, t } G _ { t } - b \left ( s ^ { - i } \right )$$

where ℎ 𝑖,𝑡 is the health of agent 𝑖 at time 𝑡 and s ¬ ℎ 𝑖,𝑡 𝑡 represents the true joint state of the system at time 𝑡 , except that the health of agent 𝑖 is replaced with minimum health (typically 0).

To understand the multiplication by the true health ℎ 𝑖,𝑡 in Equation 8, consider the implications of Properties 2 and 3 in Section 3.1. If reduction in system health constricts the available actions and reachable states at a given state, and these constrictions are not encoded within the policy 𝜋 𝑖 , then an inconsistency arises between chosen and executed actions that can affect training [8]. This would occur if the policy selects an action from a health state that the physical agent is incapable of executing.

To overcome this inconsistency, we modify the policy gradient such that the contribution from agent 𝑖 at time 𝑡 is multiplied by the true health of agent 𝑖 at time 𝑡 ; i.e. ℎ 𝑖,𝑡 ∈ [ 0 1 . The motivation , ] for this modification is that, as an agent's health degrades and the available action set is constricted, it becomes less likely that the action selected by the policy aligns with the action executed by the agent. By attenuating the policy gradient by the health of the agent, policy learning occurs more slowly on data generated in low health states and thus reduces the effect of mismatching chosen and executed actions. Section 5 investigates the case where the health state is binary for each agent and a zero-health state shrinks the action set until only a zero-vector action is executable by the agent. Lemma 1 states that gradient of the minimum-health baseline term in Eq. (8) is zero, and thus does not introduce bias to the gradient estimate in Eq. (7). Lemma 2 states that health-informed policy gradients converge to a locally optimal policy for systems with binary health states.

Lemma 1. Let the health-informed gradient in Eq. (7) be written as 𝑔 Ψ = 𝑔 ℎ -𝑔 𝑏 , then we have

$$g _ { b } = \mathbb { E } _ { \pi } \left [ \sum _ { i = 1 } ^ { n } b \left ( s ^ { - i } \right ) \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) \right ] = 0$$

Proof. Applying Eq. (8) to Eq. (6) we can write

$$g _ { \Psi } & = \quad \sum _ { s } \mu ( s ) \sum _ { \mathfrak { u } } \pi ( \mathfrak { u } \, | \, s, \theta ) \cdot \\ & \quad \sum _ { i = 1 } ^ { n } \left ( h _ { i } q _ { \pi } ( s, \mathfrak { u } ) - b \left ( s ^ { - i } \right ) \right ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ & = \quad g _ { h } - g _ { b }$$

Separating out the baseline's gradient contribution and applying Eq. (1)

$$- \tau \cdot \cdot \cdot \cdot - \tau \\ g _ { b } = \sum _ { s } \mu ( s ) \sum _ { u } \pi ( \mathbf u \ | \ s, \Theta ) \cdot \\ \sum _ { i = 1 } ^ { n } b \left ( s ^ { - i } \right ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \ | \ \tau _ { i }, \theta _ { i } ) \\ n$$

$$\ g _ { b } & = \sum _ { s } \mu ( s ) \sum _ { u } \pi ( \mathbf u \, | \, s, \mathbf \theta ) \cdot \\ & \sum _ { i = 1 } ^ { n } b \left ( s ^ { \sim i } \right ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ & = \sum _ { s } \mu ( s ) \sum _ { i = 1 } ^ { n } b \left ( s ^ { \sim i } \right ) \cdot \\ & \sum _ { u ^ { \prime } } \sum _ { a _ { i } } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \, | \, \tau _ { j }, \theta _ { j } ) \nabla _ { \theta _ { i } } \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ & = \sum _ { u ^ { \prime } - i } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \, | \, \tau _ { j }, \theta _ { j } ) \nabla _ { \theta _ { i } } 1 \\ & = \sum _ { u ^ { \prime } - i } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \, | \, \tau _ { j }, \theta _ { j } ) \nabla _ { \theta _ { i } } 1 \\ & = \quad 0 \\ \Delta \text{MMA 2. Given a system with binary health states } h _ { i } \in \{ 0, 1 \},$$

□

Lemma 2. Given a system with binary health states ℎ 𝑖 ∈ { 0 1 , } , where ℎ 𝑖 = 0 constricts the action space to a single element, |A 𝑖 GLYPH&lt;0&gt; s ℎ 𝑖 = 0 GLYPH&lt;1&gt; | = 1 , following the gradient 𝑔 Ψ in Eq. (7) at each iteration 𝑘 gives

$$\lim _ { k \to \infty } \| \nabla _ { \theta } J \| = 0$$

Proof. From Lemma 1 and Eq. (7), we have

$$g _ { \Psi } = g _ { h } = \mathbb { E } _ { \pi } \left [ \sum _ { i = 1 } ^ { n } h _ { i, t } G _ { t } \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) \right ].$$

With binary health states, we can separate the 𝑛 agents into groups based on their health at time 𝑡 such that I 1 = { 𝑖 : ℎ 𝑖,𝑡 = 1 } and I 0 = { 𝑖 : ℎ 𝑖,𝑡 = 0 } . For the group of agents in I 0 , the action space is constrained such that a single action is deterministically selected, regardless of 𝜃 𝑖 . Therefore,

$$\nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) = 0, \ \ i \in \mathcal { I } _ { 0 }.$$

As a result, we can say for all 𝑖

$$h _ { i, t } \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) = \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ).$$

Applying this result and Eq. (1) gives

$$g _ { \Psi } & = \mathbb { B } _ { \pi } \left [ G _ { t } \sum _ { i } ^ { n } \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) \right ] \\ & = \mathbb { B } _ { \pi } \left [ G _ { t } \nabla _ { \theta } \log \pi _ { \theta } ( \mathbf u _ { t } \ | \ s _ { t }, \theta ) \right ],$$

which is the gradient of the single-agent REINFORCE algorithm that has proven convergence properties for undiscounted returns [32, 38]. □

.

Equation 8 provides a health-informed counterfactual baseline on the state value function that is completely agnostic to the action space, a property not seen in prior work [7, 19, 20, 25, 39]. This makes our approach well suited for use in policy optimization techniques for large or continuous action spaces, such as TRPO and PPO [27, 29].

Other recent work on multi-agent credit assignment draws inspiration from WLU and Aristocrat Utility (AU). Nguyen et al. [20] offer a modern form of WLU that requires maintaining explicit counts of discrete actions and state visitations and is not well posed for continuous domains and deep-RL. Modern implementations of Aristocrat Utility (AU) such as COMA [7] require enumeration over all possible actions or computationally expensive Monte Carlo analysis at each time step. The health-informed baseline suffers no such limitations.

## 4.2 Health-Informed Multi-Agent Proximal Policy Optimization

While the health-informed credit assignment technique described in Section 4.1 is applicable to any reinforcement learning algorithm that uses value functions, we choose to demonstrate our technique within a multi-agent variant of proximal policy optimization (PPO) [29]. PPO is chosen because it has been shown to work well with continuous action spaces [6] as well as multi-agent environments [24].

Our health-informed counterfactual baseline is evaluated using a centralized critic, 𝑉 𝑤 ( s 𝑡 ) , which we model with a deep neural network parameterized by weights 𝑤 . As with the original PPO paper [29], the centralized critic is trained using generalized advantage estimation [28] where centralized value targets are defined as

$$V _ { t } ^ { \text{targ} } = A _ { t } ^ { \text{GAE} } + V _ { w _ { \text{old} } } ( s _ { t } ), \text{ \quad \ \ } ( 1 0 )$$

and the centralized value loss function is

$$L ^ { \text{VF} } ( w ) = \left ( V _ { w } ( s _ { t } ) - V _ { t } ^ { \text{targ} } \right ) ^ { 2 }. \quad \ \ ( 1 1 ) \quad \ \ \ \ \ t i { \alpha }$$

Now replacing the returns, 𝐺 𝑡 , in Eq. (8) with the more general value targets, our counterfactual baseline becomes

$$\Psi _ { i, t } = h _ { i, t } \left ( V _ { t } ^ { \text{targ} } - V _ { w _ { o l d } } \left ( s _ { t } ^ { \neg i } \right ) \right ) \quad \quad ( 1 2 ) \quad \ v a$$

We apply the health-informed counterfactual baseline in Eq. (12) to PPO's surrogate objective function and formulate the clipped surrogate objective function

$$L ( \theta ) = \mathbb { E } _ { t } \left [ \frac { \pi _ { \theta } ( a _ { i, t } \, | \, \tau _ { i, t } ) } { \pi _ { \theta _ { \text{old} } } ( a _ { i, t } \, | \, \tau _ { i, t } ) } \, \Psi _ { i, t } \right ] = \mathbb { E } _ { t } \left [ \rho _ { i, t } ( \theta ) \Psi _ { i, t } \right ] \quad ( 1 3 ) \quad \text{co} \} _ { \text{dist} }$$

$$L ^ { \text{CLIP} + S } ( \theta ) = \Xi _ { t } [ c S _ { \pi _ { \theta } } + \begin{array} { c } \text{receipt} \\ a \sec } \\ & \min ( \rho _ { i, t } ( \theta ) \Psi _ { i, t }, \end{array} & \text{receipt} \\ [ \text{4} ] \text{-} ] \text{-} ]$$

clip GLYPH&lt;0&gt; 𝜌 𝑖,𝑡 ( 𝜃 ) , 1 -𝜖, 1 + 𝜖 GLYPH&lt;1&gt; Ψ 𝑖,𝑡 )] .

Asin the original PPO paper, we also need to train the value function network and augment with an entropy bonus𝑆 𝜋 𝜃 weighted by hyperparameter 𝑐 -to encourage exploration [29].

Algorithm 1 gives the training process for a group of 𝑛 cooperative agents in a centralized-learning, decentralized-execution framework using the health-informed multi-agent proximal policy optimization (MAPPO) algorithm and parameter sharing.

Algorithm 1 Health-Informed Multi-Agent PPO

Initialize 𝜃 and 𝑤

for 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛 = 1 2 , , ... do

Run local policies 𝜋 𝜃 on 𝑛 agents for 𝑡 𝑓 timesteps

Compute value targets 𝑉 targ 𝑡 , ∀ 𝑡 ∈ { 1 , .., 𝑡 𝑓 }

Compute Ψ 𝑖,𝑡 with Eq. (12) ∀ 𝑖, ∀ 𝑡

Compute 𝜃 ′ with PPO update in Eq. (14), with 𝐾 epochs and minibatch size 𝑀 ≤ 𝑛𝑡 𝑓

Compute 𝑤 ′ with Eq. (11)

Update 𝜃 ← ′ 𝜃 , 𝑤 ← 𝑤 ′

end for

## 5 EXPERIMENTS

This section presents experiments to demonstrate health-informed credit assignment in multi-agent learning. Two separate implementations of health-informed proximal policy optimization were developed. The first implementation was built with a TensorFlow framework within a forked version of OpenAI's Multi-Agent Particle Environment (MPE) library that is extended to incorporate the concepts of system health and risk-taking [17, 18]. To take advantage of recently developed multi-agent RL toolsets, a second implementation was built with PyTorch within RLlib [16] and trained in the PettingZoo multiwalker environment [9, 34].

Since the original MPE environments were dedicated to small groups of agents and did not incorporate the concept of health, new scenarios were developed. 3 The two MPE scenarios, titled hazardous navigation and hazardous communication network , and the PettingZoo multiwalker environment are described later in this section.

The experiments compare multi-agent deep deterministic policy gradients (MADDPG) and QMIX (for RLlib implementation only) [25] with three multi-agent variants of proximal policy optimization (MAPPO) referred to as local critic , central critic and min-health crediting . The local critic MAPPO uses an advantage function based on local observation value estimates Ψ 𝑖,𝑡 = 𝐴 GAE 𝑡 GLYPH&lt;16&gt; 𝜏 𝑖,𝑡 𝑓 GLYPH&lt;17&gt; . The central critic MAPPO uses an advantage function based on joint state value estimates enabled by the centralized learning assumption: Ψ 𝑖,𝑡 = 𝐴 GAE 𝑡 ( s 𝑡 ) . The minimum-health crediting MAPPO uses the health-informed counterfactual baseline in Equation 12.

Hazardous navigation. This environment is closely related to Lowe's 'cooperative navigation' environment where agents must cooperate to reach a set of landmarks [18]. Reward is based on the distance from each landmark to the nearest agent, thus all agents receive the same reward and each landmark should be 'covered' by a separate agent in order to maximize reward. Our variation of this problem incorporates a hazardous landmark that can probabilistically cause an agent to be terminated (i.e. spontaneously transition to a zero-health state) if the agent is within a threshold distance of the hazard. The landmark that poses a hazard is not known until at least one agent crosses its threshold distance. To connect this scenario to a real-world problem, consider the use of uninhabited aerial vehicles (UAVs) to monitor wildfires. Each spot fire must be

3 See Appendix B for a comparison between MADDPG and our proposed variants of MAPPO in an environment taken directly from the original MADDPG paper [18].

Figure 1: The 8-agent hazard navigation (1a), 16-agent hazardous communication (1b), and 5-agent multiwalker (1c) environments. (1a) black dots represent landmarks to be covered by agents. The red dot is the hazardous landmark that has been 'revealed' by an agent in its vicinity. (1b) The larger black dots represent the terminals to be connected. The smaller dots represent agents. Links are formed between agents that are within each other's communication radius. The red dot is the environmental hazard. Tiny red crosses represent agents that have been terminated due to proximity to the hazard. (1c) Walker balance the package on their heads and walk together. Fallen agents are given a zero-health and rendered immobilized

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-f9a57fc3-ef0f-4f74-a749-d08d8b2b5d82.jpg)

continuously monitored and one spot fire poses significant risk to any UAV within its proximity. Figure 1a is a snapshot of the hazardous navigation environment.

## 5.1 Results

Hazardous communication network. This environment consists of two fixed landmark terminals and a group of mobile agents that can serve as communication relays over short distances. The objective is for the agents to cooperatively arrange themselves into an uninterrupted chain linking the two terminals. All agents receive the same reward for every time step in which the terminals are connected, and zero reward when the link is broken. For each episode an environmental hazard is randomly placed between the terminals, which causes agents in its vicinity to be terminated with some probability 𝑝 fail . Figure 1b shows a snapshot of the hazardous communication network scenario.

Multiwalker. This environment, originally presented in Gupta et al. [9] and adapted into the PettingZoo library [34], consists of 𝑁 robots that must collaboratively carry a package. The group of robots is rewarded based on the distance the package has moved. Each agent observes the relative pose of neighboring walkers as well as the pose of the package. As control input, each agent selects the joint torques to apply to their leg joints. The agents must learn to walk as well as carry the package in order to achieve high reward. Unlike the original implementation of multiwalker that used local reward shaping to avoid the multi-agent credit assignment problem [9], this version of the problem enforces a joint reward signal. If an agent falls to the ground, it's health is set two zero and can take no further action. Figure 1c gives a snapshot of the multiwalker environment.

All three environments are characterized by partially observed state spaces, continuous action spaces, joint rewards, and agent attrition; making them particularly challenging for multi-agent reinforcement learning.

Figure 2 summarizes the results of our experiments. A few trends that are common to all campaigns immediately emerge. Most notably, we see that MAPPO with health-informed crediting tends to outperform all other multi-agent RL algorithms for each of the environments and group sizes tested. Furthermore, by comparing 2a-to-2b and 2c-to-2d, we see that the performance gap between health-informed crediting and other algorithms tends to increase as the number of agents increases. We expect such a trend because, as the number of agents in the environment increases, the more pronounced the multi-agent credit assignment problem becomes, and therefore crediting algorithms such as Equation 8 should show increasing benefits. In cases where health-informed crediting only slightly outperforms a non-crediting approach (such as 2a, 2b , and 2f), we see that the health-informed baseline has the added benefit of reducing variance between trials within a training campaign. This can be seen by comparing the relative sizes of the blue shaded regions with the orange shaded regions.

In general, centralized critics-which include MAPPO: central critic and MAPPO: min-health crediting-tend to outperform local critics and always outperform MADDPG and QMIX for the environments tested. MADDPG's underperformance is likely due to the fact that these environments consist of multi-agent group sizes considerably larger than those developed in the original MADDPG work. This would explain why MADDPG shows its best performance in Figure 2a which is the scenario most closely aligned with the original 'cooperative navigation' environment [18].

The poor perofmance of QMIX is almost certainly due to the fact the algorithm is fundamentally designed for discrete action spaces but our environments all consist of continuous action spaces. In order to run QMIX, the action space was discretized into eight action bins per joint, but this did not give sufficient resolution to enable QMIX to learn a suitable policy. This highlights the advantage of credit assignment with a policy optimization algorithm (i.e PPO) in contrast to value-based methods like QMIX and COMA.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-f898940d-309a-4b6d-af1d-e904e12d6dd5.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-bb0b50fd-4cda-413f-9376-973ec39d2535.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-aa318442-b2fa-45d4-8a5b-18d959f834cd.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-93aad84d-52db-4968-8d76-52ad08d391dc.jpg)

Figure 2: Learning curves for the hazardous navigation (2a, 2b), hazardous communication (2c, 2d), and multiwalker (2e, 2f) environments. Each campaign defines an environment and the number of agents present in that environment and produces a learning curve for MADDPG, three variants of MAPPO, and QMIX (note: QMIX is only implemented in multiwalker environment where RLlib was used as the training engine). A single learning curve is an average over four independent training experiments with the shaded region representing the minimum and maximum bounds of the four training experiments. MADDPGis shown in red crosses. MAPPO with a local critic is shown in green triangles. MAPPO with a non-crediting central critic is shown in orange X's. MAPPO with a central critic and the health-informed, counterfactual baseline given in Equation 8 (referred to as min-health crediting ) is shown in blue circles. QMIX is shown in purple diamonds. The algorithms and environments used to generate these results are publicly available at: https://github.com/rallen10/ergo\_particle\_gym

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-8d60b3b8-57ae-4cd9-883c-936ff05ad88e.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-51c96035-f275-447b-85f4-4183a2c1a7d7.jpg)

A local critic tends to learn more quickly, outperforming other algorithms in the short term, but then plateaus and is overtaken by central critic approaches. An interesting exception to this trend is the 5-Agent multiwalker experiment (2f) where local-critic MAPPO appears to perform on par with the health-informed MAPPO. The local critic MAPPO aggregate performance is heavily influenced by a trial that seemed to discover an exploit in the environment that produced high rewards with little coordination between the walkers; the agents learned a shaking/jerking motion-instead of a walking motion-that slid the package forward like an object moving on a shaking table. The local critic algorithm was not able to reproduce the behavior in other training, thus the wide variance in experiments.

Experiments were run on Intel Xeon E5-2687W CPUs in a 32core Linux desktop. The particle environment experiment were run for 50,000 episodes with each episode consisting of 50 time steps and training batches composed of 256 episodes. Training batches were broken into 8 minibatches and run over 8 epochs. Multiwalker trained for 5 million timesteps, with training batches of 16384 timesteps, minibatches 4096 timesteps, and 32 epochs. For the multi-agent PPO experiments an entropy coefficient of 0.01 was used for particle environments to ensure sufficient exploration [29] and 0.0 in multiwalker to stabilize training.

For all experiments represented in Figure 2 the policy network was composed of a multilayer perceptron (MLP) with 2 fully connected hidden layers, each of which being 64 units wide, and a hyberbolic tangent activation function. For experiments that utilized a local critic the value function network matched the architecture of the policy network. For experiments that utilized a centralized critic the value function network had a distinct architecture that was developed empirically. Such centralized critic networks consisted of a 8-layer by 64-unit, fully connected MLP that used an exponential linear unit (ELU) activation function [5]. We observe that the ELU activation function tended to outperform the rectified linear unit (ReLU) and hyperbolic tangent activation functions for central critic learning.

For the particle environments an actor learning rate of 1 0 . × 10 -3 and a central critic learning rate of 5 0 . × 10 -3 was used with the Adam optimizer [14]. For the multiwalker environment run with RLlib, a learning rate of 3 × 10 -4 was used.

## 6 CONCLUSIONS

In this paper we have proposed a definition for system health and shown how it can be used in policy gradient methods to improve multi-agent reinforcement learning in a certain class of Dec-POMDPs. The techniques presented here are well suited for solving continuous-control multi-robot coordination problems in hazardous environments such as search and rescue (e.g. exploring burning or collapsing buildings) disaster relief (e.g. mapping wildfires or toxic chemical leaks with groups of UAVs) and coordinated load carrying. These techniques are also well suited for reinforcement learning in multi-agent adversarial game environments that exhibit agent attrition, such as StarCraft II and DOTA 2 [24, 37].

This work raises several questions that merit future investigation. The logical next step would be to explore whether a similar form of counterfactual reasoning can help address multi-agent credit assignment in continuous-control environments that are not characterized by system health. This perhaps could be achieved by generating training data in environments with fewer agents than the target environment, but it is uncertain what side effects this type of 'off-environment" experience would have on training. Additionally, the combination of the action space constriction in Property 3 and health-informed policy gradient in Eq. (7) and Eq. (8) highlight the need for further investigation of policy gradients on systems where actions chosen by the policy do not exactly match the actions executed by an agent or agents [8].

## REFERENCES

- [1] Edward Balaban, Stephen B. Johnson, and Mykel J. Kochenderfer. 2019. Unifying System Health Management and Automated Decision Making. Journal of Artificial Intelligence Research 65 (Aug. 2019), 487-518. https://doi.org/10.1613/jair.1.11366
- [2] Edward Balaban, Sriram Narasimhan, Matthew Daigle, Indranil Roychoudhury, Adam Sweet, Christopher Bond, and G Gorospe. 2013. Development of a mobile robot test platform and methods for validation of prognostics-enabled decision making algorithms. International Journal of Prognostics and Health Management 4, 1 (2013), 87.
- [3] Daniel S Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. 2002. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research 27, 4 (2002), 819-840.
- [4] Abdeslam Boularias and Brahim Chaib-draa. 2008. Exact dynamic programming for decentralized POMDPs with lossless policy compression. In International Conference on Automated Planning and Scheduling (ICAPS) . AAAI Press, 20-27.
- [5] Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter. 2015. Fast and accurate deep network learning by exponential linear units (ELUs). arXiv preprint arXiv:1511.07289 (2015).
- [6] Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. 2016. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning (ICML) . 1329-1338.
- [7] Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. 2018. Counterfactual multi-agent policy gradients. In AAAI Conference on Artificial Intelligence (AAAI) .
- [8] Yasuhiro Fujita and Shin-ichi Maeda. 2018. Clipped action policy gradient. arXiv preprint arXiv:1802.07564 (2018).
- [9] Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. 2017. Cooperative multiagent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) . Springer, 66-83.
- [10] Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. 2004. Dynamic programming for partially observable stochastic games. In AAAI Conference on Artificial Intelligence (AAAI) , Vol. 4. 709-715.
- [11] Pablo Hernandez-Leal, Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. 2017. A survey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprint arXiv:1707.09183 (2017).
- [12] Pablo Hernandez-Leal, Bilal Kartal, and Matthew E Taylor. 2019. A survey and critique of multiagent deep reinforcement learning. Autonomous Agents and Multi-Agent Systems 33, 6 (2019), 750-797.
- [13] Maximilian Hüttenrauch, Adrian Šošić, and Gerhard Neumann. 2018. Local communication protocols for learning complex swarm behaviors with deep reinforcement learning. In International Conference on Swarm Intelligence . Springer, 71-83.
- [14] Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).
- [15] Mykel J Kochenderfer. 2015. Decision making under uncertainty: Theory and application . MIT Press.
- [16] Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg, Joseph Gonzalez, Michael Jordan, and Ion Stoica. 2018. RLlib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning . 3053-3062.
- [17] Ryan Lowe. 2018. Multi-agent particle environment . https://github.com/openai/ multiagent-particle-envs
- [18] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. 2017. Multi-agent actor-critic for mixed cooperative-competitive environments. In Advances in Neural Information Processing Systems (NIPS) . 6379-6390.
- [19] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. 2019. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems . 7613-7624.
- [20] Duc Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. 2018. Credit assignment for collective multiagent RL with global rewards. In Advances in Neural Information Processing Systems (NIPS) . 8102-8113.
- [21] Frans A Oliehoek, Julian FP Kooij, and Nikos Vlassis. 2008. The cross-entropy method for policy search in decentralized POMDPs. Informatica 32, 4 (2008), 341-357.
- [22] Frans A Oliehoek, Shimon Whiteson, and Matthijs TJ Spaan. 2013. Approximate solutions for factored Dec-POMDPs with many agents. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) . 563-570.
- [23] Shayegan Omidshafiei, Ali-akbar Agha-mohammadi, Christopher Amato, ShihYuan Liu, Jonathan P How, and John L Vian. 2016. Health-aware multi-UAV planning using decentralized partially observable semi-Markov decision processes. In AIAA Infotech@ Aerospace . 1407.
- [24] OpenAI. 2019. OpenAI Five . https://openai.com/five/#how-openai-five-works
- [25] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. 2018. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv:1803.11485 (2018).
- [26] Abhinav Saxena, Jose Celaya, Edward Balaban, Kai Goebel, Bhaskar Saha, Sankalita Saha, and Mark Schwabacher. 2008. Metrics for evaluating performance of prognostic techniques. In IEEE International Conference on Prognostics and Health Management . 1-17.
- [27] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. 2015. Trust region policy optimization. In International Conference on Machine Learning (ICML) . 1889-1897.
- [28] John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. 2016. High-dimensional continuous control using generalized advantage estimation. In International Conference on Learning Representations .
- [29] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017).
- [30] Matthijs TJ Spaan, Frans A Oliehoek, and Christopher Amato. 2011. Scaling up optimal heuristic search in Dec-POMDPs via incremental expansion. In International Joint Conference on Artificial Intelligence (IJCAI) .
- [31] Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT Press, Chapter 13, 321-338.
- [32] Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. 2000. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems . 1057-1063.
- [33] Daniel Szer and François Charpillet. 2005. An optimal best-first search algorithm for solving infinite horizon Dec-POMDPs. In European Conference on Machine Learning (ECML) . Springer, 389-399.
- [34] Justin K Terry, Benjamin Black, Ananth Hari, Luis Santos, Clemens Dieffendahl, Niall L Williams, Yashas Lokesh, Caroline Horsch, and Praveen Ravi. 2020. PettingZoo: Gym for Multi-Agent Reinforcement Learning. arXiv preprint arXiv:2009.14471 (2020).
- [35] Justin K Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, Benjamin Black, and Dinesh Manocha. 2020. Parameter Sharing is Surprisingly Useful for MultiAgent Deep Reinforcement Learning. arXiv preprint arXiv:2005.13625 (2020).
- [36] Kagan Tumer, Adrian K Agogino, and David H Wolpert. 2002. Learning sequences of actions in collectives of autonomous agents. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) . 378-385.
- [37] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. 2019. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 7782 (2019), 350-354.
- [38] Ronald J Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning 8, 3-4 (1992), 229-256.
- [39] David H Wolpert and Kagan Tumer. 2002. Optimal payoff functions for members of collectives. In Modeling Complexity in Economic and Social Systems . World Scientific, 355-369.

## A EXTENDED PROOFS FOR MULTI-AGENT POLICY GRADIENTS

Here elaborate on the equations presented in Section 4.1. Using Equation 1, we can derive a multi-agent policy gradient-without health-informed baseline-from the single-agent policy gradient. We then use this result to provide further detail on the intermediate steps in Lemma 1.

Lemma 3. For 𝑛 independent agents per Eq. (1)

$$\nabla J ( \theta ) \in g = \mathbb { E } \pi \left [ \sum _ { i = 1 } ^ { n } G _ { t } \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) \right ]$$

Proof. From Sutton and Barto [31] and Eq. (1) we have:

$$\nabla J ( \theta ) \in \L g = \mathcal { E } _ { \pi } \left | \sum _ { i = 1 } ^ { \ } G _ { t } \nabla _ { \theta _ { i } } \log \pi _ { \theta _ { i } } ( a _ { i, t } \, | \, \tau _ { i, t }, \theta _ { i } ) \right | \\ \L F. \, \text{From Stutton and Barto} \, [31] \, \text{and} \, Eq. \, ( 1 ) \, \text{we have} \\ \L g = \sum _ { s } \mu ( s ) \sum _ { \begin{array} { c } u \\ u \end{array} } q _ { \pi } ( s, u ) \nabla _ { \theta } \pi ( u \, | \, s, \theta ) \\ \quad = \sum _ { s } \mu ( s ) \sum _ { \begin{array} { c } u \\ u \end{array} } q _ { \pi } ( s, u ) \pi ( u \, | \, s, \theta ) \\ \quad \nabla _ { \theta } \log \prod _ { i = 1 } ^ { n } \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ \quad = \sum _ { s } \mu ( s ) \sum _ { \begin{array} { c } u \\ u \end{array} } q _ { \pi } ( s, u ) \pi ( u \, | \, s, \theta ) \\ \quad \nabla _ { \theta } \sum _ { \begin{array} { c } u \\ i = 1 } ^ { n } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ \quad = \sum _ { s } \mu ( s ) \sum _ { \begin{array} { c } u \\ u \end{array} } q _ { \pi } ( s, u ) \pi ( u \, | \, s, \theta ) \\ \quad \sum _ { i = 1 } ^ { n } \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ), \\ \text{gives the intermediate result} \\ \sum _ { i = 1 } ^ { \ } \mu ( s ) \sum _ { \begin{array} { c } u \end{array} } \pi ( u \, | \, s, \theta ).$$

which gives the intermediate result

$$g & = \sum _ { s } \mu ( s ) \sum _ { u } \pi ( u \ | \ s, \theta ) \cdot \\ & \sum _ { i = 1 } ^ { n } q \pi ( s, u ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \ | \ \tau _ { i }, \theta _ { i } ). \quad ( 1 5 ) \\ \wedge \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \. & \ }$$

$$\overline { i = 1 }$$

Continuing the derivation by replacing sums over variables with expectations of samples drawn following the policy π [31]

$$\text{$\text{$\text{$samples$ drawn following the policy $\pi$ [31]}$} \\ g = \mathbb { E } _ { \pi } \left [ \sum _ { u } \pi ( u \, | \, s _ { t }, \theta ) \. \\ \sum _ { i = 1 } ^ { n } q _ { \pi } ( s _ { t }, u ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i, t }, \theta _ { i } ) \right ] \\ = \mathbb { E } _ { \pi } \left [ \sum _ { i = 1 } ^ { n } q _ { \pi } ( s _ { t }, u _ { t } ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i, t } \, | \, \tau _ { i, t }, \theta _ { i } ) \right ]. \\ \text{$\text{$\text{$inall$ arraying at} } }$$

Finally arriving at

$$g = \mathbb { E } _ { \pi } \left [ \sum _ { i = 1 } ^ { n } G _ { t } \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i, t } \ | \ \tau _ { i, t }, \theta _ { i } ) \right ] \quad \quad ( 1 6 )$$

From Eq. (16) we can then arrive at Eq. (7) by substituting Ψ 𝑖,𝑡 for 𝐺 𝑡 in order to affect the bias, variance, and credit assignment in the policy gradient.

To investigate the convergence of the health-informed policy gradient, let us apply Equation 8 in place of 𝑞 π ( s u , ) in the final term in Equation 15. We have

$$g _ { \Psi } & = \sum _ { s } \mu ( s ) \sum _ { u } \pi ( u \, | \, s, \theta ) \sum _ { i = 1 } ^ { n } \cdot \\ & \quad \left ( h _ { i } q \pi ( s, u ) - b \left ( s ^ { - i } \right ) \right ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ & = \sum _ { s } \mu ( s ) \sum _ { u } \pi ( u \, | \, s, \theta ) \cdot \left ( \\ & \quad \sum _ { i = 1 } ^ { n } h _ { i } q \pi ( s, u ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) + \\ & \quad - \sum _ { i = 1 } ^ { n } b \left ( s ^ { - i } \right ) \nabla _ { \theta _ { i } } \log \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \, \right ) \\ & = g _ { h } - g _ { b } \\ \\ \text{Now we show that } a _ { \ } = 0 \text{ Note that this is equivalent to the}$$

Now we show that 𝑔 𝑏 = 0. Note that this is equivalent to the proof given in Lemma 1 but with more intermediate steps included to help the reader follow.

$$q$$

$$\tilde { 1 }$$

$$\text{-} \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \ dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \$$

Figure 3: Learning curves for the cooperative navigation problem with 3 agents and no hazardous landmarks . Each of the four learning curve is an average over four independent training experiments with the shaded region representing the minimumandmaximumboundsofthefourtraining experiments.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01022v4-figure-deb5900e-3a2a-4e11-98ea-820bc76cb436.jpg)

$$= \sum _ { s } \mu ( s ) \sum _ { i = 1 } ^ { n } b \left ( s ^ { \neg i } \right ) \sum _ { \mathfrak { u } ^ { \neg i } } \sum _ { a _ { i } } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \ | \ \tau _ { j }, \theta _ { j } ) \cdot \\ \quad & \nabla _ { \theta _ { i } } \pi _ { i } ( a _ { i } \ | \ \tau _ { i }, \theta _ { i } ) \\ \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

$$\tilde { 1 }$$

$$& \quad \cdot \upsilon _ { i } \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \colon \\ & = \sum _ { s } \mu ( s ) \sum _ { i = 1 } ^ { n } b \left ( s ^ { \neg i } \right ) \sum _ { \mathfrak { u } ^ { \neg i } } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \ | \ \tau _ { j }, \theta _ { j } ) \cdot \\ & \quad \sum _ { a _ { i } } \nabla _ { \theta _ { i } } \pi _ { i } ( a _ { i } \ | \ \tau _ { i }, \theta _ { i } ) \quad \\ & \quad \quad \quad$$

$$& \sum _ { a _ { i } } \nabla _ { \theta _ { i } } \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ = & \sum _ { s } \mu ( s ) \sum _ { i = 1 } ^ { n } b \left ( s ^ { \neg i } \right ) \sum _ { \mathfrak { u } ^ { \neg i } } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \, | \, \tau _ { j }, \theta _ { j } ) \cdot \\ & \quad \nabla _ { \Theta } \sum _ { a _ { i } } \pi _ { i } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) \\ = & \sum _ { s } \mu ( s ) \sum _ { i = 1 } ^ { n } b \left ( s ^ { \neg i } \right ) \sum _ { \mathfrak { u } ^ { \neg i } } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \, | \, \tau _ { j }, \theta _ { j } ) \cdot \\ & \quad \nabla _ { \Theta } 1 \\ = & \sum _ { \mathfrak { u } ( s ) } \sum _ { \mathfrak { u } ^ { n } } b \left ( s ^ { \neg i } \right ) \sum _ { \mathfrak { u } ^ { \neg i } } \prod _ { \mathfrak { u } ( a _ { i } \, | \, \tau _ { i }, \theta _ { i } ) 0 }$$

$$& = \sum _ { s } \overset { \psi } { \mu } ( s ) \sum _ { i = 1 } ^ { n } b \left ( s ^ { - i } \right ) \sum _ { \mathfrak { u } ^ { - i } } \prod _ { j = 1, j \neq i } ^ { n } \pi _ { j } ( a _ { j } \ | \ \tau _ { j }, \theta _ { j } ) 0 \\ & = 0$$

We should expect this result since the baseline term 𝑏 GLYPH&lt;0&gt; s ¬ 𝑖 GLYPH&lt;1&gt; is independent of actions-using the same logic provided by Sutton and Barto [31]-however it requires more manipulation to prove it for the multi-agent case.

## B NON-HEALTH-BASED ENVIRONMENTS

The environments described in Section 5 were designed to incorporate the concept of system health. It could be argued that these types of environments are outside the scope of what for which MADDPG was orginially designed, and therefore not a fair point of comparison. To address this concern, we ran our three variants of multi-agent PPO on the cooperative navigation environment that appears in the original MADDPG paper [18].

Figure 3 shows MADDPG successfully learning an effective policy over a 50,000 episode training experiment. This learning curve is what we expect to see given that this environment was originally developed in conjunction with MADDPG. It is shown, however, that MADDPG underpeforms all of the MAPPO implementations except the local-critic MAPPO. The central-critic, non-crediting variant of MAPPO produces the best performance, outperforming the minimum-health baseline crediting variant. This is contrast to the results for the hazardous communication scenario discussed in Section 5. However, this is to be expected due to the fact that the cooperative navigation environment using in Fig. 3 does not encapsulate the concepts of health or risk. Therefore no relevant data is generated that trains the value function network how to estimate the value of the minimum-health baseline in Eq. (8). We see that this causes the minimum-health crediting technique to display high variance between training experiments. The blue shaded region indicates that worst-performing training run on minimumhealth MAPPO under-performs all other algorithms, while the bestperforming training run out performs all other algorithms.
Ross E. Allen Jayesh K. Gupta Jaime Pena Yutai Zhou Javona White Bear Mykel J. Kochenderfer
Health-Informed Policy Gradients for Multi-Agent Reinforcement Learning
This paper proposes a definition of system health in the context of multiple
agents optimizing a joint reward function. We use this definition as a credit
assignment term in a policy gradient algorithm to distinguish the contributions
of individual agents to the global reward. The health-informed credit
assignment is then extended to a multi-agent variant of the proximal policy
optimization algorithm and demonstrated on particle and multiwalker robot
environments that have characteristics such as system health, risk-taking,
semi-expendable agents, continuous action spaces, and partial observability. We
show significant improvement in learning performance compared to policy
gradient methods that do not perform multi-agent credit assignment.