SAEIR: Sequentially Accumulated Entropy Intrinsic Reward for Cooperative Multi-Agent Reinforcement Learning with Sparse Reward

1 Introduction

Deep multi-agent reinforcement learning (MARL) is an active research field with its successful application to multi-agent cooperative tasks such as multi-player video games [Zhang and Yu, 2023], robot swarms control [Gu et al., 2023], smart grid control [Jin and Ma, 2019], autonomous vehicle coordination [Guo et al., 2023], and resource management [Li et al., 2023]. Despite the progress in value-based and policy-based MARL algorithms [Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019; Wang et al., 2021; Yu et al., 2022; Lowe et al., 2017], their efficiency relies heavily on expert-designed dense reward feedback. However, there are only sparse reward settings in many real-world multi-agent scenarios [Pathak et al., 2017], where non-zero rewards are provided just when certain conditions are satisfied rather than at every time step. Without the guidance of dense reward feedback, the agents require many episodes to come across any reward and have difficulty in learning effective cooperative strategies, which restricts the application of multi-agent algorithms. Therefore, solving cooperative tasks with sparse rewards becomes a critical challenge for multiagent reinforcement learning.

A common approach to addressing this challenge in current MARL algorithms is to apply intrinsic motivation techniques during the training procedure, which has been shown to be effective in some cooperative tasks. Due to classical curiositybased methods [Pathak et al., 2017; Savinov et al., 2019; Yang et al., 2020] performing well in single-agent scenarios, some works extend the intrinsic curiosity reward to MARL algorithms [Iqbal and Sha, 2019b; Zheng et al., 2021; Li and Gajane, 2023; Yu et al., 2023]. There are also many works that utilize the curiosity bonus as part of intrinsic reward and introduce novel prior knowledge to improve exploration, such as interaction influencing [Wang et al., 2020] and counterfactual reasoning [Yang et al., 2021]. Besides using the concept of curiosity to design the intrinsic reward, current works apply effective formulations to generate the intrinsic reward, such as the theory of mind [Ma et al., 2022], subgoal assignment [Jeon et al., 2022; Xie , 2023 ], and causal inference [Liu et al., 2023]. These methods combine intrinsic reward with the extrinsic reward provided by the environment to encourage exploration. However, the above methods ignore the great potential for entropy, the natural property in multi-agent systems, as an intrinsic reward.

Entropy originates from information theory, which is used to characterize the disorder of a system. During the training procedure, the multi-agent system transforms from stochastic processes (disorder) to stationary processes (order), where the strategies learned by agents transform from random to deterministic and the system entropy gradually decreases. As shown in Fig. 1, in the case of solving a multi-agent football game, the multi-agent system states using soccer trajectory as visualization demonstrate this phenomenon. For the visualization of different strategies, we observe that the soccer trajectories implemented by early strategies are not uniform, which means the strategies learned in the early stages are stochastic. On the contrary, the soccer trajectories implemented by later strategies are similar, which means the strategies learned in the later stages are stationary. At the same time, we observe that early strategies do not achieve goals, while later strategies all win the match. Based on this observation, we focus on the highly valuable states that result in a decrease in the entropy of multi-agent systems. Intrinsic rewards should be supplied to these states, substantially accelerating learning when the original environmental rewards are sparse.

(b) Later Strategies (Stationary Processes)

Figure 1: Visualization of the multi-agent system state under different stage strategies using soccer trajectory.

In this paper, we propose a novel Sequentially Accumulated Entropy Intrinsic Reward (SAEIR) to address the challenge of sparse reward encountered within cooperative multiagent reinforcement learning. To precisely characterize the state of the multi-agent system, the high-order state representations are extracted from the environment via the multi-scale hypergraph critic. Based on these comprehensive and compact system state representations, the change of multi-agent system entropy in a trajectory under current policy can be measured. Then, the accumulated system entropy is calculated as an intrinsic reward supplied to such highly valuable states that can decrease the system entropy. We summarize our contributions as follows:

