---
title: "Population-Based Diverse Exploration for Sparse-Reward Multi-Agent Tasks"
authors:
  - "Pei Xu"
  - "Junge Zhang"
  - "Kaiqi Huang"
doi: "10.24963/ijcai.2024/32"
url: "https://ijcai.org/proceedings/2024/32"
pdf: "https://ijcai.org/proceedings/2024/0032.pdf"
venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence"
year: 2024
pages: "283-291"
track: "Main Track"
keywords:
  - "Machine Learning: ML: Reinforcement learning"
  - "Agent-based and Multi-agent Systems: MAS: Multi-agent learning"
---

# Population-Based Diverse Exploration for Sparse-Reward Multi-Agent Tasks

Pei Xu, Junge Zhang, Kaiqi Huang

*Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 283-291. DOI: [10.24963/ijcai.2024/32](https://doi.org/10.24963/ijcai.2024/32)

## Abstract

Exploration under sparse rewards is a key challenge for multi-agent reinforcement learning problems. Although population-based learning shows its potential in producing diverse behaviors, most previous works still focus on improving the exploration of a single joint policy. In this paper, we show that with a suitable exploration method, maintaining a population of joint policies rather than one joint policy can significantly improve exploration. Our key idea is to guide each member of the population to explore different regions of the environment. To this end, we propose a member-aware exploration objective which explicitly guides each member to maximize deviation from the explored regions of other members, thus forcing them to explore different regions. In addition, we further propose an exploration-enhanced policy constraint to guide each member to learn a joint policy that is both different from other members and promotes exploration, thus increasing the probability of exploring different regions. Under reward-free setting, our method achieves 72% average improvement in the number of explored states compared to classical exploration methods in the multiple-particle environment. Moreover, under sparse-reward setting, we show that the proposed method significantly outperforms the state-of-the-art methods in the multiple-particle environment, the Google Research Football, and StarCraft II micromanagement tasks.

## Full text

## 1 Introduction

Multi-agent reinforcement learning (MARL) is an active and fast-growing field that has been applied to a wide range of real-world problems [Swamy et al., 2020; Bazzan, 2009]. To better address MARL problems, many works [Rashid et al., 2018; Yu et al., 2023b; Sun et al., 2021; Sun et al., 2024] have been proposed. Although these works have made significant progress on challenging MARL tasks, most of them focus on dense reward scenarios. However, in many real-world scenarios, rewards extrinsic to agents are extremely sparse.

∗Corresponding authors.

Figure 1: Normalized number of explored states by different methods compared to the classical count-based exploration method, averaged over six tasks in MPE [Wang et al., 2019] (higher values are better). All methods are trained with 1 million time steps under the reward-free setting (i.e., without task rewards). The number of states explored by our method is substantially higher than that of other methods. The results demonstrate the power of our method in exploration.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000000_7a9b1c8e06fbe10c56fe24cc587be3c7df2df16cc4fd6f49f2769a4b52b2ef4b.png)

To enable agents to handle these sparse-reward tasks well, studies on how to better explore environments are essential [Pathak et al., 2017]. Many great works [Wang et al., 2019; Zheng et al., 2021; Chenghao et al., 2021; Xu et al., 2023b; Liu et al., 2021] for multi-agent tasks have been proposed. However, all these methods maintain only one joint policy to explore the environment, while recent works [Chenghao et al., 2021; Parker-Holder et al., 2020; Jianye et al., 2022; Khadka and Tumer, 2018] show that maintaining a population of joint policies with different initialization parameters can produce a diverse set of behaviors.

This implies that maintaining a population of joint policies, rather than one joint policy, might improve the efficiency of exploration, if we can devise a smart method to guide each joint policy in the population to explore different parts of the environment. This topic has been preliminarily studied by works from both evolutionary reinforcement learning [Khadka et al., 2019] and population-based reinforcement learning [Eysenbach et al., 2018]. However, these works either rely solely on noise-based parameter perturbations [Khadka and Tumer, 2018] or simply encourage behavioral diversity [Parker-Holder et al., 2020], and thus can only handle simple tasks. To our knowledge, it is still unclear how to improve exploration by maintaining a population in sparsereward multi-agent tasks that have huge exploration spaces.

