Exploration via Joint Policy Diversity for Sparse-Reward Multi-Agent Tasks

1 Introduction

Multi-agent reinforcement learning (MARL) is an increasingly important field. Many real-world problems [Swamy et al., 2020; Bazzan, 2009] are naturally modeled using MARL technology. To address MARL problems, many works [Rashid et al., 2018; Lowe et al., 2017] have been proposed. Although these works have made significant progress on challenging MARL tasks, they all focus on dense reward multi-agent cooperation scenarios. However, in many realworld scenarios, rewards extrinsic to agents are extremely sparse [Pathak et al., 2017].

To enable agents to handle these sparse-reward scenarios well, studies on how to improve the ability of agents to explore environments are essential. Many great works [Jin et al., 2018; Hazan et al., 2019; Xu et al., 2021] have been proposed in RL. However, recent studies [Liu et al., 2021; Ryu et al., 2022; Mahajan et al., 2019] experimentally show that classical exploration methods, such as count-based exploration [Strehl and Littman, 2008; Jin et al., 2018] and variants [Burda et al., 2018b; Bellemare et al., 2016] which extend these methods to high-dimensional state spaces, do not work well in MARL scenarios when agents are parameterized by neural networks. They believe this is caused by complex dynamics between agents and the huge exploration space in MARL scenarios that amplify the vulnerability of these classical methods when encountering neural networks.

To handle the issue, some exploration methods [Wang et al., 2019; Zheng et al., 2021; Chenghao et al., 2021] for multi-agent tasks have been proposed. For example, [Wang et al., 2019] proposes an exploration bonus by preferring states that can affect transitions. [Zheng et al., 2021] propose a better estimate of the uncertainty of the state for MARL to calculate bonuses. Overall, most of these methods enhance exploration by making better use of state-level information. However, relying only on exploration bonuses based on statelevel information is not sufficient to achieve efficient exploration [Rashid et al., 2019].

To this end, this work studies how other information can be used to encourage exploration. We note that our goal is to make agents to learn policies that can solve a given task. Motivated by this, a natural question is whether policy-level information is helpful for exploration. In this paper, we focus on using policy-level information (i.e., joint policy diversity), to enhance classical exploration methods based on state-level information, such as count-based exploration. Specifically, we force agents to choose different behaviors compared to the previous episodes by maximizing the difference between the current joint policy and previous joint policies. The difference is measured by the proposed unbalanced diversity measurement. It is important to highlight that unconstrained optimization of the differences between joint policies does not necessarily improve exploration. Due to the huge joint policy space, this is likely to encourage agents to learn a different, yet unhelpful joint policy for exploration (e.g., always staying in a state). To this end, we propose a filtering-based exploration constraint to force agents to optimize their joint policy in the direction that improves exploration.

We empirically evaluate the proposed method on three challenging environments: a discrete version of the multiple-

Normalized Speedup in MPE (Sparse)

particle environment (MPE) [Wang et al., 2019], the Google Research Football [Kurach et al., 2020] and StarCraft II micromanagement (SMAC) [Samvelyan et al., 2019]. In all experiments, we consider the sparse-reward setting. This means that agents get rewards only when they complete a given task. We show that our method significantly outperforms the stateof-the-art baselines on almost all tasks (RQ1 in Sec. 5.1). Fig. 1 shows a normalized sample size to achieve a success rate above 50% with respect to our method. Moreover, to our best knowledge, on some hard tasks such 3s vs 5z, our method is the first to learn winning strategies without domain knowledge under the sparse-reward setting. To better understand the exploration behaviors of the proposed method, we present extensive experiments in the reward-free setting. Results show that our method, which is on top of a classical bonus-based method (i.e., count-based method), can explore significantly more states compared to the classical method (RQ2 in Sec. 5.2).

In summary, we make three contributions: (i) We propose a novel method to enhance classical exploration methods based on state-level information by using policy-level diversity for sparse-reward multi-agent tasks; (ii) We propose a constrained joint policy diversity to measure the difference between current joint policy and previous joint policies; and (iii) Our method significantly outperforms the state-of-the-art methods on three challenging benchmarks under the sparsereward setting, including MPE, GRF, and SMAC.

2 RelatedWork

