Year: 2021

Abstract:
Discovering successful coordinated behaviors is a central challenge in Multi-Agent Reinforcement Learning (MARL) since it requires exploring a joint action space that grows exponentially with the number of agents. In this paper, we propose a mechanism for achieving sufficient exploration and coordination in a team of agents. Specifically, agents are rewarded for contributing to a more diversified team behavior by employing proper intrinsic motivation functions. To learn meaningful coordination protocols, we structure agents’ interactions by introducing a novel framework, where at each timestep, an agent simulates counterfactual rollouts of its policy and, through a sequence of computations, assesses the gap between other agents’ current behaviors and their targets. Actions that minimize the gap are considered highly influential and are rewarded. We evaluate our approach on a set of challenging tasks with sparse rewards and partial observability that require learning complex cooperative strategies under a proper exploration scheme, such as the StarCraft Multi-Agent Challenge. Our methods show significantly improved performances over different baselines across all tasks.

heading: 1 INTRODUCTION
text: Deep Reinforcement Learning (DRL) has been applied to solve various challenging problems, where an agent typically learns to maximize the expected sum of extrinsic rewards gathered as a result of its actions performed in the environment (Sutton et al., 1998). Multi-Agent Reinforcement Learning (MARL) refers to the task of training a set of agents to maximize collective and/or individual rewards, while existing in the same environment and interacting with each other.
Recent works have shown that agents with coordinated behaviors learn remarkably faster (Roy et al., 2019) since coordination helps the discovery of effective policies in cooperative tasks. Nevertheless, achieving coordination among agents still remains a central challenge in MARL (Jaques et al., 2019). Prominent works often resort to a popular learning paradigm called Centralized Training with Decentralized Execution (CTDE) (Lowe et al., 2017; Foerster et al., 2018), where each agent is evaluated using a centralized critic and has access to extra information about the policies of other learning agents during training. At the time of execution, policies’ actions are restricted to local information only (i.e. their own observations). Our work is primarily motivated by the following natural questions:
In multi-agent settings, how can we quantify the effect of an agent (or player) on other teammates’ behaviors (particularly on their performance)? And to what degree exploiting this quantity can lead
to coordinated behaviors and consequently better overall performances?
To that end, we propose a novel approach that aims at promoting coordination for cooperative tasks by augmenting CTDE MARL main return-maximization objective with an additional multi-agent objective that acts as a policy regularizer; we refer to the latter objective as the influence function. To build intuition, a chosen agent, which we call the “influencer”, assesses the progress that other agents are making given its current policy and consequently learns behaviors that will result in an improved performance of its teammates. Concretely, we formulate the influence of an influencer π as an estimation of the dissimilarity between other agents’ behaviors and their targets given the current behavior of π. The influencer is encouraged to learn behaviors that are expected to minimize that
dissimilarity. We also propose two approaches to estimate the influence and empirically show that they yield unbiased estimates of the true value.
Agents acting upon the proposed coordination paradigm learn to efficiently exploit the observed joint action space using available information. However, and since the joint space grows exponentially with the number of agents, it is highly unlikely that agents will have access to sufficient information to learn optimal behaviors to solve the task at hand; this problem arises in many scenarios such as sparse-reward environments, thus a proper exploration scheme is often required. However, many existing multi-agent deep reinforcement learning algorithms still use mostly noise-based techniques (Liu et al., 2021; Rashid et al., 2018; Yang et al., 2018). Moreover, independent exploration proved to be inefficient in cooperative settings (Roy et al., 2019). Recently, this challenge was addressed through Intrinsic Motivation (IM) (Jaques et al., 2019; Du et al., 2019; Zhou et al., 2020b). Many approaches employ IM to encourage exploration of state-space (Han et al., 2020; Burda et al., 2019) or state-action space (Fayad & Ibrahim, 2021) by identifying novel configurations and rewarding an agent for visiting them. We provide an extension of these ideas into multi-agent settings and further build connection between reward shaping and coordinated behavior learning, where we choose an agent to act as an influencer (i.e. regularize its standard objective using the influence function) while other agents learn to maximize the expected sum of both extrinsic and intrinsic rewards.
To sum up, our main contributions are threefold: 1) developing an influence function to promote learning coordinated behaviors and improve team performance; 2) extending exploration via random network distillation to multi-agent settings by crafting a "novelty" function that rewards underexplored behaviors; 3) formulating a novel intrinsic incentive to promote learning diverse team behaviors to help uncover complex behaviors in a collaborative way.
We demonstrate the effectiveness of our methods on a comprehensive set of challenging tasks which include, but not limited to, the StarCraft Multi-Agent Challenges (SMAC) (Samvelyan et al., 2019) and the Multi-Agent Particle Environments (MAPE) (Mordatch & Abbeel, 2018; Lowe et al., 2017). Empirical results show a significant improvement over a wide variety of state-of-the-art MARL approaches. We also conduct insightful ablation studies to understand the relative importance of each component of the approach individually.

heading: 2 BACKGROUND

