Measuring Mutual Policy Divergence for Multi-Agent Sequential Exploration

Authors: haowen  dou
lujuan  dang
zhirong  luan
badong  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 14:22:47

Abstract: Despite the success of Multi-Agent Reinforcement Learning (MARL) algorithms in cooperative tasks, previous works, unfortunately, face challenges in heterogeneous scenarios since they simply disable parameter sharing for agent specialization. Sequential updating scheme was thus proposed, naturally diversifies agents by encouraging agents to learn from preceding ones. However, the exploration strategy in sequential scheme has not been investigated. Benefiting from updating one-by-one, agents have the access to the information from preceding agents. Thus, in this work, we propose to exploit the preceding information to enhance exploration and heterogeneity sequentially. We present Multi-Agent Divergence Policy Optimization (MADPO), equipped with mutual policy divergence maximization framework. We quantify the policy discrepancies between episodes to enhance exploration and between agents to heterogenize agents, termed intra-agent and inter-agent policy divergence. To address the issue that traditional divergence measurements lack stability and directionality, we propose to employ the conditional Cauchy-Schwarz divergence to provide entropy-guided exploration incentives. Extensive experiments show that the proposed method outperforms state-of-the-art sequential updating approaches in two challenging multi-agent tasks with various heterogeneous scenarios.

Main paper: 
 introduction: 
 Multi-Agent Reinforcement Learning (MARL) plays an increasingly important role in numerous real-world cooperative problems, such as smart grid management [Zhang et al., 2022b] , autonomous driving [Wang et al., 2023b] , unmanned system control [Feng et al., 2023b] and games [Zhang et al., 2022a] . Centralized and decentralized MARL methods have been investigated as the first two extensions from single-agent to multi-agent systems. However, challenges have arisen regarding the curse of dimensionality and non-stationary training as the number of agents increasing [Mao et al., 2022] . To address this issue, Centralized Training with Decentralized Execution (CTDE) was developed to disentangle training and execution phases [Foerster et al., 2018] . In the CTDE scheme, dynamically. Yu et al. [2022] proposed Multi-Agent Proximal Policy Optimization (MAPPO) which applies PPO to multi-agent scenarios without violating the guarantee of monotonic improvement in the individual policy level. Policy entropy incentive in MAPPO is one of the most related parts to our method, providing diversified policy learning from an information theory perspective. Li and He [2023] proposed MATRPO to extend Trust Region Policy Optimization (TRPO) to multi-agent tasks through a fully decentralized setting and distributed optimization. However, when the number of agents becomes large, MATRPO may encounter the challenge of the connecting link dimension curse. This is because it relies on communication rather than global information to facilitate cooperation. Guo et al. [2024] proposed MASPG, a trust region-based MARL algorithm in the off-policy manner, to enhance the sample efficiency of trust region methods. However, these methods require homogeneity of agents, i.e. parameter sharing, to ensure monotonic improvement. This homogeneity assumption can impose significant restrictions on agents, limiting their ability to explore the joint policy space adequately [Ding et al., 2022] . Consequently, if the sharing of parameters is canceled, it can lead to violations of the monotonicity guarantee and result in performance degradation [Zhan et al., 2023] . 
