Measuring Mutual Policy Divergence for Multi-Agent Sequential Exploration

Thanks for your positive comments. We address your concerns as follows:

(1) The improvement over baselines

We have re-evaluated our method against the baselines using an aggregate statistical test. We have quantified the interquartile mean (IQM) across tasks of our method and baselines. Please refer to the author rebuttal and the attached PDF for more details.

In the PDF of the author rebuttal above, Figure 2 (a) and (b) show the performance comparison with other exploration strategies. We can observe that in terms of IQM reward across multiple tasks, the proposed method consistently outperforms other methods in MA-Mujoco, with small overlap. Besides, the CS-divergence shows more stability and has smaller confidence intervals in MA-Mujoco compared to other methods. In the Bi-Dexhands environment, it shows a significant improvement gap in the last 10m steps and achieves the highest best episodic reward.

(2) The running time comparison

We have compared the running time of our methods and baselines. Please refer to the author rebuttal and the attached PDF for more details.

From Table 1 in the attached PDF in the author rebuttal above, we observe that compared to sequential MARL baselines, MADPO only introduce a negligible extra time cost.

(3) Adapt to homogeneous tasks

Homogeneous scenarios can be regarded as a special case of heterogeneous scenarios. Thus, yes, our method can be adapted to homogeneous scenarios. Existing methods ensure homogeneous agents by enabling parameter sharing. Under such a setting, the intra-agent divergence maximization is unnecessary, since agents should receive a homogeneous intrinsic reward. Consequently, when setting $\lambda$ to $0$, the Mutual PDM can be adapted to homogeneous tasks with simultaneous updating.

Due to the page limit of the attached PDF, we present here the following table, which shows the aggregate IQM best episodic rewards comparison across $10$ tasks and $5$ random seeds in MA-Mujoco, between different exploration strategies when adapted to MAPPO. Here, we disenable the parameter sharing. The results show that as an exploration incentive in MAPPO, the Mutual PDM achieves better performance than the entropy, indicating its effectiveness when adapted to homogeneous agents with simultaneous updating.

(4) Why $\lambda$ and $1-\lambda$ for weighting

We use $\lambda$ and $1-\lambda$ here to balance the two components of mutual policy divergence maximization for the following reasons.

First, it is necessary to scale the two types of divergences to the same range since they share the same range of values. In different tasks with different requirements for heterogeneity and exploration ability, adjusting the degree of the two components is necessary.

Even in tasks requiring heterogeneity and exploration ability both highly, we can tune the other parameter $\sigma$ to adjust the scale of the mutual divergence. Therefore, jointly tuning $\lambda$ and $\sigma$ can achieve the desired parameter combinations, and is sufficient for MADPO to adapt to different tasks. Compared to arbitrary weights, this parameter setting facilitates parameter tuning, since we can use $\sigma$ to control the sacle of mutual divergence and within use $\lambda$ to weighting the two parts.

Additionally, using other weighting methods, such as no-linear weighted mean or boosting learning, may introduce extra parameters and computational costs. Due to the limited time for rebuttal, we will investigate the performance of different weighting methods in the future.

First, we would like to express our gratitude for your careful review of our work, as well as for your positive comments and insightful suggestions.We address your concerns as follows:

(1) Motivation of our work

The sequential updating scheme offers a novel solution to heterogeneous MARL, enabling agents to access information from preceding ones.

Our focus is on designing a sequential exploration strategy within this framework. Simply applying simultaneous exploration approaches, such as entropy or intra-agent divergence, to sequential methods may not fully leverage the available sequential information.

Besides, in heterogeneous tasks, exploration should not only aim for novel state and policy discovery but also enhance heterogeneity. Existing sequential methods often disable parameter sharing to accommodate heterogeneity, which is a passive approach lacking active guidance.

Therefore, in this work, we propose maximizing mutual policy divergence to actively enhance exploration and heterogeneity.

(2) Statistical significance tests

We believe that results presented with confidence intervals are relatively convincing in terms of statistical significance. To further evaluate the overall performance of MADPO, we utilize rliable, a powerful statistical testing tool recommended by Reviewer 3yBc. We choose the aggregate interquartile mean (IQM) across multiple tasks as the metric for the sample efficiency test. Please refer to the author rebuttal and the attached PDF for more information.

Figure (1) in the attached PDF shows that MADPO outperforms other baselines in terms of sample efficiency with a significant improvement gap in most tasks, and achieves the highest best episodic rewards in all tasks consistently.

(3) Minor suggestions

Thank you for pointing out the typos in our paper; we have corrected them accordingly. We have also adjusted the figures to highlight our method in red and included all experimental details in the main text.