heading: 2.1 MARKOV GAMES
text: Markov games (Littman, 1994; Agarwal et al., 2020; Daskalakis et al., 2021) are a superset of Markov decision process (MDPs) and matrix games, including both multiple agents and multiple states. Formally, we consider a setting with N > 2 agents ([N ] := {1, 2 . . . , N}) who repeatedly select actions in a shared MDP. The goal of each agent is to maximize their respective action value function. Formally, an MDP is defined as a tuple G = (S,N, {Ai, ri}i∈[N ], T, γ, ρ), where:
• S is the finite states space, where the initial states are determined by a distribution ρ : S → [0, 1]. Since we consider partially observable testing environments, we denote by si the information observed by agent i about the global state s ∈ S.
• Ai is a finite action space for agent i with generic element ai ∈ Ai. Using common conventions, we will write A = Πj∈[N ]Aj and A−i = Πj 6=iAj to denote the joint action spaces of all agents and of all agents other than i with generic elements a = (ai)i∈[N ] and a−i = (aj)i 6=j∈[N ], respectively. According to this notation, we have that a = (ai,a−i) ∀i.
• ri : S × A → R is the individual reward function of agent i, i.e., ri(s, ai,a−i) is the instantaneous reward of agent i when agent i takes action ai and all other agents take actions a−i at state s ∈ S. • T is the transition probability function, for which T (s′|s,a) is the probability of transitioning from s to s′ when a ∈ A is the action profile chosen by the agents.
• γ is a discount factor for future rewards of the MDP, shared by all agents.
In a Markov game, each agent is independently choosing actions and receiving rewards. Conventionally, an agent k aims to maximize its own total expected return Rk = ∑T t=0 γ
trk,t where T is the time horizon.

heading: 2.2 MULTI-AGENT DEEP DETERMINISTIC POLICY GRADIENT
text: MADDPG (Lowe et al., 2017) is a multi-agent extension of the DDPG algorithm (Lillicrap et al., 2015). It adapts the CTDE paradigm, where each agent i possesses its own deterministic policy µ(i) for action selection and criticQ(i) for state-action value estimation, respectively parameterized by θ(i) and φ(i). All parametric models are trained off-policy from previous transitions ζt := (st,at, rt, st+1) uniformly sampled from a replay buffer D. Each centralized critic is trained to estimate the expected return for a particular agent i from the Q-learning loss:
L(i)(φ(i)) = Eζt∼D [∥∥∥Q(i)(st,at;φ(i))− [ri,t + γQ(i)target(st+1,µ(st+1))]∥∥∥2] (1)
Each policy is updated to maximize the expected discounted return of the corresponding agent i :
J (i) PG(θ (i)) = ED [ Q(i)(st,at) ] (2)
Notice that while optimizing an agent’s policy, all agents’ observation-action pairs are taken into consideration. By that, the value functions of all agents are trained in a centralized, stationary environment, despite happening in a multi-agent setting. Moreover, this procedure allows for the learning of coordinated strategies, yet needs to be augmented with efficient exploration methods that reward novel action configurations which may lead to the discovery of higher-return behaviors.

heading: 3 METHODS

heading: 3.1 BASIC INFLUENCE
text: Intuitively, one can define coordination in a team of agents as the behavior of each individual agent being informed by other agents. Furthermore, agents’ behaviors can be inter-affected either directly through communication for example or indirectly through task-specific shared goals and/or rewards or the dynamics of the environment. We hypothesize that when agents learn in a cooperative setting, they tend to affect each other’s exploitation processes, we confirm the hypothesis throughout the paper and build on that to formalize a general method to foster influential interactions and learn meaningful coordination protocols. Specifically, consider a setting where N agents with policies π1, π2, . . . , πN . We assume that the transition dynamics are dependent on agents’ actions (i.e. T (s′|s,a) 6= T (s|s′)), and use tasks that satisfy this assumption to validate our methods. We will write π,π−j to denote the joint policy of all agents and of all agents other than agent j, respectively. For two fixed agents i and j, the influence of the behavior of j’s policy on i’s performance (expected return) can be quantified by "marginalizing" out all effects induced by other agents on the expected outcomes of i. More precisely, if the desired quantity is qπji , then for all (s, aj) ∈ S ×Aj :
q πj i (s, aj) = E
a−j∼π−j [ri(s,a)] + γ ∑ s′ p(s′|s, aj) · E a′j∼πj(.|s ′ j) [ q πj i (s ′, a′j) ]
p(s′|s, aj) = ∑ a−j T (s′|s,a) ∏ k 6=j πk(ak|s) (3)
One can note that, analogously to the action-value function Qi, q πj i measures tuple values w.r.t i where the learning dynamics of i conditioned only on the behavior of j. Naturally, in expectation, q πj i represents the sum of rewards that an agent i is expected to receive when influenced by πj . Based on above, we say that an agent is an optimal influencer when agents only influenced by its policy learn optimal behaviors. To that end, if we fix an agent (say 1), then its influence, F (π1), on the rest of the team is defined as follows:
F (π1) = ∑
2≤i≤N
αi · Es,a1∼π1 [( qπ1i (s, a1)−maxu Qi(s,u) )2] (4)
where (αi)2≤i≤N are positive scaling factors that sum up to 1 and Qi is the action value function of agent i. Intuitively, since F (π1) is the difference between the expected rewards of other agents conditioned on the current behavior of π1 and the maximum returns that can be achieved by other agents in the given task, minimizing F will encourage π1 to take actions that lead other agents’
conditioned returns (qπ1i )2≤i≤N closer to their maximum unrestricted returns (maxuQi(s,u)), which matches our definition of an optimal influencer. Hence, the objective functions of agents i ∈ [N ] are: Ji(θi) = Eπ [∑ 0≤t≤T γ tri,t ] − λF (π1)1i=1, where θi are the parameters of πi and λ is a hyperparameter called the influence importance temperature. Theorem 1. (Influence Gradient)
∇θ1F (π1) = ∑
2≤i≤N
αiEs,π1 [ ∇θ1 log π1(a1|s)g(s, a1)2
+ 2g(s, a1)Es,π1 [∇θ1 log π1(a1|s)q π1 i (s, a1)] ] (5) where g(T ) = g(s, a1) = qπ1i (s, a1)−maxuQi(s,u).
It has been shown empirically that the existence of one influencer can greatly improve the overall team performance. Thus, we only consider one influencer throughout our practical sections and upon that, we call our method "Asymmetric Learning for Influencing a Team of Agents (ALITA)".