sequential updating marl: 
 The sequential updating scheme originates from single-agent rollout and policy iteration [Bertsekas, 2021] , aiming to update policies of agents one by one, as shown in Fig. 1a . This structure encourages agents to learn different policies based on information from preceding ones, thereby naturally generalizing the homogeneous MARL to heterogeneous MARL. To build the multi-agent sequential updating scheme, attempts have been addressed from both joint and individual policy perspectives. For example, Bertsekas [2021] proposed rollout and policy iteration method, which was the first to consider sequential updating in MARL. Kuba et al. [2022] observed the multi-agent advantage decomposition lemma and proposed HAPPO. Leveraging this powerful lemma, HAPPO estimates and decomposes the joint advantage function to implement sequential updating and ensure the joint monotonic improvement. On the other hand, A2PO proposed by Wang et al. [2023a] focuses on individual policy improvement by leveraging the multi-agent policy difference lemma. A2PO maintains distribution invariance during each agent's advantage estimation process and consider a more refined updating order. Zhao et al. [2023] introduced a localized action value function as the surrogate optimization objective, offering a provable convergence guarantee for multi-agent PPO.Information-theoretic principles serve as a powerful regularization technique for providing valuable guidance in intrinsic reward-driven RL [Liu and Zhang, 2023 , Subramanian et al., 2022 , Russo and Proutiere, 2024] , including both policy and state exploration [Cen et al., 2021 , Jacob et al., 2022] . For example, the Soft Actor-Critic (SAC) is the first to maximize the Shannon entropy of policies, promoting randomness and encouraging exploration [Haarnoja et al., 2018] . On-policy methods, such as PPO, MAPPO and HAPPO, embrace the same concept by incorporating entropy regularization into the optimization objective. Additionally, recent advancements have explored the utilization of various entropy forms, such as encoder estimated stable entropy [Liu and Abbeel, 2021] , value conditional entropy [Kim et al., 2023] and Rényi entropy [Yuan et al., 2023] to model environmental dynamics and accelerate novel state discovery. However, maximizing entropy only introduces stochasticity for measuring uncertain dynamics. To address this limitation, policy divergence regularization between episodes [Su and Lu, 2022, Xu et al., 2023] has been proposed. This regularization method calculates the policy divergence based on a fixed policy and offers more directed guidance compared to entropy alone. Furthermore, the efficacy of state divergence in combating local optima and fostering state novelty has been demonstrated [Hong et al., 2018 , Yang et al., 2021] . However, the existing divergence RL methods cannot be effectively extended to the sequential updating paradigm.In this work, we pursue an on-policy method to enhance exploration and heterogenize agents in a sequential updating paradigm, termed Multi-Agent Divergence Policy Optimization (MADPO). In contrast to the aforementioned policy divergence-based methods, we introduce a novel approach that maximizes inter-and intra-agent policy divergence, thereby incorporating policy information. To further address the deficiency of exploration direction in the traditional divergence RL, we propose to employ the conditional Cauchy-Schwarz divergence to provide an entropy-guided incentive. Figure 1 : A three-agent example of traditional sequential updating MARL and our MADPO. The white boxes represent the policies to be updated π i , and the orange boxes represent the updated policies πi . The white boxes with dashed lines represent the joint policies to be updated π, and the orange ones represent the updated joint policy π. Compared to the traditional sequential updating MARL, our method takes the intra-agent and inter-agent divergence into account, as shown in the blue boxes. The intra-agent divergence directs agents to explore novel policies based on their former policies, while the inter-agent divergence heterogenizes agents sequentially.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss the main limitation of this work in Conclusion 6. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
marl porblem formulation: 
 In this paper, we consider a multi-agent sequential decision-making problem, which can be described as a decentralized Markov decision process (DEC-MDP). A DEC-MDP with n agents can be formulated as the tuple: ⟨S, A, r, T , γ⟩, where S represents the state space. We denote N = {1, . . . , n} as the set of finite agents. A = A 1 × • • • × A n is the joint action space by taking the product of actions spaces of n agents. T : S × A × S → [0, 1] is the state transition function of the environment dynamics. r : S × A → R is the reward function. γ is the discount factor. At time step t, to interact with the environment, each agent at state s t ∈ S takes an action a i t from its own policy π i (•|s t ) to form a joint action a t = {a 1 t , . . . , a n t } and a joint policy π(•|s t ) = π 1 × . . . × π n . The agents then receive a joint reward r(s t , a t ) and step to the new state s t+1 with the probability T (s t+1 |s t , a t ). The objective is to learn an optimal joint policy by maximizing the expected cumulative reward:π = arg max π ∞ t=0 E st∼ρπ,at∼π [γ t r(s t , a t )], where ρ π is the marginal state distribution. Following Bellman Equations, the state-action value function and the state function of state s t are defined asQ π (s t , a t ) = r(s t , a t ) + ∞ i>t E si∼ρπ,ai∼π γ i-t r(s i , a i ) , and V π (s t ) = ∞ i>t E si∼ρπ,ai∼π γ i-t r(s i , a i )|s 0 = s t . And the advantage function is defined as A π (s t , a t ) = Q π (s t , a t ) -V π (s t ).Sequential updating paradigm was introduced to alleviate homogeneity in multi-agent reinforcement learning. The overview of sequential updating with a three-agent setting is shown in Fig. 1a . For instance, Heterogeneous-Agent Proximal Policy Optimisation (HAPPO) takes preceding agent information into account by employing the multi-agent advantage decomposition lemma and the joint advantage estimator [Kuba et al., 2022] . At episode k, agent m in HAPPO maximizes the extrinsic multi-agent clipping objective as formulated in Eq. 1,r E = E s∼ρπ θ k ,a∼π k min π im (a i |s) πim k (a i |s) M i1:m (s, a), clip π im (a i |s) πim k (a i |s) , 1 ± ϵ M i1:m (s, a) ,(1) where πim k (a i |s) is the policy of the m th agent updated at episode k -1, the superscript of r E represents Extrinsic, and M i1:m (s, a) is the joint advantage estimator of the first to m th agents, which is defined as follows,EQUATIONwhereπ i1:m-1 = m-1 p=1π ip is the joint policy of the first to m th agents, and Â(s, a) is an individual advantage estimator, such as Generalized Advantage Estimation (GAE). Additionally, Eq. 1 is also incorporated with an intrinsic reward term, i.e. the policy entropy, defined as r I = H(π im (a i |s)).4 Method EQUATIONwhere Div(•) is one divergence measurement, λ is the coefficient to control the influence of the two divergence, and the superscript I represents Intrinsic.The first term in Eq. 3 is the inter-agent policy divergence, quantifying the discrepancy between policies of the current agent and the preceding agent. In heterogeneous tasks, such as multi-joint control in robotics, each agent has its own specialization. Hence, learning diversified policies for different agents is more desirable in these scenarios. By maximizing the inter-agent divergence, agents are provided with a novel optimization direction towards heterogeneity, resulting in significant diversification. Note that in the simultaneous updating manner, the inter-agent divergence maximization becomes theoretically challenging, since these methods lack access to the information from the preceding agents.The second term in Eq. 3 is the intra-agent policy divergence, which measures the difference between the current policy and the former policy of an agent. The intra-agent policy divergence encourages agents to learn new and diverse policies based on their previous policies. Consequently, we provide agents an optimization direction towards policy novelty, greatly enhancing exploration.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) • The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