• We propose an effective intrinsic reward, using sequentially accumulated system entropy as a dense bonus to accelerate the learning of successful strategies in multiagent systems with sparse reward settings.
• Amulti-scale hypergraph critic is proposed to extract accurate system state representations, which are used to measure the change of multi-agent system entropy between sequential states. It also enhances the ability to effectively evaluate the action produced by the actor.
• Empirical results in cooperative multi-agent environments with sparse rewards demonstrate our method outperforms the state-of-the-art methods and promotes agents to generate better cooperative policies.

2 RelatedWork

2.1 Intrinsic Motivation for Multi-Agent Reinforcement Learning with Sparse Rewards

Benefiting from the significant performance of intrinsic motivation techniques in the sparse-reward SARL domain, most MARL methods addressing the challenge of sparse rewards have been adapted from single-agent intrinsic incentives. Multi [Iqbal and Sha, 2019b] designs various types of countbased intrinsic rewards by considering coordination among agents and utilizes a hierarchical policy to dynamically select exploration modalities trained on diverse intrinsic rewards. EDTI and EITI [Wang et al., 2020] consider the agents' interactions during their training process to coordinate their exploration and use information- and decisiontheoretic influence to obtain intrinsic rewards respectively. CIExplore [Yang et al., 2021] combines a joint curiositybased reward and an influence reward motivated by counterfactual reasoning as an intrinsic reward, avoiding training instability and enabling agents to generate cooperative behavior. Elign [Ma et al., 2022] designs an intrinsic reward inspired by the self-organization principle in Zoology [Couzin, 2007]. It is a simple and effective way to improve the learning ability of agents in the alternative setup of decentralized training or sparse rewards. LIGS [Mguni et al., 2022] employs an adaptive learner to construct intrinsic rewards online for performing coordinated joint behavior and achieving an efficient learning process. MASER [Jeon et al., 2022] generates subgoals from the experience replay buffer and designs individual intrinsic rewards for each agent using actionable representations, helping agents maximize the joint action value while achieving their subgoals. IPERS [Xie et al., 2023] utilizes prioritized experience replay along with subgoals to enhance the training convergence rate in environments with sparse rewards. Subgoals are employed to provide beneficial intrinsic rewards. SAME [Xu et al., 2023b] gets a bonus from a special structural prior on the reward function and combines it with a count-based bonus, which not only encourages agents to explore sub-state paces with higher uncertainty but also preserves novel states in the fullstate space level. USM [Yu et al., 2023] is an intrinsic reward that focuses on the target-related attributes of the underexplored subspaces rather than the whole state space to accelerate learning. LJIR [Chen et al., 2023] introduces a general framework to construct a compound intrinsic reward online by agents' state and joint actions, which helps agents find the best joint actions via the combination of state novelty and joint-action novelty. The work [Xu et al., 2023a] improves traditional count-based methods by introducing constrained joint policy diversity, making the traditional countbased methods work well with neural networks and achieve significant performance. PDP [Sun et al., 2023] actively amplifies the diversity among agents' policies during training and designs an intrinsic reward based on the diversity. LAIES [Liu et al., 2023] defines the concept of lazy agents in MARL and proposes two intrinsic rewards based on intrinsic motivation for individual diligence and collaborative diligence derived from these definitions. I-Go-Explore [Li and Gajane, 2023] integrates an intrinsic curiosity module with the Go-Explore framework [Ecoffet et al., 2021] to address the limitations of the intrinsic curiosity module. However, despite SAME employing the entropy of the state distribution to find the sub-state space with higher uncertainty, none of the above methods explicitly considers mapping the state entropy as an intrinsic reward, which is a natural property in multiagent systems and a suitable intrinsic motivation that does not require domain knowledge. We aim to exploit the state entropy to facilitate learning coordinated policies in complex cooperative multi-agent environments with sparse rewards.

2.2 Enhanced Critic for Multi-Agent Reinforcement Learning with Sparse Rewards