Regarding the statements in Line 89, we would like to clarify that in MATRPO [1], proposed by Li and He, a communication method using connecting links is proposed for sharing information among agents. However, as the number of agents increases, the additional cost of these connecting links cannot be ignored.

(4) Sensitivity to the scale of divergence reward

In CS divergence, the kernel width $\sigma$ controls the scale of divergence. We conducted parameter sensitivity experiments, as presented in the original manuscript, which demonstrate that MADPO is somewhat sensitive to $\sigma$. Additionally, we performed an IQM test to further investigate this sensitivity in the rebuttal. Please refer to the author rebuttal and the attached PDF for more information.

We can observe from Figure 2 (c) that, even though MADPO is slightly sensitive to $\sigma$, it outperforms HAPPO in a reasonable range of $\sigma$ across several tasks. Note that we show here the aggregate results of parameter sensitivity experiments, and we can tune $\sigma$ in each tasks individually for further improvement.

(5) Policy updating in intra-agent divergence maximization

The policy is updated every episode. The intra-agent policy divergence measures the difference between one agent’s current policy and its policy in the last episode. Thus, except for the first episode, once the agent’s policy is improving, the intra-agent policy divergence would not be zero. And the policy is updating according to the divergence.

(6) Concerns about CTDE

First, we would like to clarify that our MADPO is based on CTDE. Because MADPO has a global V network and multiple agent policy networks and follows CTDE settings. The centralized V network generates a V function for training agent networks, while decentralized agents interact with the environment individually, as indicated in Algorithm 1 of the original manuscript.

Computing the divergence between $\pi_k^i$ and $\pi_{k-1}^j$ is not practically challenging indeed. However, diversifying agents in simultaneous updating methods, such as MAPPO, requires the non-parameter sharing setting, under which MAPPO will lose the monotonic improvement guarantee, even though it may bring better performance [2]. On the contrary, in sequential methods, such as HAPPO and our MADPO, the objective naturally takes the preceding information into account, and maintains the monotonic improvement guarantee in heterogeneous tasks.

Therefore, we made the statement that adapting the inter-agent divergence maximization to simultaneous updating methods is theoretically challenging. Additionally, we are also aware that adapting the proposed model to value-based methods, such as QMIX, is feasible, since it does not have the monotonic improvement issue.

(7) Upper bound of CS divergence

The CS divergence has an upper bound. According to Proposition 1 in the original manuscript, the upper bound of CS divergence $D_{CS} (\pi||\overline{\pi})$ is the sum of two 2-order Rényi entropies: $D_{CS} (\pi||\overline{\pi}) \leq \frac{1}{2}\mathcal{H}_2(\overline{\pi})+\frac{1}{2}\mathcal{H}_2(\pi).$ Furthermore, given a finite action set $\pmb{A}=\\{a_0,...,a_n\\}$, the entropy $\mathcal{H}_2(\pi)$ has an upper bound $\log(n)$ when $\pi$ is a uniform distribution. Thus, the CS divergence is upper bounded by $\log(n)$, where $n$ is the number of the actions.

[1] Li, Hepeng, and Haibo He., "Multiagent trust region policy optimization.", IEEE TNNLS 2023.

[2] Kuba, J. G., et al., "Trust Region Policy Optimisation in Multi-Agent Reinforcement Learning.", ICLR 2022.

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.

Thanks for your positive comments. We address your concerns as follows:

(1) The aggregate evaluation metrics

Thanks for your constructive suggestion. We have re-evaluated our method by using this powerful toolbox rliable. Please refer to the author rebuttal and the attached pdf for more information. Since the environments used in this study does not have a round end score, we choose the aggregate interquartile mean (IQM) across tasks as the evaluation metric. The results in Figure 1 of the PDF demonstrates that, in terms of aggregate IQM, MADPO achieves better performance and has smaller confidence intervals in most tasks. We believe these results has the statistical significance.

(2) A cyclic similarity problem in learned policies

It is an interesting question, and we believe the probability of such a situation occurring is extremely low. In our MADPO, agents are encouraged to learn different policies from the preceding ones, yet are not to be guided to behave like another one. We admit that there is a chance that one agent can autonomously imitate the one before the preceding one by a divergence incentive, as you mentioned. However, the probability is extremely low due to (a) there is no direct guidance for imitation, (b) agents are also goaded to diversify based on their previous policies (the intra-agent policy maximization), and (c) the CS divergence incentive can bring further stochasticity to agents by implicitly maximizing the policy entropy.

(3) Why choose CS divergence over JS divergence

JS divergence fixes the problem that CS divergence may explode in MARL scenarios, since it has a constant lower bound and upper bound. However, the JS divergence is not the best choice. The JS divergence between the current policy and a fixed policy is defined as follows,