conditional cauchy-schwarz policy divergence: 
 To measure the discrepancy between policies, a natural idea is to use the KL-divergence. At episode k, agent i optimizes the KL-divergence between the current policy π i k and a fixed policy π, which can be defined as follows,EQUATIONwhere H(π i k , π) is the cross entropy between π i k and π, H(π i k ) is the policy entropy. However, optimizing KL-divergence between policies raises problems regarding instability and inhibition of exploration in MARL. Specifically, when approaching 0, the fixed policy π(a j |s j ) in Eq. 4 may lead to uncontrollability and unreliability of the log term, which is common in initialization and converged phrase of MARL. Moreover, the second term in Eq. 5 minimizes the entropy of the current policy, which brings an opposite optimization direction, thus adversely affecting exploration. To address these issues, we introduce Conditional Cauchy-Schwarz Divergence for policy divergence maximization.The Conditional CS divergence, recently proposed by Yu et al. [2023] , is an extension from classic CS divergence for quantifying the discrepancy between two conditional distributions. Formally, given random variable A and S with a finite data set, the CS inequality is defined as follows,EQUATIONwhere p(a) and q(a) are the probability density functions. By leveraging Eq. 6, we can obtain the CS divergence, defined asD CS = -1 2 log ( p(a)q(a)) 2 p 2 (a) q 2 (a). Similarly, we can derive the conditional CS divergence of two policies, i.e. the action distributions conditioned by the states, defined as follows,EQUATIONWe then present some desirable properties of Eq 7. Proposition 1. Given a policy to be updated π and a fixed policy π, and α-order Rényi policy entropyEQUATION)Proofs can be found in Appendix A.1. Proposition. 1 is motivated by [Li et al.] and indicates that the CS divergence between distributions is a lower bound of the sum of 2nd-Rényi entropy of distributions. Consequently, in MARL, maximizing the CS divergence between a target policy and a fixed policy behaves like maximizing the 2nd-Rényi entropy of the target policy, which is a generalized form of Shannon policy entropy [Yuan et al., 2023] . In this way, by taking the conditional CS divergence into account, agents are encouraged to enhance their policy entropy while diversifying their policies. Thus, maximizing the CS policy divergence can provide agents with 2nd-Rényi entropy-guided exploration incentives.Proposition 2. Given a policy to be updated π and a fixed policy π with a finite action set A = {a 0 , ..., a n } at state s, then the CS divergence is lower bounded by:EQUATIONProofs can be found in Appendix A.2. Recall that in Eq. 4, it is obvious that the KL-divergence is unstable when the probability of one action approaching 0, a common occurrence in MARL.In contrast, Proposition. 2 demonstrates that the CS divergence has a deterministic lower bound unless the number of actions approaches infinity, which is not feasible in practical MARL. Even if in continuous action tasks, the trajectories sampled from policies have finite actions. Thus, maximizing the CS divergence can provide a more stable guidance for policy optimization.We first present the overall optimization objective of MADPO in this section. At episode k, agent i in MADPO maximizes the practical objective as follows,EQUATIONwhere DCS (•||•) is the estimator of the conditional CS divergence, and σ is the parameter of the estimator. Given trajectories τ π = {s π 1 , a π 1 , ..., s π n , a π n } and τ π = {s π 0 , a π 0 , ..., s π n , a π n } sampled from a fixed policy π and the current policy π. The empirical estimator of Eq. 7 can be formulated by using kernel density estimation:EQUATIONwhere S π and A π represent the Gram matrices of states and actions sampled from the policy π:S π ij = κ(s π i -s π j ), A π ij = κ(a π i -a π j ), where κ(•) is a Gaussian kernel denoted as κ(•) = exp(-||•|| 2 2σ 2), and σ is the parameter of κ(•). Moreover, S π→π and A π→π represent the Gram matrices from distribution (i.e. policy) π to distribution π, formulated as S π→π ij = κ(s π i -s π j ). Detailed proofs can be found in Yu et al. [2023] .In contrast to existing sequential methods, starting from the second agent in the first episode, MADPO maintains the buffer data for more time. Specifically, for mutual policy divergence maximization, when finished training in episode k, MADPO maintains the minibatch of the updated k-th policies for one more episode. We summarize the whole algorithm in Algo. 1.Input: Initial joint policy π 0 = π 1 0 × ... × π n 0 , parameters of Mutual PDM, σ and λ. 1: for iteration k = 1, ..., K do 2: Collection trajectories T k = {τ 1 k , ..., τ n k } by running πk = π1 k × ... × πn k . 3:Restore T k into the buffer.Compute the advantage Â(s, a) by using the V network.for agent i = 1, ..., n do 6:if not i = 1 then 7:Compute the inter-agent divergence 1-λ σ DCS (π i k ||π i-1 k ; σ) via trajectories τ i-1 k , τ i k and Eq. 11. Compute the intra-agent divergence λ σ DCS (π i k ||π i k-1 ; σ) via trajectories τ i k-1 , τ i k and Eq. 11.10:Compute J = r E + r I mutual and update the actor network by maximizing Eq. 10.11:Compute the joint advantage via Eq. 2.12:end for 13:Update the V network.14:Delete T k-1 from the buffer. 15: end for 5 ExperimentsWe evaluate the proposed MADPO on two challenging multi-agent heterogeneous environments, Multi-Agent Mujoco (MA-Mujoco) [de Witt et al., 2020] and Bi-DexHands [Chen et al., 2022] . Multi-Agent Mujoco is a complex and widely used task which necessitates up to 17 different joints of one robot to coordinate for human-like behavior imitation, such as running and walking. Bi-DexHands is a bimanual dexterous manipulation environment, where agents are in control of fingers, hands or joints. Sub-scenarios in Bi-DexHands require agents to collaborate for more complex bimanual tasks, such as opening a door inward and outward, passing an item from one hand to another. We compare MADPO with state-of-the-art MARL algorithms, including one simultaneous method MAPPO [Yu et al., 2022] and sequential methods, such as HATRPO [Kuba et al., 2022] , HAPPO [Kuba et al., 2022] and A2PO [Wang et al., 2023a] . Clearly, different agents in the two benchmarks should learn diversified policies. Hence, we switch off the parameter sharing setting for HAPPO, HATRPO, A2PO and our MADPO, and keep sharing parameter in MAPPO. In this work, we conduct experiments of 5 random seeds on 10 scenarios of MA-Mujoco and 10 scenarios of Bi-DexHands.We also conduct statistical testing experiments by using rliable [Agarwal et al., 2021] . Since the environments we used in this work do not have a round end score, we choose the aggregate interquartile mean (IQM) sample efficiency test of rliable for evaluation. The interquartile mean (IQM) computes the mean scores of the middle 50% runs, while discarding the bottom and top 25%.Here, we evaluate the performance across multiple tasks, and the total number of runs is n × m, where n is the number of trials for one task, and n = 5 in this paper. m is the number of tasks. IQM test is more robust than the mean and has less bias than the median. The experimental details can be found in Appendix B.  