The reliable and accurate critic can improve the performance of MARL algorithms [Foerster et al., 2018; Iqbal and Sha, 2019a; Liu et al., 2022]. Therefore, some works focus on utilizing the enhanced critic to address the challenge of sparse reward. IRAT [Wang et al., 2022] introduces a framework that assists the team policy learning from critic with sparse reward by the individual policy learned using critic with dense reward. SN-MAPPO [Mehta et al., 2023] utilizes the spectral normalization technique to regularize the plain critic. It enables agents to quickly and stably learn from the setup of sparse rewards. Our method develops an enhanced critic via the multi-scale hypergraph network, which not only enhances the ability to effectively evaluate the action produced by the actor but also extracts the accurate high-order system state representations.

3 Preliminaries

3.1 ProblemFormulation

The multi-agent cooperation problem can be formulated as a decentralized partially observable Markov decision process (Dec-POMDP) [Oliehoek and Amato, 2016]. Generally, it is defined as a tuple < N, S,A,O, T ,R, γ >, where N is the set of n agents indexed by 1, 2, . . . , n; S is the finite set of environment states; A = A1 × A2 × . . . × An is the set of joint actions and Ai represents the set of actions available for agent i (i ∈ N); O = O1 × O2 × . . . × On is the set of joint observations and Oi denotes all possible observation of agent i on S; T : S ×A → S formulates the transition probability function, and at each time step, the agents select actions a ∈ A at state s ∈ S, then reach the next new state s′ ∼ T (s, a); R : S ×A → Rn is the reward function. The action policy πi : Oi ×Ai → [0, 1] represents the probability of agent i selecting an action ai ∈ Ai based on its partial observation oi ∈ Oi. Given an initial state s, all the agents work cooperatively to maximize the total system's discounted cumulative reward: J(τ) = ∑∞t=0 γ t rt , where rt is the reward obtained by agents at time step t according to the police πi, γ ∈ [0, 1] is a discount factor.

3.2 Multi-agent Reinforcement Learning Algorithms

The Actor-Critic method is widely used in the multi-agent deep reinforcement learning framework [Lowe et al., 2017; Foerster et al., 2018; Yu et al., 2022]. The most AC methods commonly use advantage function Aπ to optimize policy π:

and the policy objective function is:

3.3 Multi-Agent Proximal Policy Optimization

IPPO [de Witt et al., 2020] trains an independent PPOlearned [Schulman et al., 2017] strategy with a parametersharing technique [Gupta et al., 2017] for each agent in the multi-agent system. MAPPO [Yu et al., 2022] extends the independent critics of IPPO to a centralized value function accepting global information, which shows the significant performance in various cooperative multi-agent tasks. It optimizes the policy network θ by maximizing the following objective:

where ηi t (θ) = πθ(ait |τ i t ) πθold (ait |τ i t ) denotes the probability ratio. The function clip (·) removes ηi t (θi ) outside of the interval [1 - ϵ, 1 + ϵ] parameterized by ϵ, which approximates the KL-divergence constraint. ˆ Ati is a generalized advantage estimator (GAE) [Schulman et al., 2016]

where T is the episode time horizon.

3.4 Hypergraph Neural Network

Hypergraph neural network [Feng et al., 2019] is a generalization of general graph neural network, in which a hyperedge can link any number of vertices. Hence, the hypergraph can capture high-order representations through group-wise embeddings instead of pair-wise ones used in the general graph, which has proven to be effective in a wide range of applications. Mathematically, a hypergraph is defined as G = (V, E), where V = {v1, v2, . . . , vN} denotes the set of vertices in the hypergraph (N represents the number of vertices), and E = {ei := (v(i) 1 , v(i) 2 , . . . , v(i) k )|i = 1, 2, . . .M} denotes the set of hyperedges (M represents the number of hyperedges, k represents the number of vertices in a hypergraph and k can be different in different hyperedges).