In this paper, we present a novel exploration method which encourages diverse exploration between members of a population. Specifically, we propose a member-aware exploration objective, which explicitly guides each member to maximize deviation from the explored regions of other members, thus forcing them to explore different regions. In addition, we further propose an exploration-enhanced policy constraint, which guides each member to learn a joint policy that is both different from other members and promotes exploration, thus increasing the probability of exploring different regions.

We empirically evaluate the proposed method on three challenging environments: a discrete version of the multipleparticle 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. 4.1). To better understand the exploration behaviors, we present extensive experiments in the reward-free setting. Results show that our method, which encourages diverse exploration between members of a population, can explore significantly more states compared to other methods (RQ2 in Sec. 4.2). Fig. 1 shows normalized number of explored states for each method trained without task rewards in MPE.

In summary, we make three contributions: (i) We propose a novel method that maintains a population of joint policies to improve exploration for sparse-reward multi-agent tasks; (ii) We propose a member-aware exploration objective and an exploration-enhanced policy constraint to guide each member to actively explore different parts of the environment; 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 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 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 [Rashid et al., 2018].

## 3 Method

In this section, we present a novel exploration method for sparse-reward multi-agent tasks. Our key idea is to maintain a population of joint policies, and then guide each member of the population to explore different regions. To achieve this, we propose a new member-aware exploration objective that guides each member to maximize deviation from the explored regions of other members. In addition, we also propose an exploration-enhanced policy constraint, which guides each member to learn a joint policy that is both different from other members and promotes exploration, thus increasing the probability of exploring different regions.

## 3.1 Member-Aware Exploration Objective

One natural solution to encourage exploration in a population is to directly use classical exploration techniques by treating members of a population as a whole. For example, if we use provably efficient maximum state entropy exploration methods [Hazan et al., 2019] and maintain a population that contains M members Π = {π1, · · · , πM}, parameterized by Θ = {θ1, · · · , θM}, then the vanilla exploration objective for i-th member can be defined as

<!-- formula-not-decoded -->

where s is a state sampled from a population Π, dΠ is a state distribution induced by the population Π, and H(·) is the Shannon entropy based on a state distribution. According to [Hazan et al., 2019; Zhang et al., 2021], the bonus bvan(st, at, st+1|θi) for i-th member derived from Eq. 1 with respect to dΠ is

<!-- formula-not-decoded -->

Eq. 2 encourages exploration by requiring the overall state distribution dΠ to be as uniform as possible.

The main issue in the vanilla Eq. 1 and Eq. 2 is that it is a member-unaware exploration objective, which only cares about the overall exploration, not the specific exploration of each member, making it difficult to guide each member to explore different regions. Fig. 2 gives an example to show the inability of Eq. 1 to encourage diverse exploration. We can see that each member in Distribution B has diverse explored regions, and the explored regions of each member in Distribution A are the same. Although Distribution B is more diverse than Distribution A for each member, Eq. 1 treats the two distributions equally. This indicates that the vanilla objective fails to achieve the diverse exploration we desire.

To achieve diverse exploration between members which guides each member to explore different regions, we propose a new member-aware exploration objective, which explicitly guides each member to maximize deviation from the explored regions of other members. Formally, the proposed objective for i-th member can be defined as:

Figure 2: The mechanism of our member-aware exploration objective. Two state distributions, A and B. In state distribution A, each member has the same state distribution and visits each state c times. In state distribution B, each member explores a different state and visits the corresponding state 3c times. Since distributions A and B have the same overall state distribution dΠ induced by the population, the vanilla exploration objective (Eq. 1) gives them the same value. In contrast, our member-aware exploration objective (Eq. 3) favors diverse exploration between members and gives a larger value for distribution B (19.1, ϵ = 10-8 ) than for distribution A (2.2).

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000001_04a65f4ffc9a2603bac5d0c51c802e30a506d2cde935281274d09b40a64e5c4e.png)

<!-- formula-not-decoded -->