ablation study: 
 We also investigate the efficiency of conditional CS policy divergence compared to other widely used exploration incentives as shown in Fig. 5a and Fig 5b . Here, no incentive presents disabling the intrinsic reward for training. We can clearly observe in Fig. 5a that the conditional CS policy divergence and KL-divergence achieve significant improvements compared to the popular policy entropy. These results indicate the effectiveness of mutual PDM framework, which takes the information from preceding agent into account. Additionally, the conditional CS policy divergence outperforms the famous KL-divergence empirically, particularly in MA-Mujoco tasks. This is because the KLdivergence implicitly minimizes the entropy of the current policy when maximizing the divergence, which can be detrimental to exploration. In contrast, the CS policy divergence maximizes policies' novelty and, more importantly, the Rényi entropy for efficient exploration. Fig. 5b demonstrates that in the aggregate evaluation, the CS-divergence outperforms other incentives with narrower confidence interval, indicating its better stability than KL-divergence. Fig. 6 shows the experiments of parameter sensitivity. In this experiment, λ controls the influences of inter-and intra-agent policy divergence. When λ = 0, the inter-agent policy divergence is disabled, and when λ = 1, the intra-agent policy divergence is disabled. We can observe a consistent degradation in performance when any one aspect of the mutual policy divergence is turned off, thus confirming the significance of our method. When λ = 0.2, the proposed method achieves the highest reward, whereas excessive influence from inter-agent divergence with λ = 0.5 is harmful. Parameter σ controls the kernel width in Cauchy-Schwarz divergence, impacting the influence of the mutual PDM. We find that MADPO is slightly sensitive to σ, behaving similarly to the entropy coefficient in MAPPO. 