Many exploration techniques have been studied for singleagent deep reinforcement learning problems. Among them, two types of bonus-based methods are the most popular. One type is count-based methods which encourage agents to visit novel states [Strehl and Littman, 2008; Bellemare et al., 2016]. The other class of methods relies on prediction errors for problems related to the agent's transitions [Pathak et al., 2017; Burda et al., 2018a; Burda et al., 2018b; Badia et al., 2020]. However, these methods focus on how to better estimate the state uncertainty in the high-dimensional state space. Recent studies [Mahajan et al., 2019; Wang et al., 2019; Liu et al., 2021] experimentally show that these methods do not work well in MARL scenarios which have larger exploration spaces and complex dynamics between agents.

Recently, some exploration methods designed for multiagent scenarios have been proposed. EITI and EDTI [Wang et al., 2019] capture the influence of one agent's behaviors on others, and agents are encouraged to visit states that will change other agents' behaviors. More recently, EMC [Zheng et al., 2021] uses prediction errors of individual Q-values as intrinsic rewards for exploration. CDS [Chenghao et al., 2021] maximizes the mutual information between agents' identities and their trajectories to encourage extensive exploration. In summary, these methods introduce some heuristic principles to make better use of state-level information. In contrast, our work focuses on policy-level information.

More recently, some researchers have turned to other technical lines to improve exploration in MARL scenarios. CMAE [Liu et al., 2021] proposes a goal-conditioned exploration method that can cleverly use domain knowledge. [Zhang et al., 2021] uses a learned centralized environmental model to replace the real environment, thus improving sample efficiency. [Ryu et al., 2022] uses a powerful simulator to modify the distribution of initial states, making agents more likely to find rewards. However, all of these methods have some insurmountable issues, such as the difficulty of obtaining domain knowledge and the accuracy of the learned model. In contrast, our work is a bonus-based method that does not depend on domain knowledge or a learned model.

3 Preliminaries

A cooperative multi-agent task is modeled as a multi-agent Markov decision process (MDP). An n-agent MDP is defined by a tuple (S,A,P,R,Z,O, n, γ,H). S is the state space. A is the action space of each agent. At each time step t, each agent's policy πi , i ∈ N ≡ {1, . . . , n}, selects an action ait ∈ A. All selected actions form a joint action at ∈ An . The transition function P : S×An → ∆(S) maps the current state st and the joint action at to a distribution over the next state st+1. All agents receive a collective reward rt ∈ R according to the reward function R : S ×An → R. The objective of all agents' policies is to maximize the collective return ∑Ht=0 γ t rt, where γ ∈ [0, 1] is the discount factor, H is the

Normalized Speedup in SMAC (Sparse)

horizon, and rt is the collective reward obtained at timestep t. Each agent i observes local observation oit ∈ Z according to the observation function O : S × N → Z. All agents' local observations form a full observation ot. All agent's policy πi form a joint policy π : On → ∆(An ). In this paper, we follow the standard centralized training with decentralized execution paradigm (CTDE) [Rashid et al., 2018].

4 Method

In this section, we present a novel exploration method for sparse-reward multi-agent tasks. The proposed method exploits information from the joint policy level to improve classical count-based methods [Strehl and Littman, 2008; Burda et al., 2018b], which are based on state uncertainty and do not work well with neural networks. An overview of the proposed method is given in Fig. 2.

4.1 Joint Policy Diversity

One possible solution to use information from the joint policy level to drive exploration is to encourage diversity between joint policies. Specifically, in the k-th parameter update, we optimize the current joint policy πθ with the constraint that πθ is distinct from previous joint policies (i.e., π1, · · · ,πk-1). To implement this idea, a natural choice is using KL-divergence to measure the distance between joint policies. Formally, the distance is defined by

However, there are several issues in Eq. 1. The first issue is that KL-divergence is not suitable in our setting. The accumulative KL-divergence of a trajectory is defined as

where H(πθ,πj) is the cross-entropy between πθ and πj, and H(πθ) is the entropy of πθ. As shown in the above derivation, using KL-divergence as the distance measure would inherently encourage learning a joint policy with small entropy H(πθ), which is undesirable in our problems since a low entropy joint policy is harmful for exploration. Thus, we ignore H(πθ) in Eq. 2. In other words, we choose to use Cross-Entropy instead of KL-divergence. Formally, the distance based on the cross-entropy is defined as