where dπi is a state distribution induced by the member πi, DKL(·, ·) is KL-divergence, and H(·, ·) is cross-entropy. ρπi is a mixing of state distributions of other members:

<!-- formula-not-decoded -->

where ϵ is a very small constant to ensure ρπi (s) &gt; 0 for any state s. For i-th member, we derive the bonus bsd(st, at, st+1|θi) from Eq. 3 with respect to dπi :

<!-- formula-not-decoded -->

Based on the above derivation, two points should be highlighted. First, compared to vanilla Eq. 1 which only considers the overall state distribution induced by the population, our new objective (Eq. 3) explicitly encourages diverse exploration between members by considering the state distribution of each individual member. To show the difference between our objective and the vanilla Eq. 1 more clearly, let us consider the example in Fig. 2 again. In this example, only Distribution B can maximize the new objective, whereas both Distribution A and Distribution B can maximize the vanilla objective. Moreover, we show in supplementary material that the solution that maximizes the sum of all members of Eq. 3 also can maximize Eq. 1. This indicates that our new objective requires not only that a population explore the environment uniformly, which is consistent with the classical exploration objective (Eq. 1), but also that the exploration of each member is diverse.

Second, compared to previous population-based works [Parker-Holder et al., 2020; Eysenbach et al., 2018; Sharma et al., 2019], the proposed objective not only encourages each member to explore different regions (the first term), but also requires each member to cover as much of the state space as possible (the second term), which was neglected in these previous works. Without the second term H(dπi ), the most easily learned optimal strategy of the i-th member is to always stay in a single state that has not been visited by any other member. In contrast, with the second term, it is easy to check that the maximizer of Eq. 3 is dπi ∝ 1/ρπi . This means that the optimal strategy of i-th member is to actively explore regions that other members are less likely to explore. Obviously, this optimal strategy is more suitable for exploration.

## 3.2 Exploration-Enhanced Policy Constraint

In the previous subsection, we discuss how differences in state distributions between members can be used to encourage diverse exploration, and thus propose Jsd(θi). In this subsection, we propose an exploration-enhanced policy constraint Jpd(θi), which considers policy differences between members, as a supplement to Jsd(θi). In particular, we encourage each member to learn a joint policy that is both different from other members and promotes exploration, thus increasing the probability of exploring different regions. Formally, in the kth parameter update, for i-th member, we optimize the current joint policy πi,k-1 by

<!-- formula-not-decoded -->

Figure 3: Comparison of our method against baseline methods on MPE across five runs. Our method significantly outperforms all others.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000002_232f7f393dd70b0287d965315c6a41fd359c24b6d6db859ade7f6058b38960e2.png)

where Π1 = {{πm,1}Mm=1,m̸=i , · · · , {πm,k-1}Mm=1,m̸=i} are current and historical joint policies of other members, and Π2 = {πi,1, · · · ,πi,k-2} are all previous joint policies of ith member.

Similar to previous work [Parker-Holder et al., 2020], Eq. 6 also forces the joint policy of each member to be different from that of other members (first term). However, our aim is effective exploration, not just a diverse population. So, we further force each member to learn an exploration-enhanced joint policy, which prefers actions that were less likely to be chosen by previous joint policies (second term) and also has a high degree of randomization (third term). The latter two terms increase the probability of each member visiting new states.

In order to maximize Eq. 6, we need to consider all previous joint policies of all members, which leads to a very high consumption of computational resources. To alleviate this problem, we introduce a joint policy mixture πmix which is the average of all discovered joint policies. Formally, in the k-th parameter update, the joint policy mixture πmix is defined as

<!-- formula-not-decoded -->

We show in supplementary material that the following inequality holds:

<!-- formula-not-decoded -->

The above inequality tells us that ̂ Jpd(θi) is a lower bound of the original Jpd(θi). Thus, we can optimize the original policy constraint 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.

We maximize ̂ Jpd(θi) by using the bonus bpd(ot, at, ot+1|θi) which is defined as

<!-- formula-not-decoded -->

## 3.3 Overall Exploration Bonus