heading: 3.1.1 INFLUENCE WITH SINGLE ESTIMATOR
text: Practically, we quantify the influence F (π1) by initializing a network Qcen : S ×A→ RN−1 with parameters φcen; the i-th component of Qcen(.;φcen) estimates qπ1i by minimizing the following loss at each timestep t:
L(φcen) = E(x,a,r,x′)∼Dt [ ‖Qcen(x,a;φcen)− y‖2 ] (6)
where y ∈ RN−1, yi = ri(x,a) + γQ(i)target(x′,π(x′)); Q (i) target is the target critic of agent πi, and Dt = {T | T = (x,a, r,x′) ⊂ B and x1 = s1,t, a1 = a1,t}, where B is a buffer storing all agents’ transitions. The reason for choosing such definition of D is that when fixing the current information of π (i.e. at timestep t) while updating Qceni , we practically marginalize out all agents’ experience (other than 1 and i). Later in this section, we show that this trick yields a fairly good approximation of qπ1i . After training Q cen, we compute the influence F (π1):
F (π1) = E(x,.,r,x′)∼B [ ‖Qcen(x,π(x))− z‖2 ] (7)
where z = [maxuQ2(x′,u), . . . ,maxuQN (x′,u)]T . Note that the second term in the expectation (i.e. the target vector z) is set to be undifferentiable with respect to π1’s parameters and thus does not propagate through its network.

heading: 3.1.2 INFLUENCE WITH MULTIPLE INDIVIDUAL ESTIMATORS
text: As seen earlier, agent π1 estimates the gap between each agent’s value and its target value by employing a single network. Another desirable approach is to additively decompose the centralized estimator Qcen, i.e. to use multiple estimators where each estimator, namely Q(i)clone, individually calculates a fairly good approximation of qπ1i . To reduce computational costs and arrive at better estimates, each estimator’s network is initialized with the parameters of the corresponding critic network at each episode (i.e. Q(i)clone ← Qi). The training is carried out similarly to that of the single estimator setting,
L(φ(i)) = E(x,a,r,x′)∼Dt [ ||Q(i)clone(x,a;φ (i))− yi||2 ]
(8)
The influence function could be expressed as:
F (π1) = E(x,.,.,x′)∼B 1
N − 1 N−1∑ i=1 ∥∥∥Q(i)clone(x,π(x))− zi∥∥∥2 (9) Which approach yields better estimates of the true value of the influence? The influence of an agent π on a team of agents T was defined as a measure of the improvement in the performance of T given the current behavior of π. However, measuring the influence using function approximators might result in inaccurate estimates. To resolve this concern, we plot the influence estimates of the two prior approaches over time while they learn on the Cooperative Navigation MAPE task (Mordatch
& Abbeel, 2018), where the number of agents is N = 6. In Figure (1), we graph the average influence estimates over 40000 episodes and compare it to the true value. The latter is averaged over 1000 episodes following the current policies of agents and is reported every 5000 episodes. The plots show a relatively small bias of both methods during learning. However, as Figure (1) suggests, measuring influence using multiple individual estimators yielded more accurate values after enough training which substantiates its superiority over the shared network approach. Note that, although confirms our prior hypothesis, this experiment does not reflect the importance of employing the influence on the final performance of the agents as we will discuss that in Section (4).