where K ∈ {Individual(I),Group(G), Team(T)}. ¯ eKi,t and hKi,t respectively denote the encoded state feature and the hidden state used for extracting the state representation at the scale of individual, group, and team. W K MLP andW K GRU are the learnable weights.

State Representation Hypergraph Network: The comprehensive and compact state representation is extracted under multiple scales via the hypergraph network. Mathematically, let V = {v1, v2, . . . , vN} denote a vertex set containing N agents and E I = {eI1 , eI2 , . . . , eIN }, E G = {eG1 , eG2 , . . . , eGMs } and E T ={eT1 } denote three hyperedge sets with the scale of individual, group, and team respectively, where 1 < Ms < N and it is decided by a hyperparameter NG that denotes the number of agents in a group. Therefore, the multiple scale hypergraph networks are formalized as G I = {V, E I }, GG = {V, E G} and G T = {V, E T }. The topology of each GK can be constructed as an incidence matrix HK ∈ R|V|×|E K | , where HKi,m = 1 if the ith vertex is included in the mth hyperedge, otherwise HKi,m = 0. Concretely, HI equals to the identity matrix IN×N and HT equals to the vector with all 1 elements 1N×1 . For HG, we first compute an affinity matrix AG ∈ RN×N to measure the correlation between the ith agent and the jth agent:

Then, the hyperedges in E G are formed by searching the highdensity submatrices in the affinity matrix AG via a greedy algorithm approximation, where agents in the submatrices have high correlation with each other and form a group:

where || · ||1 denotes the matrix entrywise L1-norm. HG ∈ RN×Ms is composed of a stack of eGm(m = 1, 2, . . . ,Ms). The obtained hyperedge contains the most correlated agents

4 Method

This section describes our proposed intrinsic reward function SAEIR for effectively addressing the challenge in cooperative MARL with sparse reward settings. We follow the Centralized Training and Decentralized Execution (CTDE) framework, where agents are trained with access to global information but make decisions based on their own local information in execution. We implement the SAEIR on the representative Actor-Critic (AC) style CTDE algorithm, which has a plain actor and a multi-scale hypergraph critic shown in Fig. 2. The agent executes action sampled from the policy learned by the plain actor (a three-layer Multi-Layer Perceptron with ReLU non-linearities) and interacts with the environment. The multi-scale hypergraph critic provides the state value for the plain actor to update. It also offers a comprehensive and compact system state representation to calculate the intrinsic reward. The sequentitally accumulated entropy intrinsic reward is calculated based on these system state representations and supplied to the highly valuable states, leading to a highly efficient learning process. We then introduce the details of the multi-scale hypergraph critic and the calculation of the SAEIR intrinsic reward.

4.1 Multi-Scale Hypergraph Critic

To extract the high-order system state representations and provide the accurate state value for the plain actor, we develop the multi-scale hypergraph critic (MSHG Critic) that comprises the state feature encoder, the state representation hypergraph network, and the state value decoder.

State Feature Encoder: The encoder is composed of a threelayer Multi-Layer Perceptron (MLP) and a Gated Recurrent Unit (GRU). For each agent i at time step t, the system state sti is encoded using the MLP to create the encoded state feature ¯ ei,t. Then, the GRU takes the encoded state feature ¯ ei,t and the hidden state hi,t-1 as inputs to generate the next hidden state hi,t as shown in Eq. 5

and links them together to consider the state representation from a group perspective. According to the hyperedge sets E K , the state representation ¯ sKi is obtained through:

where eKm denotes the state feature embedding from vertex to hyperedge for the mth hyperedge in each K scale, vK i is the state representation for the ith agent in each K scale and initial vK i equals to the hidden state hKi,t , wKm is the learnable weight for weighting the state feature embedding of each hyperedge, aKm,i denotes the attention coefficient of each vertex vi in eKm, F K eKm (·) is a three-layer MLP, F K ¯ s (·) and F K vi (·) are a single-layer network respectively, [·, ·] denotes the concatenation of all state representations about one vertex contained in the associated hyperedges.