conclusion: 
 In this work, we present MADPO, a sequential updating MARL method equipped with mutual policy divergence maximization for efficient exploration in heterogeneous tasks. By leveraging the sequential updating paradigm, MADPO maximizes intra-agent policy divergence to enhance exploration and inter-agent policy divergence to promote heterogeneity. However, maximizing traditional divergence measurements can lead to instability and lack of direction in MARL. To tackle this issue, we propose conditional Cauchy-Schwarz policy divergence to quantify the distance between policies. The conditional Cauchy-Schwarz policy divergence possesses favorable properties and provides a stable entropy-guided incentive for sequential exploration. We evaluate the performance of MADPO on two challenging heterogeneous tasks, MA-Mujoco and Bi-Dexhands. We observe that the proposed Mutual PDM outperforms entropy-based methods since it consider both previous and preceding information. Moreover, we verify the efficiency of the conditional Cauchy-Schwarz policy divergence in terms of stabilizing and guiding the exploration. Totally, the results demonstrate the effectiveness of MADPO, achieving state-of-the-art performance in complex multi-agent scenarios. The main limitation of this work is that when the number of agent increases, the proposed method may require more ram to restore previous information. We will investigate effective representation methods for previous information in the future.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This work does not poses a risk of misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We have provided the URL of assets used in this work in B.1.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: A.1 Proofs of the Proposition 1 Proposition 1. Given a policy to be updated π and a fixed policy π, and their α-order Rényi entropy H α (π) = 1 1-α log A π α (a|s)da = 1 1-α E a∼π log π α-1 (a|s), then we have:EQUATIONProof. At state s, consider A as the action set, a is the random variable, we can rewrite the right side of Eq. 12 as follows,EQUATIONwhere the first term in Eq. 14 is the 2nd-order Rényi cross entropy between π and π. Thus, using Gibbs inequality, we haveEQUATION)EQUATION)EQUATIONwhich finish the proof.Proposition 2. Given a policy to be updated π and a fixed policy π with a finite action set A = {s 0 , ..., s n } at state s, then the CS divergence of is lower bounded by:EQUATION)Proof. For two policies represented by the trajectories, the CS divergence between them at state s is defined as follows,EQUATION)Consider the quadratic mean of the π(a = a|s),A π(a|s)EQUATIONEQUATION)We also have A π(a = a|s)π(a = a|s) ≤ 1, and thenEQUATIONwhich complete the proof. In this experiment, we follow the official implement and hyperparameter settings of HAPPO and HATRPO1 [Kuba et al., 2022] , MAPPO 2 [Yu et al., 2022], and A2PO3 [Wang et al., 2023a] . We compare the proposed method with baselines on two popular heterogeneous environments, MA-Mujoco4 , and Bi-DexHands5 . For MA-Mujoco, the commom hyperparameter are listed in Tab. 1, and the different hyperparameters in each scenarios are listed in Tab. 2. For Bi-DexHands, the commom hyperparameter are listed in Tab. 3, and the different hyperparameters in each scenarios are listed in Tab. 4. The experiments were conducted on a PC with NVIDIA RTX3090 GPU, Intel Xeon 64-core CPU, and 64GB Ram.Full results of 10 scenarios in MA-Mujoco and 10 scenarios in Bi-DexHands are shown in Fig. 7 and Fig. 8 . We can make two observations on results of MA-Mujoco tasks. First, MADPO demonstrates superiority in terms of both reward maximum and learning speed, highlighting its effectiveness in exploring novel policies. Second, MADPO exhibits the lowest variance compared to other methods in most scenarios, indicating its training stability. In the more challenging Bi-DexHands tasks, we find MADPO outperforms baselines in most scenarios, confirming the effectiveness of MADPO in complex coordination tasks.We also conduct the experiments of different updating orders in Ma-Mujoco, as indicated in Fig 9 .Here, each agent controls one joint of one leg, and the joints in the same position on the legs have the same specilization. The Rand. order represents updating agents randomly. The Def. order represents updating agents in the default order in Ma-Mujoco, where agents are grouped according to the legs they belong to. For example, the default updating order can be: right thigh joint, right leg joint, right foot joint, left thigh joint, • • • . The Spec. order represents updating agents according to their specilization, and can be: right thigh joint, left thigh joint, right foot joint, left foot joint, • • • . We can observe that the random updating order outperforms the other orders. We believe that this is because our framework can benefit from various updating orders. For example, if the current agent share the same specilization as the preceding agent, maximizing the inter-agent divergence can enhance exploration. On the other hand, if the current agent differs from the preceding agent, maximizing the inter-agent divergence can promote heterogeneity.In Fig 10 , we compare the performance between different parameter settings using IQM aggregate test. We can observe that MADPO is a little sensitive to parameter σ. However, it outperforms HAPPO in a reasonable range of σ. Additionally, we can also individually tune σ for special task for further performance improvement. We also observe that MAPDO is a little sensitive to the parameter λ, yet it consistently shows better performance than HAPPO.Tab. 5 shows the running time of MADPO and other methods. Compared to MARL baselines, MADPO only introduces a negligible extra time cost.We do not foresee an obvious negative impart by conducting the experiments included in this work, since we evaluate methods in a controlled simulation environment. However, We are also aware that recent works [Radosavovic et al., 2024 , Handa et al., 2023] tested RL algorithms on real-world environments. This may raise concerns regarding the potential personal hazards caused by agent exploration in real world. To address this issue, one possible approach is to define safety behaviours to restrict the actions of agents [Feng et al., 2023a] or perform evaluation in safe simulation environments [Ji et al., 2023] preliminarily.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: We confirm that we accurately and clearly claim the contributions and the scope of this work in the abstract. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.https://github.com/PKU-MARL/HARLhttps://github.com/marlbenchmark/on-policyhttps://github.com/xihuai18/A2PO-ICLR2023https://github.com/schroederdewitt/multiagent_mujocohttps://github.com/PKU-MARL/DexterousHands 