D_{JS}(\pi||\overline{\pi}) &= \frac{1}{2}D_{KL}(\pi||\frac{\pi+\overline{\pi}}{2}) + \frac{1}{2}D_{KL}(\frac{\pi+\overline{\pi}}{2}||\overline{\pi}) \\\\ &=\frac{1}{2}[\mathcal{H}(\pi,\frac{\pi+\overline{\pi}}{2})-\mathcal{H}(\pi) + \mathcal{H}(\frac{\pi+\overline{\pi}}{2},\overline{\pi})-\mathcal{H}(\overline{\pi})]. \end{aligned}$$ It still has the same drawback as KL divergence, i.e. minimizing the policy entropy $\mathcal{H}(\pi)$ when maximizing the divergence, which is harmful to exploration. On the contrary, as indicated in Proposition 1, our method implicitly maximizes the policy when maximizing the divergence, which can bring more stochasticity to policies and benefit exploration. Hence, our method is able to provide agents with entropy-guided divergence incentives for exploration. ## (4) Guideline for tuning parameters We have evaluated MADPO under different parameter settings by using the aggregate IQM test of ***rliable***, and thanks again for recommending this method. Please refer to the author rebuttal and the attached PDF above for the experimental results. The results show that our MADPO achieves better performance than HAPPO in a reasonable range of $\sigma$. Based on the empirical results, here we can give a guideline for tuning $\sigma$ and $\lambda$: (a) set $\sigma$ as commonly used values, such as 1e2 or 5e2; (b) set $\lambda$ based on the task type, but not more than 0.5. ## (5) Minor suggestions Thanks for pointing out the wrong reference and citation formats, and we have corrected them accordingly.

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.

Thanks for your positive suggestions. We address your concerns as follows:

(1) Comparison with HASAC

Liu et al. proposed Heterogeneous Agent SAC (HASAC) by extending maximum entropy RL into heterogeneous MARL [1]. However, we would like to clarify that our MADPO is an on-policy MARL method, while HASAC is based on an off-policy manner. Thus, HASAC naturally enjoys higher sample efficiency than other on-policy sequential updating methods, such as HAPPO, HATRPO and A2PO. However, as an off-policy method, HASAC incurs significant time costs.

In terms of handling heterogenous tasks, HASAC shares the similar idea in HAPPO, decomposing the joint Q function (joint advantage function in HAPPO) to individual ones conditioned by other agents’ policies. Nevertheless, HASAC lacks an active optimization objective to guide agents toward greater heterogeneity and diversity. In terms of enhancing exploration, HASAC adopts the strategy of SAC by incorporating a policy entropy term into the reward. In contrast, MADPO actively maximizes the stable mutual divergence of policies while implicitly maximizing the policy entropy, providing a stronger incentive for exploration and heterogeneity, as presented in Section 4 of the original manuscript.

To comprehensively compare MADPO with other sequential updating approaches, we conducted overall performance and wall time experiments for HASAC and our method. Please refer to the author rebuttal and the attached PDF for more information. We can observe from Table 1 and Figure 4 in the attached PDF that, although HASAC achieves a performance improvement, its huge time costs cannot be ignored.

Additionally, we recognize that the proposed mutual policy divergence maximization can be adapted to off-policy methods as well, which is our future research direction.

(2) Consistency between policies trained on MADPO and the original reward

As an intrinsic reward, mutual PDM in MADPO aims to apply incentives when the change of extrinsic reward extrinsic rewards does not lead to policy improvements. Therefore, in MADPO, when the episode reward is increasing, the original reward part is dominant, resulting in policies that keep consistency with those trained on extrinsic rewards. On the other hand, when the reward struggles to improve, indicating agents should explore the environment, the intrinsic reward provides guidance to encourage agents to escape from suboptimal policy. In such cases, the policy generated may deviate from the original policy. To tackle this issue, we use parameter $\sigma$ to control the scale of the intrinsic reward, ensuring consistency between policies trained on the original and proposed rewards.

We have conducted the experimental comparison with the $no$ $incentive$ setting. We choose here the interquartile mean (IQM) across tasks as the metric. Please refer to Figure 2 of the attached PDF in author rebuttal above. The results indicate that mutual PDM in MADPO leads to significant policy improvements over the original reward. We have also conducted the parameter sensitivity experiments for $\sigma$, revealing that the mutual PDM with a reasonable choice of $\sigma$ will not cause performance degradation.

[1] Liu, Jiarong, et al., "Maximum Entropy Heterogeneous-Agent Reinforcement Learning", ICLR 2024.