State Value Decoder: The decoder uses a fully connection (FC) layer to generate the state value vK,π i,t for agent i at time step t under current policy π, which takes each ¯ sKi,t as the input and is shown in Eq. 9:

The final state value is

where wK i,t are the weight coefficient.

4.2 Sequentially Accumulated Entropy Intrinsic Reward

To determine the highly valuable state for adding a bonus, we utilize the entropy-based technique to characterize the disorder of a multi-agent system. According to the comprehensive and compact system state representation obtained from the MSHG critic, the multi-agent state is measured by the weighted sum of state representation with attention coefficients:

where ⊙ denotes the Hadamard product operator. In practice, we set aK to be W K FC to maintain consistency between the estimation of the system state and the state value provided by the critic. To identify the highly valuable states that lead to a decrease in the disorder of the multi-agent system, the sequentially accumulated entropy of the system state in a trajectory is calculated as follows:

where T ≡ t denotes the time length of the trajectory until time step t. According to Eq. 12, the highly valuable states that decrease the disorder of the system are searched to be added intrinsic rewards, and the sequentially accumulated entropy intrinsic reward is designed as:

where wK i,t are the weights for three scales of intrinsic rewards and ∑K wK i,t = 1, I is an indicator function:

which represents the state st decreasing the accumulated system entropy ˆ et within the sequentially time length T + 1 of trajectory is identified as highly valuable state, and the bonus should be supplied to this state. While the intrinsic reward is obtained according to Eq. 13, the augmented reward for agent i at time step t is:

where rext i,t is the external reward given by the environment, rint i,t is the intrinsic reward calculated by Eq. 13, and β is a positive scalar that weights the intrinsic reward.

During the training procedure, the disorder of the system state gradually decreases and intrinsic rewards finally converge to a constant close to 0. Therefore, the advantage estimate ¯ Aπ (st, at) with intrinsic rewards can be proved:

This means that after a certain amount of training, the policy is only influenced by external rewards, ensuring policy invariance.

4.3 Training Process

In this section, we show the overall training process of the SAEIR applied to the agent in Algorithm 1. The plain actor network is trained to minimize the Eq. 17 and the multi-scale hypergraph critic network is trained to minimize the Eq. 18:

where rθ i = πθ(ai|oi) πθold (ai|oi) , S is the policy entropy, σ is the entropy coefficient hyperparameter, and Rt i (γ) is the discounted reward-to-go of the augmented reward with factor γ.

5 Experiments and Results

In this section, We evaluate SAEIR in two complex cooperative multi-agent environments: Cooperative Navigation (CN, [Lowe et al., 2017]) and Google Football Research (GRF, [Kurach et al., 2020]). In all environments, scenarios with sparse reward settings are considered. We compare the performance of SAEIR against a classical Actor-Critic MARL algorithm MAPPO [Yu et al., 2022], an EnhancedCritic MARL algorithm SN-MAPPO [Mehta et al., 2023], and two intrinsic reward MARL algorithms RND [Burda et al., 2019] (extended to MARL version), Elign [Ma et al., 2022]. All experiments run with five random seeds to maintain reliability and consistency.

5.1 Experimental Settings

For the CN environment, it requires N agents cooperating to reach L landmarks while avoiding collision. The locations of agents and landmarks are generated randomly. Each agent gets a positive reward related to the number of occupying landmarks and a negative reward when collisions oc-

Algorithm 1 Sequentially Accumulated Entropy Intrinsic Reward Applied to Agents (SAEIRA)

Initialize the parameters θ for policy π, the parameters set ϕK for multi-scale critic V K , K ∈ {individual, group, team}, using Orthogonal initialization.