Decision: The paper presents Multi-Agent Divergence Policy Optimization (MADPO), which introduces a mutual policy divergence maximization framework aimed at enhancing exploration and heterogeneity in MARL. The method leverages a sequential updating scheme, allowing agents to learn from preceding ones, and proposes the use of conditional Cauchy-Schwarz (CS) divergence to address the stability and directionality issues in traditional divergence measurements. The paper is well-grounded in theory, with clear explanations of how the proposed method addresses these stability and directionality challenges in policy divergence measurements. The results in heterogeneous multi-agent environments demonstrate that MADPO outperforms existing methods, providing strong empirical evidence for the effectiveness of the proposed approach. The reviewers are satisfied with the addition of statistical significance tests, as well as comparisons to related works and other baselines. Based on this, the paper is recommended for acceptance.

Reviews: review: paper_summary: paper_summary: This paper introduces a novel multi-agent reinforcement learning (MARL) method called Multi-Agent Divergence Policy Optimization (MADPO), which enhances exploration and heterogeneity through a mutual policy divergence maximization framework. MADPO leverages a sequential updating scheme and quantifies discrepancies between episodes and agents, termed intra-agent divergence and inter-agent divergence, respectively. To address the instability and lack of directionality in traditional divergence measurements, the paper proposes using conditional Cauchy-Schwarz divergence to provide entropy-guided exploration incentives. Experiments demonstrate that the proposed method outperforms state-of-the-art sequential updating approaches in two challenging multi-agent tasks with various heterogeneous scenarios.
strength_weakness: strength_weakness: 1.  The paper lacks analysis and comparison with relevant literature on sequential decision-making, such as:
   - Liu J, Zhong Y, Hu S, et al. Maximum Entropy Heterogeneous-Agent Reinforcement Learning[C]//The Twelfth International Conference on Learning Representations.  (This paper extends SAC to heterogeneous sequential decision-making scenarios, and the relationship between this work and the current paper remains unclear.)