The second issue is that, to calculate Eq. 3, we need to calculate the distance between the current joint policy and the previous k - 1 joint policies at the k-th parameter update. As the training process continues, we need to consider a large number of previous joint policies, which leads to an unacceptable consumption of computational resources. Consequently, we introduce a joint policy mixture πmix which is the average of all previous joint policies. Formally, in the k-th parameter update, the joint policy mixture πmix is defined as

Then, according to Jensen's inequality, we have

The above inequality tells us that the cross-entropy between the current joint policy πθ and the joint policy mixture πmix is a lower bound of the original optimization objective Jce(πθ). Thus, we can optimize the original objective by maximizing this lower bound which has a moderate computational cost. In this paper, we get a joint policy mixture πmix by using past joint action/observation histories to train networks. Details of implementation are given in supplementary material.

Next, we discuss how to further modify Eq. 5. In our setting, agents are expected to choose actions that were less frequently chosen before, which is helpful for exploration. Therefore, we propose an Unbalanced Cross-Entropy by adding a penalty term into the original cross-entropy. For an observation-action pair (ot, at) from a joint policy πθ and a policy mixture πmix, when the probability πmix(at|ot) is higher than a fully random joint policy πrand (i.e., selecting each joint action with the same probability), the penalty term will reduce the contribution of the observation-action (ot, at) pair to the distance. Formally, the unbalanced cross-entropy is defined as

where I[·] denotes an indicator function and β ∈ (0, 1] is a penalty factor. The unbalanced cross-entropy Huce(πθ, πmix)

recovers the original cross-entropy H(πθ,πmix), when β is set to 1.

To calculate the distance in Eq. 6, we need to estimate the joint action probability. To this end, we use an auto-regressive form [Fu et al., 2022] to represent a joint policy mixture πmix(a|o). Given an execution order X = {x1, · · · , xn}, we can factorize a joint policy πmix(a|o) into the form of

where πxi θxi is the xi-th agent. In this way, we can obtain an estimate of the joint action probability without directly learning a joint policy.

In summary, we use the joint policy diversity

which is based on the auto-regressive form, the joint policy mixture, and unbalanced cross-entropy to drive exploration.

4.2 Filtering-based Exploration Constraint

Maximizing ̂ J ar uce (πθ) increases the joint policy diversity and thus helps agents to find a new joint policy that is different from previous joint policies. However, not all joint policies in the joint policy space are helpful for exploration. For example, under the guidance of diversity, agents will even learn a new joint policy that always stays in a certain state. This case may happen as long as the new joint policy differs from the previous ones. Obviously, such joint policies would waste opportunities that could be used to explore new states. To this end, it is necessary to add constraints when maximizing ̂ J ar uce (πθ). One natural way is to consider in Eq. 8 the effect of each observation-action (ot, at) pair on the exploration, i.e, the uncertainty (or novelty) of st+1. Therefore, we modify Eq. 8 as follows

where d(ot, at) = log 1 πmix(at|ot) + I[ πrand(at|ot) πmix(at|ot) ≤ 1] log β, and u(st+1) is the uncertainty of st+1.

However, the constraint is too mild, and agents can still get positive incentives from Eq. 9 by visiting states with low uncertainty u(st+1). To this end, we introduce a filteringbased exploration constraint

where cu is a hyperparameter that controls the strength of the constraint. Compared to Eq. 9, the above constraint is stronger, and agents can only get positive incentives when they visit states with uncertainty not less than cu. In general, by combining the joint policy diversity with the exploration constraint, we encourage agents to find a new joint policy that is helpful for exploration.

We maximize ̂ J ar fec,uce (πθ) by using the bonus bjpd(ot, at) which is defined as

4.3 Overall Exploration Bonus

In this section, we introduce the final augmented reward ˆ r, which includes the extrinsic reward r, the bonus bjpd based on the constrained joint policy diversity, and the bonus bcls which is the classical exploration bonus based on state uncertainty. In this paper, we use easy-to-implement count-based bonus as our bcls = 1/√Ncntr(st+1), where Ncntr(·) stands for the state visit count. For simplicity, we replace u(st+1) in Eq. 11 with bcls. For continuous state tasks, such as SMAC, we use RND [Burda et al., 2018b] to estimate bcls. We use the addition operation that is widely used in the literature [Zha et al., 2021; Wang et al., 2019] to combine bjpd and bcls. Formally, the final augmented reward received by agents at each timestep is defined as

where w1 and w2 are hyperparameters.

5 Experiments

