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

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.

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

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

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:

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:

where ϵ is a very small constant to ensure ρπi (s) > 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 :

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

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

We show in supplementary material that the following inequality holds:

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

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

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.

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.

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.

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.

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 > 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.