heading: 3.2 INTRINSIC MOTIVATION FOR DIVERSIFIED TEAM BEHAVIOR
text: In this section, we introduce a framework for achieving cooperative exploration by ensuring that agents are consistently tilted towards visiting under-explored state-action configurations; we start by providing a simple demonstration which shows that the number of environment steps required for all agents to randomly traverse all possible action configurations increases at least exponentially with the number of agents.
Proposition 1. Consider an L-action setting of n agents. In expectation, the number of steps T needed to visit all Ln action configurations at least once without coordinated exploration grows at least exponentially with the number of agents. More concretely, E[T ] = Ω(nLn).
To mitigate this issue, we assign agent π1 a prediction error as an intrinsic reward to facilitate recognizing and learning novel behaviors:
r (π1) t = r ext 1,t + λπ ‖φ(s1,t, a1,t)− (s1,t, a1,t)‖ 2︸ ︷︷ ︸ ψ(s1,t,a1,t)
(10)
Where φ is an autoencoder network regularly trained on data generated by the policy π1 and λπ is a hyper-parameter that balances the extrinsic and intrinsic reward terms. ψ’s expression stems from the observation that when an autoencoder is trained on data from a particular distribution, it will be good at reconstructing data from that distribution, while it will perform poorly if the data is from a different distribution. Thus, by employing ψ as an intrinsic bonus, π1 rewards states’ observations and actions that do not belong to the data generated by it. In practice, φ is designed to be a relatively large network since we want it to be slightly overfitted to the training data so that it will not accidentally generalize to behaviors that we may deem novel (Fayad & Ibrahim, 2021; Zhang et al., 2019).
Nevertheless, assigning each agent a ψ is not sufficient as it makes the case equivalent to independent exploration approaches. Thus, we propose a coordinated exploration method that takes into account other agents’ behaviors, encouraging agents to diversify team behavior while maintaining good performance.
Specifically, we assign agents {πi}Ni=2 intrinsic penalty defined as:
rintπi(st,at) = − exp ( − ωiψ(s1,t, a1,t) ) ‖πi(si,t)− ai,t‖2 (11)
This reward term aims at teaching the agents to recognize previous behaviors and synchronously select novel configurations. To build intuition, consider a case where N = 2. Whenever (π, µ) select an action tuple in the neighborhood of a frequently-visited tuple (a1, a2) in a global state s, ψ will be relatively small and the penalty, rintµ , will be large. Conversely, if (π, µ) encounter a novel tuple, say (a′1, a ′ 2) in s, the small penalty of µ (Eq. (11)) together with a large reward for π (Eq. (10)) will drive both agents to further explore this encounter.
In all, Fig. (2) shows how this framework can be augmented with the basic influence introduced earlier to reinforce learning and discovering coordinated behaviors.

heading: 4 EMPIRICAL EVALUATION & ANALYSIS
text: The goals of our experiments are to: a) verify the performance of our method on a comprehensive set of multi-agent challenges (SMAC, MAPE, sparse-reward settings, and continuous control environments); b) perform ablations to examine which particular components of the proposed framework are important for good performance.

heading: 4.1 COOPERATIVE & MIXED GAMES

heading: 4.1.1 STARCRAFT MULTI-AGENT CHALLENGE
text: StarCraft provides a rich set of heterogeneous units each with diverse actions, allowing for extremely complex cooperative behaviors among agents. We thus evaluate our method on several SC micromanagement tasks from the SMAC1 benchmark (Samvelyan et al., 2019), where a group of mixed-typed units controlled by decentralized agents needs to cooperate to defeat another group of mixed-typed enemy units controlled by built-in heuristic rules with “difficult” setting; the battles can be both symmetric (same units in both groups) or asymmetric. Each agent observes its own status and, within its field of view, it also observes other units’ statistics such as health, location, and unit type (partial observability); agents can only attack enemies within their shooting range. A shared reward is received on battle victory as well as damaging or killing enemy units. Each battle has step limits set by SMAC and may end early. We consider 5 battle maps grouped into Easy (2s3z), Hard (5m_vs_6m, 3s_vs_5z), and Super Hard (corridor, 3s5z_vs_3s6z) against 8 baseline methods using their open-source implementations based on PyMARL (Samvelyan et al., 2019): IQL (Tan, 1993), VDN (Sunehag et al., 2018), QMIX (Rashid et al., 2018), LIIR (Individual Intrinsic Rewards) (Du et al., 2019), LICA (Implicit Credit Assignment) (Zhou et al., 2020b), and MAVEN (Variational Exploration) (Mahajan et al., 2019), EDTI (Decision-Theoretic Exploration) , EITI (Information-Theoretic Exploration) (Wang et al., 2019).
The corridor map, in which 6 Zealots face 24 enemy Zerglings, requires agents to make effective use of the terrain features and block enemy attacks from different directions. A properly coordinated exploration scheme applied to this map would help the agents discover a suitable unit positioning quickly and improve performance, while 2s3z requires agents to learn “focus fire" and interception. For the asymmetric 5m_vs_6m, basic agent coordination alone such as “focus firing” no longer suffices (Du et al., 2019) and consistent success requires extended exploration to uncover complex cooperative strategies such as pulling back units with low health during combat. The 3s_vs_5z scenario features three allied Stalkers against five enemy Zealots. Since Zealots counter Stalkers, the only winning strategy for the allied units is to kite the enemy around the map and kill them one after another, causing the failure of independent learning algorithms to learn good policies in this task. The 3s5z_vs_3s6z is an extended scenario of 3s_vs_5z where 3 Stalkers and 5 Zealots battle against 3 Stalkers and 6 Zealots—The extra enemy makes this scenario far more challenging. For this task, we randomly chose 1 S and 1 Z to act as influencers because of the heterogeneity of the team. In the rest, agents are symmetric, hence the influencer is randomly chosen at the beginning of training.
For most of these scenarios, ALITA consistently shows the best performance with significant learning speed which confirms the effectiveness of our proposed methods. Detailed results are reported in Figure (3) as they present the median win rate during the training across 12 random runs.
1https://github.com/oxwhirl/smac