The experiments are designed to answer the following research questions: RQ1: how is our method compared with the state-of-the-art exploration methods on multi-agent benchmarks in the sparse-reward setting (Sec. 5.1)? RQ2: how will our method explore environments without extrinsic rewards (Sec. 5.2)? RQ3: how important each component is in our method (Sec. 5.3)? We evaluate our method on three challenging environments: (1) a discrete version of the multiple-particle environment (MPE) [Liu et al., 2021]; (2) the StarCraft II micromanagement (SMAC) [Samvelyan et al., 2019]; and (3) the Google Research Football (GRF) [Kurach et al., 2020]. In all environments, we consider the sparse-reward setting. All experiments run with five random seeds. Details for environments and training are given in supplementary material.

Experimental Setup. In MPE, following previous works [Wang et al., 2019; Liu et al., 2021], we consider three standard tasks: Push Box, Pass, Secret Room. We also consider other challenging tasks: Room, Large Push Box and Large Pass. In all tasks, agents see a positive reward only when they complete the given task. In SMAC, we consider six standard tasks: 2m vs 1z, 3m, 8m, 3s vs 4z, 3s5z, and 3s vs 5z. We consider the sparse reward setting, which means agents see a positive reward only when all enemies are taken care of. In GRF [Kurach et al., 2020], following previous work [Chenghao et al., 2021], we consider three tasks: 3 vs 1 with keeper, counterattack easy, and counterattack hard. In GRF tasks, only scoring leads to rewards.

Baselines. We consider several baselines. Following previous works [Liu et al., 2021; Wang et al., 2019], we first consider QMIX [Rashid et al., 2018] which is a popular value-based method for MARL, and COUNT which includes a classical count-based bonus [Strehl and Littman, 2008] on top of QMIX. Then, we consider recently proposed methods: CMAE [Liu et al., 2021] utilizes domain knowledge and learns an exploration policy by selecting goals from many restricted spaces; EITI and EDTI [Wang et al., 2019] capture the influence of one agent's behaviors on others; EMC [Zheng et al., 2021] uses prediction errors of individual Q-values as intrinsic rewards for exploration; CDS [Chenghao et al., 2021] introduces diversity between agents to encourage extensive exploration. In SMAC andGRF, the countbased bonus and our bcls are approximated by RND [Burda et al., 2018b]. Our method is based on COUNT and introduces additional constrained joint policy diversity.

5.1 Experiments on StandardMulti-agent Tasks

Results on MPE. We first compare our method with baselines on MPE tasks. The training curves are included in Fig. 3. The results of CMAE are obtained using the publicly available code released by the authors. EITI and EDTI, which need to learn dynamics, both fail in all tasks. CMAE which utilizes domain knowledge is the state-of-the-art method in sparse-reward MPE. We observe that CMAE can learn winning strategies on simple tasks but the performance is unstable, while on difficult tasks CMAE fails. As we expected, COUNT which combines with a count-based exploration bonus can solve easy tasks, but does not perform well on hard tasks. Our method which introduces constrained joint policy diversity on top of COUNT shows amazing sample efficiency on all tasks. Compared to COUNT, our method solves tasks faster on all tasks, which confirms the importance of constrained joint policy diversity. Compared to CMAE, our method achieves comparable performance on some tasks (e.g., Secret Room), and our method still achieve good performance on other tasks (e.g., Large Pass) where CMAE fails. This demonstrates the stability of our method.

Results on SMAC. To further study RQ1, we evaluate our method in more challenging tasks with continuous state space. We consider the sparse reward setting, which means agents see a positive reward only when all enemies are taken care of. Since CMAE does not provide an implementation on SMAC, we get the results of CMAE from the original paper [Liu et al., 2021]. As shown in Fig. 4, QMIX which relies on random exploration fails in all tasks. And CDS, which introduces diversity between agents, also can not learn a winning strategy. RND and EMC can solve easy tasks, such as 2m vs 1z and 3m. However, as we expected, they both fail in the more challenging tasks such as 3s vs 5z which is classified as hard even in the dense-reward setting [Samvelyan et al., 2019]. In contrast, our method works well in all tasks. Specifically, on easy tasks, our method significantly outperforms RND and achieves comparable performance to EMC. In hard 3s vs 5z, to our knowledge, our method is the first to learn winning strategies without domain knowledge under the sparse-reward setting.