2. It is unclear whether the intrinsic reward method proposed in this paper can ensure that the resulting trained policies are consistent with the original policies.
questions: questions: 1. Could you provide a detailed comparison between your proposed MADPO method and the approach presented in "Maximum Entropy Heterogeneous-Agent Reinforcement Learning" by Liu et al.? Specifically, how does MADPO improve upon or differ from this method in terms of handling heterogeneous sequential decision-making scenarios?

2. I may have missed some details, but could you clarify whether the intrinsic reward method in MADPO ensures that the trained policies remain consistent with those optimized solely based on the original rewards?
limitations: limitations: The authors have addressed the limitations of their work and discussed potential negative societal impacts in accordance with the guidelines.
paper_summary: paper_summary: This paper is situated in the problem setting of heterogeneous cooperative agents, under the sequential update framework. The paper introduces the novel MADPO algorithm, in which agents maximize the Cauchy Schwarz divergence between agents and between episodes of data gathered by the same agent, to improve exploration. Empirical validation is performed on the Multi-Agent Mujoco and Bi-DexHands benchmark suites, demonstrating that the MADPO outperforms baselines.
strength_weakness: strength_weakness: 1. The motivation of the paper is not altogether clear to me. The paper seems to suggest that exploration is more challenging in the sequential update setting, necessitating devoted algorithms. Why would this be the case? 
2. In many of the presented domains, the improvement of MADPO over the next best method is not very large. Sometimes, confidence intervals of MADPO overlap those of the next best method. Can the authors provide statistical significance tests for the main results in Figures 2 and 3, comparing MADPO to the next best method?
3. Some minor suggestions:
- Please check your paper carefully for typos, as there are quite a few: 
    - Line 89: "connecting link dimension curse"? Not sure what this is
    - No period after Figure 4
    - Trust interval -> confidence interval 
    - Lacking 'and' at line 174
    - Line 204: conditoned -> conditioned
    - Line 216: extra "of" 
- Please be sure to state the number of trials in the main text. It is mentioned in the Neurips checklist, but I could not find it  in  the main text
- Please make the colors of the methods the same for both domains (i.e. pick 1 color for MADPO and be consistent with it)
questions: questions: 1. How sensitive is the algorithm to the scale of the divergence rewards? Have you done a study on this? 
2. On the intra-policy divergence: is the policy updated every episode? If not, then wouldn't the intra-policy divergence reward often be 0? 
3. Line 180 states that it would be challenging to define an inter-agent divergence in the simultaneous update scheme. Why not consider the divergence between $\pi^i_k$ and $\pi^j_{k-1}$? But this does not seem any more challenging to compute, and can be computed under  CTDE assumptions.
4. Would it be possible to implement this exploration scheme in the CTDE setting? If so, it would be interesting to see how well the method performs. 
5.   Proposition 2 states that the CS divergence has a lower bound. Does it also have an upper bound?
limitations: limitations: yes
paper_summary: paper_summary: The paper proposes a novel training objective where it encourages the policies to diverge from each other and from the previous policy under heterogeneous multi-agent tasks based on sequential recently proposed sequential policy update. It utilizes CS divergence for calculation of "distance" between policies for tractable and stable optimization compared to KL divergence. The evaluation is done in high-dimensional multi-agent mujoco and and bi-dexhands environments, outperforming existing state-of-the-art sequential algorithms.
strength_weakness: strength_weakness: - The evaluation is hard to judge whether the proposed method is actually performs better than the baselines, this is a deal breaker. I suggest the authors also incorporate aggregate quantities from https://agarwl.github.io/rliable/