heading: 4.1.2 SPARSE-REWARD SETTINGS
text: We test on two additional tasks to show the effectiveness our method on sparse-reward settings and compare it to famous influence-based coordinated exploration algorithms (Table (1)): EDTI, EITI (Wang et al., 2019), and Social Influence (Jaques et al., 2019).
Sparse Push-Box: A 15× 15 room is populated with 2 agents and 1 box. Agents need to push the box to the wall in 300 environment steps to get a reward of 1000. Moreover, both can observe the coordinates of their teammate and the location of the box. However, the box is so heavy that only when two agents push it in the same direction at the same time can it be moved a grid. Agents need to coordinate their positions and actions for multiple steps to earn a reward.
Sparse Secret Room: A 25× 25 grid is divided into three small rooms on the right and one large room on the left where 2 agents are initially spawned. There is one door between each small room and the large room. A switch in the large room controls all three doors. A switch also exists in each small room which only controls the room’s door. The agents need to navigate to one of the three small rooms, i.e. the target room, to receive positive reward. The task is considered solved if both agents are in the target room. The state vector contains (x, y) locations of all agents and binary variables to indicate if doors are open.
A notable reason for the good performance of ALITA on the two tasks is that through the intrinsic rewards, agents tend to explore the majority of the possible encounters at the beginning of learning which is crucial for estimating the value of the influence. Exploiting the latter, agents tend to reinforce learning jointly rewarding configurations.

heading: 4.1.3 MULTI-AGENT PARTICLE ENVIRONMENTS
text: To understand how the proposed method helps agents achieve cooperative behavior in nonstationary settings, we conduct experiments on the grounded communication environment 2 proposed in
2https://github.com/openai/multiagent-particle-envs
(Mordatch & Abbeel, 2018; Lowe et al., 2017). The chosen tasks are the Cooperative Navigation, Cooperative Communication, and Physical Deception.3 We trained with 10 random seeds and reported results in Tables (2, 3, 4).

heading: 4.2 CONTINUOUS ENVIRONMENTS
text: To confirm the scalability of our algorithm to large continuous settings, we measure the performance of our algorithm on a suite of PyBullet (Tan et al., 2018) continuous control tasks, interfaced through OpenAI Gym (Brockman et al., 2016). Gym environments, however, are mainly single-agent settings, thus to evaluate our approach, we reframe the problem by introducing an additional learning agent that acts as an auxiliary agent. Crucially, both agents work collaboratively in order to find a region of the solution space where an agent accumulates higher rewards. We use TD3 (Fujimoto et al., 2018) as our learning model and test it against state-of-the-art algorithms in 5 gym environments. Our algorithm outperforms all baselines across all different environments (e.g. our method attains 131% return of SAC final performance on Humanoid-v3). For detailed results, see Appendix C.
4.3 ABLATIONS
We further investigate the significance of each component along with a symmetric extension of the proposed framework. Specifically, we consider the three cases: 1) No F: where the influence function does not contribute to the update rule to any of the policies; 2) No IM: where a randomly selected agent maximizes both the expected sum of extrinsic rewards along with the influence function, and other agents’ policies are learned using the DDPG; 3) Symmetric: where all agents simultaneously play the role of an influencer and influencee: they learn to maximize an augmented reward function (extrinsic and intrinsic) along with the influence function.
Results of the experiments conducted on the 2s3z SMAC scenario show that, in the absence of the intrinsic rewards (No IM), the agents experience a slightly decreased overall performance when compared to the significant decline induced by detaching the influence function (No F). In Figure (4), we observe that the agents following the Symmetric approach learn faster, and achieve a significantly higher median win rate. This approach, however, doubles the computational costs which restricts its applicability in larger settings.