Results on GRF. Next, we evaluate our method on three challenging Google Research Football (GRF) offensive scenarios: 3 vs 1 with keeper, counterattack easy and counterattack hard. In GRF, all experiments follow the training settings of CDS [Chenghao et al., 2021], except that all experiments use TD(λ) to speed up training. The training curves are reported in Fig. 5. We observe that, as the difficulty of the task increases, the advantages of our method become more obvious. On easy tasks, our method slightly outperforms the state-of-the-art method CDS, but on harder tasks, our method significantly outperforms all baselines.

5.2 Exploration without Extrinsic Rewards

To study RQ2 and analyze exploration behaviors of the proposed method, we train COUNT, CMAE, Ours w/o JPD, and Ours after 1 million without extrinsic rewards. Ours w/o JPD ablates the joint policy diversity by only keeping the filteringbased exploration constraint I[u(st+1) ≥ cu]u(st+1) in Eq. 11. We first report the number of explored states and the improvement of our method compared to COUNT in Tab. 1. More explored states mean better exploration. We also report the visited state entropy in the supplementary material. We make four observations. First, our method explores more states than COUNT in all tasks, showing that the superior performance (Fig 3) in the sparse-reward setting comes from our better exploration. Second, our method outperforms Ours w/o JPD, which confirms the importance of joint policy diversity. Third, the filtering-based exploration constraint is beneficial for exploration. This may be because assigning additional bonuses to states with higher uncertainty (i.e., higher novelty) allows agents parameterized by neural networks to more easily distinguish between novel states and familiar states. Fourth, states explored by CMAE are significantly less than that of our method and COUNT. This suggests that the strong performance of CMAE in some tasks comes from its use of domain knowledge, rather than its exploration ability.

In supplementary material, we report the percentage of states with higher novelty (uncertainty greater than 0.7) in an episode. We observe that COUNT wastes many opportunities that could be used to explore new states. In contrast, our method has better exploration ability and wastes fewer opportunities.

To further understand the impact of the joint policy diversity on exploration, the joint action entropy of the joint policy mixture, which is defined in Eq. 4, is shown in Fig. 6. We first observe that the joint action entropy of our method is higher than that of Ours w/o JPD. A high joint action entropy implies that the action selection of the joint policy mixture, which consists of historical joint policies, is more uniform. This explains why our method can explore more states than Ours w/o JPD, and confirms the importance of the diversity term in Eq. 11. In addition, we also observe that the exploration constraint can slightly increase the joint action entropy. This may be a by-product of the rapid change in bonuses caused by the exploration constraint.

5.3 Ablations

To study RQ3 and further understand the proposed method, we carry out ablation studies. To confirm that our unbalanced cross-entropy is more suitable for exploration than KL-divergence, we replace the unbalanced cross-entropy in Eq. 11 with KL-divergence. As shown in Fig. 7 (left), our method is better under the reward-free setting.

Then, to study the impact of cu (Eq. 10) on exploration, we train agents with different cu under the reward-free setting. The results are reported in Fig. 7 (middle). We make two observations. First, a weak constraint (cu = 0) does not improve exploration compared to COUNT. This confirms the importance of the proposed filtering-based constraint. Second, a too-strong constraint (cu = 0.9) is also harmful. This is because it would make bjpd = 0 (Eq. 11) in most cases.

To study the impact of β in Eq. 6, we train agents with different β in 2m vs 1z under the sparse-reward setting. The results are shown in Fig. 7 (right). We make two observations. First, the unbalanced cross-entropy is significantly better than the original cross-entropy (β = 1.0). This confirms that the unbalanced cross-entropy is important for efficient exploration. Second, a too-low β (such as 0.1) also hurts sample efficiency. This is reasonable because in this case, the penalty term overwhelms the cross-entropy term.

6 Conclusion

In this paper, we focus on sparse-reward multi-agent tasks. We present a novel exploration method, which exploits both constrained joint policy diversity and classical bonus based on state uncertainty to jointly encourage exploration. We evaluate our method on three challenging environments under the sparse-reward setting. Results show that our method pushes forward state-of-the-art. One limitation of the current work is that it focuses on discrete-action tasks. In the future, we will explore the possibility of extending our method to scenarios with continuous-action space.

Acknowledgements

This work is supported in part by Basic Cultivation Fund project, CAS (JCPYJJ-22017) and the Youth Innovation Promotion Association CAS.