In this section, we introduce the final augmented reward ˆ r, which includes the task reward r, the bonus bsd based on differences in state distributions between members, and the bonus bpd based on policy differences between members. For discrete state tasks, such as MPE [Wang et al., 2019], we use empirical counts to estimate the state distribution dπi . For continuous state tasks, such as SMAC [Samvelyan et al., 2019] and GRF [Kurach et al., 2020], we follow previous works [Seo et al., 2021; Liu and Abbeel, 2021] and use the particle-based k-nearest neighbors entropy estimator [Singh et al., 2003] to estimate the state distribution dπi . We use the addition operation that is widely used in the literature [Wang et al., 2019] to combine bsd and bpd. Formally, the final augmented reward received by agents at each timestep is defined as

<!-- formula-not-decoded -->

where w1 and w2 are hyperparameters.

The exploration abilities of different members may vary due to the task structure and the randomness of the optimization process. To this end, we use a dynamic member selection that gives members with better exploration more chances to interact with the environment, thus further improving exploration efficiency. Specifically, we assign a sampling probability based on the average augmented rewards of last L episodes for each member. According to the probabilities, we sample a member to interact with the environment before the start of each episode.

Figure 4: Comparison of our method against baselines on the sparse-reward version of SMAC across five runs.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000003_67dd84b72d40ed5d405e11123f645ca3e0684d469dcbe7a50a9011f8383e4c9a.png)

Figure 5: Comparison of our method against baselines on the sparse-reward version of Google Research Football across five runs.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000004_a5c4c796350ad166688dbc0a9ee2e05cd127eef18e17d11318423e8ff27739b8.png)

## 4 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. 4.1)? RQ2: how will our method explore environments without task rewards (Sec. 4.2)? RQ3: how important each component is in our method (Sec. 4.3)? We evaluate our method on three challenging environments: (1) a discrete version of the multipleparticle 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. Experiment details are given in supplementary material.

Experimental Setup. In MPE, following previous works [Wang et al., 2019; Xu et al., 2023b], we consider six standard tasks: Push Box, Pass, Secret Room, 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: 3m, 3s vs 4z, 5m vs 6m, 8m vs 9m, 3s5z, and 6h vs 8z.

We consider the sparse reward setting, which means agents see a positive reward only when all enemies are taken care of. In GRF, 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. Following previous works [Liu et al., 2021; Wang et al., 2019], we first consider QMIX [Rashid et al., 2018] which is a popular method for MARL, and COUNT which includes a classical count-based bonus on top of QMIX. Then, we consider recently proposed methods: EITI [Wang et al., 2019] captures 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; CMAE [Liu et al., 2021] utilizes domain knowledge to find task rewards; SAME [Xu et al., 2023b] encodes task structures into exploration. We also consider classical population-based methods: ERL [Khadka and Tumer, 2018] which maintains a population of evolutionary algorithm agents, and DvD [Parker-Holder et al., 2020] which maintains a population of RL agents and encourages diversity among members.

Figure 6: The normalized number of explored states for each method trained without task rewards. A higher number is better for exploration. Our method is superior to previous works in all tasks.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000005_a8e49011a8c55d47f5e44f404532d6eea039374a825b7ad03af0423c96fbcd13.png)

## 4.1 Experiments on StandardMulti-agent Tasks

Results on MPE. To study RQ1, we report the training curves on MPE tasks in Fig. 3. EITI which needs to learn dynamics, fails in all tasks. SAME which encodes task structures into exploration is the state-of-the-art method in sparsereward MPE. Compared to SAME, our method solves tasks faster on almost all tasks, which confirms that maintaining a population is important for exploration. In addition, DvD which encourages the vanilla policy diversity among members of the population is better than ERL which maintains a population of noise-based agents for exploration. More importantly, our method which combines a member-aware exploration objective and an exploration-enhanced policy constraint, is significantly better than DvD. These suggest that a smart mechanism to guide the behaviors of members of a population is the key to efficient exploration.

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. As shown in Fig. 4, QMIX which relies on random exploration, fails in all tasks. CDS, which introduces diversity between agents, also can not learn a winning strategy. RND and EMC can only solve easy tasks, such as 3m. The state-of-the-art method SAME shows strong performance in hard tasks, such as 5m vs 6m, but fails in more hard tasks. In contrast, our method works well in all tasks. Specifically, on easy tasks, our method outperforms classical RND and achieves comparable performance to SAME. On more hard tasks, our method shows overwhelming superiority.