heading: 5 RELATED WORK
text: We discuss recently developed methods for exploration in RL using intrinsic motivation, coordination in multi-agent RL, and influence-based coordinated exploration methods subsequently.
Intrinsic motivation (IM) has been increasingly used both in single-agent RL and multi-agent RL. A core idea of IM is to encourage the agent to take new actions or visit new states, thus exploring the environment and obtaining more diverse behaviors. One common approach is to approximate state or state-action visitation frequency and add a reward bonus to states the agent rarely covers (Tang et al., 2017; Bellemare et al., 2016; Martin et al., 2017). A more related IM approach is to evaluate state visitation novelty (Klissarov et al., 2019; Han et al., 2020; Burda et al., 2019) or state-action visitation novelty (Fayad & Ibrahim, 2021). Inspired by the latter, we provided a natural extension for this approach to the MARL settings by the learning of a "novelty" function. Other works make use of single-agent IM to construct their multi-agent intrinsic reward (Du et al., 2019; Iqbal & Sha, 2019). Each agent in (Du et al., 2019) learns a distinct intrinsic reward so that the agents are stimulated differently, even when the environment only feedbacks a team reward. This reward helps distinguish the contributions of the agents when the environment only returns a collective reward. In (Iqbal & Sha, 2019), each agent has a novelty function that assesses how novel an observation is to it, based
3Full description in Appendix B
on its past experience. Their multi-agent intrinsic reward is defined based on how novel all agents consider an agent’s observation. A recent work (Liu et al., 2021) assigns agents a common goal while exploring. The goal is selected from multiple projected state spaces via a normalized entropy-based technique. Then, agents are trained to reach this goal in a coordinated manner.
Many works studied the cooperative settings in MARL; a straightforward approach is to use independent learning agents (fully decentralized learning). This approach, however, is shown to perform inadequately both with Q-learning (Matignon et al., 2012) and with policy gradient (Lowe et al., 2017). Therefore, we considered the CTDE paradigm, where each agent’s policy takes its individual observation as many real life applications dictate, while the centralized critic permit for sharing of information during training. Policy gradient methods have been commonly used along with the CTDE paradigm in MARL, either by implementing a single centralized critic for all agents (Foerster et al., 2018), or one centralized critic for each agent (Lowe et al., 2017). Adopting the latter, we enable agents with different reward functions to learn in competitive and mixed scenarios as well.
Some other works encouraged cooperative interactions between agents by sharing useful information (Yang et al., 2020; Hostallero et al., 2020). In Hostallero et al. (2020), each agent broadcasts a signal that represents an assessment of the effect of the joint actions that all agents take on its expected reward. Different from our approach, this signal encourages agents to behave as is expected of them and does not benefit exploration. As for Yang et al. (2020), each agent learns an incentive function that rewards other agents based on their actions. Each agent’s function aims to alter other agents’ behavior to maximize its extrinsic rewards. To accomplish this, each agent requires access to every other agent’s policy, incentive function, and return making this approach difficult to scale and execute. Additionally, Roy et al. (2019) proposed two policy regularizers approaches to promote coordination in a team of agent, one of which assumes that an agent must be able to predict the behavior of its teammates in order to coordinate with them, while the other supposes that coordinated agents collectively recognize different situations and synchronously switch to different sub-policies to react to them.
Similarly to our work, (Jaques et al., 2019) proposed a similar idea of rewarding an agent for having a casual influence on other agents’ actions. Their method showed interesting results in terms of learning coordinated behavior. However, this casual influence is designed to reward policies for influencing other policies’ actions without considering the "quality" of this influence. Barton et al. (2018) propose causal influence as a way to measure coordination between agents, specifically using Convergence Cross Mapping (CCM) to analyze the degree of dependence between two agents’ policies. Our method also draws inspiration from the work of (Wang et al., 2019), as they define an influence-based intrinsic exploration bonus, called Value of Interaction (VoI), by the expected difference between the action-value function of one agent and its counterfactual action-value function without considering the state and action of the other agent. Particularly, the latter measures the expected behavior of an agent in a situation where it is not influenced by the other agent. Consequently, by maximizing the VoI, agents tend to explore meaningful interaction points as the distance between their action-value functions conditioned on other agents and their independent action-value (only conditioned on self behavior) functions is maximized. The primary difference from ALITA lies in our definition of the influence.

heading: 6 CONCLUSIONS & FUTURE WORK
text: We introduced a novel multi-agent RL algorithm for achieving coordination through assessing the influence an agent has on other agents’ behaviors. Additionally, we proposed to learn an intrinsic reward for each agent to promote coordinated team exploration. We tested our algorithm on a wide variety of tasks with many challenges, such as partial observability, sparse rewards, and large spaces; these tasks include, but not limited to, SMAC, MAPE, as well as OpenAI gym continuous environments. Our methods achieved noticeable improvement over prominent algorithms on all tasks. One promising extension of our algorithm is to use Graph Attention Networks (Veličković et al., 2017; Zhou et al., 2020a) to learn the importance of the influencer in determining the influencees’ policies and to establish a message-passing architecture in networked systems. The investigation of the effectiveness of these methods is left for future works.

heading: 7 REPRODUCIBILITY STATEMENT
text: We have provided an illustration of the proposed algorithm in Fig. (1) along with implementation details and hyperparameters selection in Appendix D. Furthermore, code is submitted with Supplementary Material and each algorithm is evaluated at least 10 times using random seeds on all environments.