I'm willing to increase the score if the authors show that the improvement is statistically significant
questions: questions: - Is it possible to have a "cyclic" problem where the 1st, 3rd, 5th, ... (and also 2nd, 4th, 6th, ...) policies have the same behavior despite optimizing the proposed training objective?
- Can the authors explain why CS is chosen over Jensen–Shannon divergence (JSD)?
- Is there a guideline for tuning the coefficients for the intrinsic rewards?
limitations: limitations: Minor comments
- line 36, wrong citation format
- line 193 and line 217, Ep. 5 should be Eq. 4
paper_summary: paper_summary: The authors study MARL in heterogeneous settings, where agents are not allowed to share their parameters, and make use of the sequential updating scheme under the CTDE schema. They propose a method which exploits the preceding information to improve exploration and heterogeneity sequentially. This method is equipped with a mutual policy divergence maximization framework, which utilizes the discrepancies between episodes to enhance exploration and between agents to heterogenize agents. Interestingly, the authors propose the conditional Cauchy-Schwarz divergence to provide entropy-guided exploration incentives.
strength_weakness: strength_weakness: - The improvement over the baselines (standard KL-divergence, entropy term, no incentive) does not seem to be quite consistent in the ablation study, due to (a) high variance in the results of the no incentive, and (b) very close improvement over the KL divergence baseline in terms of best episodic reward in 2 out 3 tasks.

- Since the CS divergence is new in MARL and RL, a table containing the running times of the evaluated algorithms is missing. How costly is the CS divergence?
questions: questions: - The authors mention: "To the best of our knowledge, there is no exploration method that can adapt to both heterogeneous scenarios with sequential updating and homogeneous scenarios with simultaneous updating". But can the proposed method adapt to homogeneous scenarios with simultaneous updating? No experiments in such settings have been provided. Could the proposed intrinsic rewards be used to improve exploration in MARL settings with homogeneous agents?

- Why do the authors use $\lambda$ and $1 - \lambda$ for weighting the intrinsic rewards, instead of arbitrary weights (not in a convex combination)? How important is it to the performance?
limitations: limitations: The authors provide limitations of their work.

Comments: title: Thanks for the response
Thanks for the response
Thanks for the response
comment: Thank you for your response. We are delighted to hear that our rebuttal addressed your concerns well.
Thank you for your response. We are delighted to hear that our rebuttal addressed your concerns well. 

To address the issue you mentioned, even though it is unlikely to occur, we need to quantify the behaviors of each policy or measure the divergence among more than two policies [1]. However, quantifying the policy behaviors is challenging due to the difficulty of designing a best behavior representation method. Recent works share insights for behavior representation, such as trajectory distributions [2] and state-action pairs [3]. We will investigate the efficient representation approach and choose a more powerful divergence [1] for our work in the future. 


[1] Lu Mingfei, et al., "Measuring generalized divergence for multiple distributions with application to deep clustering", Pattern Recognition, 2024.

[2] Dhruva Tirumala, et al., "Behavior Priors for Efficient Reinforcement Learning", JMLR, 2022.

[3] Huang Zhiyu, et al., "Efficient Deep Reinforcement Learning With Imitative Expert Priors for Autonomous Driving", IEEE TNNLS, 2023.
Thank you for your response. We are delighted to hear that our rebuttal addressed your concerns well. 

We agree that Sun et al. [1] did great work and offered a monotonic improvement guarantee for decentralized agents in MAPPO and IPPO. They ensured the trust region optimization by bounding the independent ratio. However, we would like to highlight that, decentralized agents are not equal to hetergeneous agents. In [1], when bounding the ratio, the authors noted the  necessity for paremeter sharing (please see the statement above Eq. 16 in [1]). Thus, when switching off the paremeter sharing, it remians unclear whether the guarantee proposed in [1] holds. 


[1] Sun Mingfei, et al., "Trust Region Bounds for Decentralized PPO Under Non-stationarity", AAMAS, 2023.
I have read the common response and the rebuttal to my specific review. Thanks for going over my review in detail. I am satisfied with the rebuttal to most of my points, except for point 6 (see below). The rebuttal underlines my belief that this is a good paper which should be accepted. However, my score already reflects this belief, so I will not change it. 

Recent work by (Sun et al. AAMAS 23)[https://arxiv.org/pdf/2202.00082] shows that even decentralized IPPO maintains the monotonic improvement guarantees by maintaining an approximate trust region, so I disagree that MAPPO w/o PS would lose that guarantee. It would be interesting if the authors could show that their proposed exploration technique works for the simultaneous decision-making approaches as well. However, this is an auxiliary point that is not directly relevant to the acceptance of this paper.
Thanks the authors for the detailed answers and also for incorporating an improved evaluation metric. I do appreciate the effort the authors took to improve the paper. I'm willing to increase my score from 6 to 7.

One additional question: Can the authors give a quantitative or qualitative analysis on how the behaviors of the policies differ? As we discussed, it is possible that the policies alternate between a few behaviors. If this is the case, future work could use this insight to further improve the algorithm.
I would like to thank the authors for addressing my concerns and questions. I increased my rating score.