Results on GRF. Next, we evaluate our method on three challenging Google Research Football (GRF) offensive scenarios. 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-ofthe-art method SAME, but on harder tasks, our method significantly outperforms all baselines.

Figure 7: Visitation maps of different members of a population for DvD+COUNT (top) and Ours (bottom). Brighter areas correspond to more visits. In this task, agents are placed in the left room and required to explore the right three rooms. Compared to the vanilla method, our method shows diverse exploration, i.e., different members explore different rooms on the right.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000006_be94b4aaddbb0bb2788eefd68376b5df4f1af96858c7f8d60e2ced5301e01629.png)

## 4.2 Exploration without Task Rewards

To study RQ2, we train COUNT, CMAE, SAME, ERL, DvD, and Ours after 1 million without task rewards. Each method runs with five random seeds. We first report the normalized number of explored states (compared to COUNT method) in Fig. 1 and Fig. 6. We also report the exact number of explored states in the supplementary material. We make three observations. First, our method explores more states than all other methods in all tasks, showing that the superior performance in the sparse-reward setting comes from our better exploration. Specifically, compared to the classic COUNT method, our method obtains 99%, 95% and 94% improvement on Secret Room, Pass and Large Push Box tasks, respectively. On Push Box, Room and Large Pass, our method gets 83%, 34% and 25% improvement, respectively. Second, our method outperforms DvD+COUNT which is a classic population-based method, confirming our memberaware exploration objective and exploration-enhanced policy constraint are important for exploration. Third, ERL which maintains a population of noise-based agents is even worse than COUNT. This suggests that simply maintaining a population does not improve exploration without a good mechanism to guide the behaviors of members.

To further understand the exploration behaviors of the proposed method, we show the heatmaps of visitation counts (brighter areas correspond to more visits) of each member under the Secret Room task in Fig. 7. In this task, the room on the left is easy to explore and the three rooms on the right are hard to explore. Unsurprisingly, in our method, different members pay attention to different rooms on the right. This shows that our method can guide each member to explore different regions, while the previous classical population-based method fails.

Figure 8: Ablation studies for the population size M.

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000007_42ad5824eb3f009e4174016bc0d38f08c72731e984de3d4e13411118d721a319.png)