heading: A MATHEMATICAL DETAILS
text: Theorem 1. (Influence Gradient) ∇θ1F (π1) = ∑
2≤i≤N
αiEs,π1 [ ∇θ1 log π1(a1|s)g(s, a1)2 + 2g(s, a1)Es,π1 [∇θ1 log π1(a1|s)q π1 i (s, a1)] ] where g(T ) = g(s, a1) = qπ1i (s, a1)−maxuQi(s,u).
Proof. We start by finding ∇θ1q π1 i :
∇θ1q π1 i (s, a1) = γ E
s′∼p(.|s,a1) a′1∼π1(.|s ′ 1)
[ ∇θ1 log π1(a′1|s′)q π1 i (s ′, a′1) +∇θ1q π1 i (s ′, a′1) ]
Let T = (s, a1) ∈ S×A1, and φ(T ) = γEs′,a′1 [∇θ1 log π1(a ′ 1|s′)q π1 i (s ′, a′1)] where the distribution of s′ is conditional on s and a1. Thus, write∇θ1q π1 i (T ) as:
φ(T ) + γEs′,a′1 [∇θ1q π1 i (T ′)] (T ′ = (s′, a′1))
= φ(T ) + γEs′,a′1 [φ(T ′) + γEs′′,a′′1 [∇θ1q π1 i (T ′′)]] (new tuples T ′′are conditioned on previous ones) ... (repeatedly unroll∇qπ1i )
∗ = ∑ T ′ ∞∑ k=0 Pr(T → T ′; k)γkφ(T ′)
∝ ∑ T ′ lim t→∞
Pr(St = s′|T, γπ1)︸ ︷︷ ︸ dT (s′) φ(T ′) (normalize the series term)
= ∑ T ′ dT (s ′)Es′′,a′′1 [∇θ1 log π1(a ′′ 1 |s′′)q π1 i (s ′′, a′′1)] (dT is the discounted visitation distribution induced by π1)
= E s′∼dT (.) a′1∼π1(.|s ′)
[∇θ1 log π1(a′1|s′)q π1 i (s ′, a′1)]
= E T ′∼ρ(.|T )
[∇θ1 log π1(a′1|s′)q π1 i (T ′)] (use T ′ to simplify notation)
Since g(T ) = qπ1i (s, a1)−maxuQi(s,u), the gradient of F (π1) can be expressed as: ∇θ1F (π1) = ∑
2≤i≤N
αiET [ ∇θ1 log π1(a1|s)g(T )2︸ ︷︷ ︸
A
+2g(T )∇θ1q π1 i (T )]
= ∑
2≤i≤N
αiET [ A+ 2g(T ) E
T ′∼ρ(.|T ) [∇θ1 log π1(a′1|s′)q π1 i (T
′)] ]
= ∑
2≤i≤N
αiET [ A+ 2g(T ) · ET ′ [∇θ1 log π1(a′1|s′)q π1 i (T ′)] ]
In all, ∇θ1F (π1) = ∑
2≤i≤N
αiEs,π1 [ ∇θ1 log π1(a1|s)g(s, a1)2+2g(s, a1)Es,π1 [∇θ1 log π1(a1|s)q π1 i (s, a1)] ]
Proposition 1. Consider an L-action setting of n agents. In expectation, the number of steps T needed to visit all Ln action configurations at least once without coordinated exploration grows at least exponentially with the number of agents. More concretely, E[T ] = Ω(nLn).
Proof. Let M = Ln. Since agents tend to visit different action configurations with no coordinated behavior, one can equivalently say that agents uniformly pick a configuration out of all Ln possible
configurations at each step. Let Tk be the number of steps to visit the k-th distinct configuration after covering k − 1 distinct action tuples. Observe that:
E[T ] = M∑ k=1 E[Tk] (12)
Now, Pr[Tk = i] = ( k−1 M )i−1( 1− k−1M ) meaning that Tk follows a geometric distribution. Thus,
E[Tk] = ∞∑ i=1 ( k − 1 M )i−1( M − k + 1 M ) i =
M
M − k + 1 (13)
Getting back to Eq. (12),
E[T ] = M M∑ k=1
1
M − k + 1 = M M∑ k=1 1 k > M ∫ M 1 1 x dx = M lnM = nLn lnL (14)
And the conclusion follows.

heading: B DETAILS OF MAPE TASKS
text: Cooperative Navigation: In this environment, N agents must collaborate to reach a set of N landmarks with known positions. Agents are rewarded based on how far any agent is from each landmark, meaning that the agents learn to spread with each agent covering one landmark. The agents, which occupy a significant physical space, are aware of their relative positions to each other and are further penalized when colliding with each other.
Cooperative Communication: Here, a stationary speaker must guide a listener in an environment consisting of three landmarks of differing colors. At each episode, one landmark of a particular color is set as a goal for the listener to be reached, however, only the speaker can observe which landmark the listener must navigate to. Moreover, The speaker can produce a communication output at each time step which is observed by the listener. The latter must navigate the environment to reach the correct landmark. Agents are collectively rewarded at the end of an episode based on the listener’s distance from the correct landmark.
Physical Deception: This environment consists of N agents and N landmarks, with one landmark as the target of all agents. The agents are rewarded based on the distance of the closest agent to the target landmark, making it sufficient for only one agent to reach it. An adversary agent also tries to reach the target landmark, while the agents are penalized as it gets closer to the target. The adversary, however, does not know which landmark is the target and must deduce it from the agents’ behavior. For that reason, agents must cooperate to trick the adversary by learning to cover all the landmarks. This task shows that our algorithm is applicable not only to cooperative interactions but to mixed environments as well.
In the cooperative communication and physical deception tasks, ALITA obtained the highest success rate across all baselines.