Set learning rate α. 1: while step ≤ stepmax do 2: set data buffer D ={} 3: for b = 1 to batch size do 4: τ =[ ] empty list 5: for t = 1 to T do 6: for all agents i do 7: pti , ht-1 i = π(oti , hti ; θ) 8: ati ∼ pti 9: vK i,t , hKi,t-1 , ˆ sKi,t = V K (st; ϕK ) // Eq. 5 - Eq. 9 10: V π i,t = ∑K wK i,t vK i,t // Eq. 10 11: end for 12: Execute actions at , observe rext t , st+1, ot+1 13: Calculate intrinsic reward rint i,t using Eq. 13 14: τ+=[st, ot, ht , hKt , at, rext t , rint t , st+1, ot+1] 15: end for 16: Calculate advantages estimate ˆ Aπ for plain actor by GAE on τ , using PopArt 17: Calculate reward-to-go Rt(γ) of augmented reward by GAE on τ with normalizing PopArt 18: D =D∪ τ 19: end for 20: for p = 1 to epochtrain do 21: Sample data d from D 22: Adam update θ on Lπ (θ) with data d // Eq. 17 23: Adam update ϕ on LC (ϕ) with data d // Eq. 18 24: end for 25: for e = 1 to epocheval do 26: Evaluate policy πi of each agent i 27: end for 28: end while

cur. The evaluation metric is the coverage rate per episode during the training process. In the GRF environment, each scenario requires agents to learn collaborative skills to score, such as dribbling, passing, and moving. Each agent only obtains a +1 reward for scoring a goal and a -1 reward when conceding one to the opposing team, which corresponds to the SCORING reward function provided by the environment. The evaluation metric is the winning rate per episode during the training process. More details are within supplementary.

5.2 Results in Cooperative Navigation

Fig. 3 shows the training curves of the coverage rate for agents reaching goal landmarks. According to Fig. 3, we can find that the performance of RND deteriorates as the number of agents increases. Although SN-MAPPO and Elign learn coherent policies, their performance slightly lags behind MAPPO. We think this is mainly because the outputs of critic in SN-MAPPO are too smooth and the dynamics models learned in Elign are suboptimal. SAEIR achieves better performance than the other baselines. With the increase in the number of agents, SAEIR shows increasingly pronounced performance improvements compared to the other methods.

5.3 Results in Google Football Research

Fig. 4 shows the training curves of the success rate for agents completing a football game. As shown in Fig. 4, RND does not learn a winning strategy in two sparse reward scenarios. Although MAPPO solves the task in Academy 3 vs.1 with keeper scenario, it failed in another scenario. For SNMAPPO and Elign, they can learn winning strategies in two sparse reward scenarios but the performances are unstable. In both sparse reward scenarios, we can see that SAEIR achieves the highest success rate among the baselines. Table 1 shows the exact results in all sparse reward scenarios.

5.4 Ablation Study

We present the results of the ablation studies. To confirm the performance individually using the multi-scale hypergraph critic and the sequentially accumulated entropy-based bonus, we choose the academy 3 vs.1 with keeper scenario to make the report. Fig. 5 shows the training curves of the success rate. Although the MSHG critic and the SAE-based bonus learn comparable winning strategies, the performance improvements do not achieve expectations. Benefiting from the advantages of both two components, our method achieves the highest performance and is quite stable with a small variance.

6 Conclusion and FutureWork

In this paper, we propose a novel intrinsic reward called SAEIR to successfully learn an effective strategy in sparse reward environments. The proposed method is based on the assumption that the highly valuable states making a decrease in the entropy of multi-agent systems should be added a bonus. SAEIR guides multiple agents to find better states that decrease the disorder of system and facilitates the learning of successful strategies. The experimental results demonstrate the effectiveness of SAEIR compared to state-of-the-art methods. One limitation of the current work is that it has a cold start issue sometimes. In the future, we will make efforts to address this limitation and explore the possibility of combining our method with the subspace or subgoal technique.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (61976034,U1808206), the Dalian Science and Technology Innovation Fund (2022JJ12GX013), the Natural Science Foundation of Liaoning Province (2022YGJC20), and the Fundamental Research Funds for the Central Universities (DUT21YG106).