![Image](https://ijcai.org/proceedings/2024/fulltext/32/image_000008_485050c3dcba0fe059a4f3e523b6f62cf26d493535919e879a8e260bde8c631d.png)

## 4.3 Ablations

To study RQ3, we carry out ablation studies. To study the impact of the population size M on exploration, we train agents with different M under the reward-free setting. Fig. 8 (left) shows the joint action entropy of the joint policy mixture, which is defined in Eq. 7. A high joint action entropy implies that the action selection of the joint policy mixture, which consists of historical joint policies, is more uniform and is considered good for exploration [Mnih et al., 2016]. Fig. 8 (right) shows the corresponding normalized number of explored states. Three points should be highlighted. First, it is important to choose a suitable population size, not only to maintain high joint action entropy, but also to explore more states. Second, our method with M &gt; 1 achieves a significant improvement, suggesting that maintaining a population is important for efficient exploration. Third, our method with M = 1 is still better than COUNT, showing the validity of the proposed exploration-enhanced policy constraint.

To study the importance of each component in our method, we carry out ablation studies in Secret Room and 3m. 'w/ van-Obj' ablates our member-aware exploration objective by replacing Eq. 3 with Eq. 1. 'w/ van-PC' ablates the exploration-enhanced policy constraint by only considering the first term in Eq. 6. 'w/o Dy' ablates the dynamic member selection by uniformly sampling members. Fig. 9 (right) shows the normalized number of explored states in Secret Room under the reward-free setting. Fig. 9 (left) shows the task performance in 3m. We make three observations. First, ignoring any component can hurt exploration and task performance, which confirms the importance of each component. Second, in hard-to-explore tasks, such as Secret Room, the proposed member-aware exploration objective has the most significant impact on exploration. Third, in easy-to-explore tasks, such as 3m, the dynamic member selection has the greatest impact on performance. This is reasonable, as sampling each member uniformly in easy-toexplore tasks tends to cause duplication of exploration.

## 5 RelatedWork

With the development of deep learning [Krizhevsky et al., 2017; Chen et al., 2024b; Chen et al., 2024a; Xu et al., 2018], many exploration techniques [Bellemare et al., 2016; Pathak et al., 2017; Burda et al., 2018; Xu et al., 2022] have been studied for single-agent deep reinforcement learning problems. However, recent studies [Wang et al., 2019;

Figure 9: Ablation studies for each component in our method.

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 [Wang et al., 2019; Liu et al., 2021; Xu et al., 2023a; Yu et al., 2023a; Devidze et al., 2022; Ramamurthy et al., 2020] designed for multiagent scenarios have been proposed. 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 exploration. SMAE [Xu et al., 2023b] encodes task structures into exploration. However, these methods keep a single joint policy for exploration. In contrast, our work focuses on improving exploration by maintaining a population of joint policies.

Studies [Khadka and Tumer, 2018; Pourchot and Sigaud, 2018; Khadka et al., 2019; Jianye et al., 2022; Majumdar et al., 2020; Tao et al., 2020; Aydeniz et al., 2023] from evolutionary reinforcement learning also maintain a population. They focus on how to better combine evolutionary algorithms and RL, so most of them use noise-based parameter perturbations for exploration. However, noise-based exploration is inefficient [Taiga et al., 2019] for sparse-reward tasks.

Population-based reinforcement learning is another related field. Works [Parker-Holder et al., 2020; Eysenbach et al., 2018] from this field focus on increasing the diversity of a population rather than exploring new states. In contrast, our work systematically and deeply considers various factors affecting exploration, and therefore shows an overwhelming performance advantage in experiments.

## 6 Conclusion

In this paper, we focus on sparse-reward multi-agent tasks. We propose a novel method to improve exploration by guiding each joint policy of a population to explore different regions of the environment. We evaluate our method in three challenging environments under the sparse-reward setting. Results show that our method pushes forward state-of-the-art. One limitation of this work is that each member's interaction with the environment runs sequentially, which prevents our method from fully utilizing computational resources. In the future, we hope to combine our method with distributed reinforcement learning to improve the efficiency of massively parallel exploration for more complex problems.

## Acknowledgements

This work is supported in part by the National Science and Technology Major Project (Grant No. 2022ZD0116403), the Postdoctoral Fellowship Program of CPSF (Grant No. GZC20232995), the National Natural Science Foundation of China (Grant No. 62176255), the Strategic Priority Research Program of Chinese Academy of Sciences (Grant No. XDA27010103), and the Youth Innovation Promotion Association CAS.

## References

1. [Aydeniz et al., 2023] Ayhan Alp Aydeniz, Robert Loftin, and Kagan Tumer. Novelty seeking multiagent evolution- ary reinforcement learning. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 402- 410, 2023.
2. [Bazzan, 2009] Ana LC Bazzan. Opportunities for multi- agent systems and multiagent reinforcement learning in traffic control. Autonomous Agents and Multi-Agent Sys- tems, 18(3):342-375, 2009.
3. [Bellemare et al., 2016] Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Process- ing Systems, pages 1471-1479, 2016.
4. [Burda et al., 2018] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random net- work distillation. arXiv preprint arXiv:1810.12894, 2018.
5. [Chen et al., 2024a] Shuai Chen, Mingyi Zhang, Junge Zhang, and Kaiqi Huang. Exemplar-based continual learn- ing via contrastive learning. IEEE Transactions on Artifi- cial Intelligence, pages 1-12, 2024.
6. [Chen et al., 2024b] Shuai Chen, Mingyi Zhang, Junge Zhang, and Kaiqi Huang. Task-wise prompt query func- tion for rehearsal-free continual learning. In 2024 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 6320-6324, 2024.
7. [Chenghao et al., 2021] Li Chenghao, Tonghan Wang, Chengjie Wu, Qianchuan Zhao, Jun Yang, and Chongjie Zhang. Celebrating diversity in shared multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
8. [Devidze et al., 2022] Rati Devidze, Parameswaran Ka- malaruban, and Adish Singla. Exploration-guided re- ward shaping for reinforcement learning under sparse re- wards. Advances in Neural Information Processing Sys- tems, 35:5829-5842, 2022.
9. [Eysenbach et al., 2018] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:1802.06070, 2018.
10. [Hazan et al., 2019] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference on Ma- chine Learning, pages 2681-2691. PMLR, 2019.
11. [Jianye et al., 2022] HAO Jianye, Pengyi Li, Hongyao Tang, Yan Zheng, Xian Fu, and Zhaopeng Meng. Erl-re 2 : Effi- cient evolutionary reinforcement learning with shared state representation and individual policy representation. In The Eleventh International Conference on Learning Represen- tations, 2022.
12. [Khadka and Tumer, 2018] Shauharda Khadka and Kagan Tumer. Evolution-guided policy gradient in reinforcement learning. Advances in Neural Information Processing Sys- tems, 31, 2018.
13. [Khadka et al., 2019] Shauharda Khadka, Somdeb Majum- dar, Tarek Nassar, Zach Dwiel, Evren Tumer, Santiago Miret, Yinyin Liu, and Kagan Tumer. Collaborative evo- lutionary reinforcement learning. In International con- ference on machine learning, pages 3341-3350. PMLR, 2019.
14. [Krizhevsky et al., 2017] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
15. [Kurach et al., 2020] Karol Kurach, Anton Raichuk, Piotr Stanczyk, Michal Zajac, Olivier Bachem, Lasse Espe- holt, Carlos Riquelme, Damien Vincent, Marcin Michal- ski, Olivier Bousquet, et al. Google research football: A novel reinforcement learning environment. In Proceed- ings of the AAAI Conference on Artificial Intelligence, vol- ume 34, pages 4501-4510, 2020.
16. [Liu and Abbeel, 2021] Hao Liu and Pieter Abbeel. Be- havior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 34:18459-18473, 2021.
17. [Liu et al., 2021] Iou-Jen Liu, Unnat Jain, Raymond A Yeh, and Alexander Schwing. Cooperative exploration for multi-agent deep reinforcement learning. In Interna- tional Conference on Machine Learning, pages 6826- 6836. PMLR, 2021.
18. [Majumdar et al., 2020] Somdeb Majumdar, Shauharda Khadka, Santiago Miret, Stephen McAleer, and Ka- gan Tumer. Evolutionary reinforcement learning for sample-efficient multiagent coordination. In International Conference on Machine Learning, pages 6651-6660.
19. PMLR, 2020.
20. [Mnih et al., 2016] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asyn- chronous methods for deep reinforcement learning. In In- ternational conference on machine learning, pages 1928- 1937, 2016.
21. [Parker-Holder et al., 2020] Jack Parker-Holder, Aldo Pac- chiano, Krzysztof M Choromanski, and Stephen J Roberts. Effective diversity in population based reinforcement learning. Advances in Neural Information Processing Sys- tems, 33:18050-18062, 2020.
22. [Pathak et al., 2017] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 16-17, 2017.
23. [Pourchot and Sigaud, 2018] Aloïs Pourchot and Olivier Sigaud. Cem-rl: Combining evolutionary and gradient- based methods for policy search. arXiv preprint arXiv:1810.01222, 2018.
24. [Ramamurthy et al., 2020] Rajkumar Ramamurthy, Rafet Sifa, Max Lübbering, and Christian Bauckhage. Novelty- guided reinforcement learning via encoded behaviors. In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEEE, 2020.
25. [Rashid et al., 2018] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pages 4295-4304. PMLR, 2018.
26. [Samvelyan et al., 2019] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv:1902.04043, 2019.
27. [Seo et al., 2021] Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient explo- ration. In International Conference on Machine Learning, pages 9443-9454. PMLR, 2021.
28. [Sharma et al., 2019] Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics- aware unsupervised discovery of skills. arXiv preprint arXiv:1907.01657, 2019.
29. [Singh et al., 2003] Harshinder Singh, Neeraj Misra, Vladimir Hnizdo, Adam Fedorowicz, and Eugene Dem- chuk. Nearest neighbor estimates of entropy. American journal of mathematical and management sciences, 23(3-4):301-321, 2003.
30. [Sun et al., 2021] Chuxiong Sun, Bo Wu, Rui Wang, Xiao- hui Hu, Xiaoya Yang, and Cong Cong. Intrinsic motivated multi-agent communication. In Proceedings of the 2021 International Conference on Autonomous Agents and Mul- tiagent Systems, pages 1668-1670, 2021.
31. [Sun et al., 2024] Chuxiong Sun, Zehua Zang, Jiabao Li, Jiangmeng Li, Xiao Xu, Rui Wang, and Changwen Zheng. T2MAC: targeted and trusted multi-agent communication through selective engagement and evidence-driven inte- gration. In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 38, pages 15154-15163, 2024.
32. [Swamy et al., 2020] Gokul Swamy, Siddharth Reddy, Sergey Levine, and Anca D Dragan. Scaled autonomy: Enabling human operators to control robot fleets. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 5942-5948. IEEE, 2020. Taiga et al., 2019] Adrien Ali Taiga, William Fedus, Mar- los C Machado, Aaron Courville, and Marc G Bellemare. On bonus based exploration methods in the arcade learn- ing environment. In International Conference on Learning Representations, 2019.
33. [Tao et al., 2020] Ruo Yu Tao, Vincent Franc ¸ois-Lavet, and Joelle Pineau. Novelty search in representational space for sample efficient exploration. Advances in Neural Informa- tion Processing Systems, 33:8114-8126, 2020.
34. [Wang et al., 2019] Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent explo- ration. In International Conference on Learning Represen- tation, 2019.
35. [Xu et al., 2018] Pei Xu, Xin Zhao, and Kaiqi Huang. Densely connected single-shot detector. In Proceedings of the International Conference on Pattern Recognition, pages 2178-2183, 2018.
36. [Xu et al., 2022] Pei Xu, Qiyue Yin, Junge Zhang, and Kaiqi Huang. Deep reinforcement learning with part-aware ex- ploration bonus in video games. IEEE Transactions on Games, 14(4):644-653, 2022.
37. [Xu et al., 2023a] Pei Xu, Junge Zhang, and Kaiqi Huang. Exploration via joint policy diversity for sparse-reward multi-agent tasks. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 326-334, 2023.
38. [Xu et al., 2023b] Pei Xu, Junge Zhang, Qiyue Yin, Chao Yu, Yaodong Yang, and Kaiqi Huang. Subspace-aware exploration for sparse-reward multi-agent tasks. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 11717-11725, 2023.
39. [Yu et al., 2023a] Yang Yu, Qiyue Yin, Junge Zhang, Hao Chen, and Kaiqi Huang. Underexplored subspace min- ing for sparse-reward cooperative multi-agent reinforce- ment learning. In 2023 International Joint Conference on Neural Networks (IJCNN), pages 1-8. IEEE, 2023.
40. [Yu et al., 2023b] Yang Yu, Qiyue Yin, Junge Zhang, and Kaiqi Huang. Prioritized tasks mining for multi-task co- operative multi-agent reinforcement learning. In Proceed- ings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 1615-1623, 2023.
41. [Zhang et al., 2021] Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph E Gonzalez, and Stu- art Russell. Made: Exploration via maximizing deviation from explored regions. Advances in Neural Information Processing Systems, 34, 2021.
42. [Zheng et al., 2021] Lulu Zheng, Jiarui Chen, Jianhao Wang, Jiamin He, Yujing Hu, Yingfeng Chen, Changjie Fan, Yang Gao, and Chongjie Zhang. Episodic multi-agent reinforcement learning with curiosity-driven exploration. Advances in Neural Information Processing Systems, 34, 2021.