heading: C ADDITIONAL EXPERIMENTS ON CONTINUOUS ENVIRONMENTS
text: Since the formulation of F needs a shared buffer, SAC and TD3 stand as the best off-policy candidates to be incorporated with our framework, as they have shown great performances on many benchmarks. SAC, however, uses stochastic policies in general which makes it infeasible to combine with the formulation of rint. Therefore, we use TD3 as our learning model to measure its performance on a suite of PyBullet (Tan et al., 2018) continuous control tasks, interfaced through OpenAI Gym (Brockman et al., 2016). While many previous works utilized the Mujoco (Todorov et al., 2012) physics engine to simulate the system dynamics of these tasks, we found it better to evaluate our method on benchmark problems powered by PyBullet simulator since it is widely reported that PyBullet problems are harder to solve (Tan et al., 2018) when compared to Mujoco. Also, Pybullet is license-free, unlike Mujoco that is only available to its license holders.
We compare our method to the original twin delayed deep deterministic policy gradients (TD3) (Fujimoto et al., 2018); soft actor critic (SAC) (Haarnoja et al., 2018); proximal policy optimization (PPO) (Schulman et al., 2017), a stable and efficient on-policy policy gradient algorithm; deep deterministic policy gradient (DDPG); trust region policy optimization (TRPO) (Schulman et al.,
2015); Tsallis actor-critic (TAC) (Chen & Peng, 2019), a recent off-policy algorithm for learning maximum entropy policies, where we use the implementation of the authors4 5; and Actor-Critic using Kronecker-Factored Trust Region (ACKTR) (Wu et al., 2017), as implemented by OpenAI’s baselines repository 6. Each task is run for at least 1 million time steps and the average return of 15 episodes is reported every 5000 time steps. To enable reproducibility, each experiment is conducted on 10 random seeds of Gym simulator and network initialization. Results of the best performing agent of the two across different methods are reported in Figure (5).

heading: D TRAINING DETAILS
text: D.1 GENERAL CONFIGURATIONS
We use a buffer-size of 106 entries and a batch-size of 1024. We collect 100 transitions by interacting with the environment for each learning update. For all tasks in our hyper-parameter searches, we train the agents for 15, 000 episodes of 100 steps and then re-train the best configuration for each algorithm-environment pair for twice as long (30, 000 episodes) to ensure full convergence for the final evaluation. We use a discount factor γ of 0.95, an influence importance temperature λ of 0.1, and a gradient clipping threshold of 0.5 in all experiments unless otherwise specified. Each cloned critic is updated 4 time per step.
D.2 SPARSE PUSH BOX AND SPARSE SECRET ROOM, MAPE, & GYM
We use the Adam optimizer (Kingma & Ba, 2014) to perform parameter updates. All models (actors, critics and proxy critics) are parametrized by feedforward networks containing two hidden layers of 128 units excpet for the autoencoder network where we use 7 hidden layers with dimensions (128, 64, 12, 3, 12, 64, 128), respectively. All models’ parameters are initialized using Glorot Initialization method (Glorot & Bengio, 2010); while the autoencoder’s parameters are initialized using Kaiming method (He et al., 2015). We employ the Rectified Linear Unit (ReLU) as activation function and layer normalization (Ba et al., 2016) on the pre-activations unit to stabilize the learning.
The architecture of all agent networks is a DRQN (Hausknecht & Stone, 2015) with a recurrent layer comprised of a GRU with a 64-dimensional hidden state, with a fully-connected layer before and after. All neural networks are trained using RMSprop (α = 0.99 with no weight decay or momentum) with learning rate 5× 10−4.

Review summaries:
This paper introduces a new exploration method for cooperative multi-agent reinforcement learning (MARL), which utilizes influence-based regularization and curiosity-driven incentives to encourage coordinated and diverse exploration. This paper formulates the dissimilarity between other agents' behaviors and their one-step TD targets as the influence metric and extends the random network distillation (RND) to the multi-agent setting for crafting a "novelty" metric. Empirical results show that this method achieves improved performances on a comprehensive set of challenging tasks.

This paper introduces the idea of estimating the influence an agent has on other agents' actions, in order to achieve better coordination among agents. An agent is chosen as the influencer, which estimates the gap between other agents' actions and their targets given its current action. The influencer is encouraged to minimize this gap to lead other agents closer to their target returns. The paper also proposes to learn an intrinsic reward for each agent to encourage agents to learn more diverse team behaviour. The proposed method was tested in a wide range of multi-agent tasks. 

This paper introduces two techniques for Centralized Training with Decentralized Execution (CTDE) MARL. Specifically: (1) It proposes an "influence" training objective by which one agent is encouraged to help the other agents reach target returns. (2) It introduces intrinsic motivation and intrinsic cost terms aimed at encouraging efficient joint exploration of the Markov game. It then goes on to give several empirical comparisons with baselines, showing the utility of the approach in Starcraft Multi-Agent Challenge (SMAC), two sparse reward settings, Multi-Agent Particle Environments, and OpenAI Gym continuous control environments. It also performs an ablation study in (SMAC), demonstrating the usefulness of each component of the proposed method.

This paper is situated in the context of CTDE for cooperative MARL. The paper proposes new forms of intrinsic rewards to improve multi-agent exploration and a policy regularization term for an agent to have more influence over others. Experiments were conducted on existing benchmarks, such as StarCraft micromanagement and scenarios in the multi-agent particle environment, and two sparse-reward gridworld settings designed by the authors. The proposed method was compared with selected MARL baselines and ablations.