Enhancing Diversity In Parallel Agents: A Maximum State Entropy Exploration Story

We sincerely appreciate the reviewer's time and effort in evaluating our work, and we are grateful for the opportunity to provide further clarifications. We also thank the reviewer for highlighting grammatical and formatting issues, which we will address in the final version. Additionally, we are pleased that our contribution on applying the exploration approach to offline RL was appreciated.

Weaknesses: I feel the significance of this work is lacking.

We hear the reviewer's concerns about the simple domains and baselines. We will address them in detail below. First, we want to spend a few words to get on the same page with the reviewer on the nature of this work. The core contributions of this paper are conceptual and theoretical: The formulation of a reward-free exploration objective tailored to the parallel MDP setting (Section 3), its theoretical characterization through novel concentration bounds (Section 4 and Theorem 4.1), the design of a specialized policy gradient procedure (Section 5). While we corroborate the latter contributions with a preliminary empirical analysis, this is not meant to close the gap between foundations and application in the real world, which we believe requires a substantial amount of additional work for not just a follow-up but a series of papers. We kindly ask the reviewer to also weigh our main contributions in their evaluation and to reward the paper for its seminal potential.

If a core motivation of this work is practical applications, then why are the environments so simple?

Please note that we do not claim the paper provides a solution for real-world applications, but that this research line is motivated by real-world applications. We do not aim to close the gap with applications with our work, which, being just the first in this direction, aims to introduce the problem formally and to provide the theoretical foundations for future works.

Why was training only shown for 2, 4, and 6 agents?

Given the gridworld’s complexity, a few agents are sufficient for successful navigation, and adding more does not significantly improve performance due to state space constraints. In experiments on more complex scenarios, we expect a much larger number of learners to be beneficial for the exploration. For completeness, we will extend Figure 7 in the Appendix to show performance with more agents, highlighting how increasing their number maximize the objective until reaching a plateau.

I would like to see a small discussion around the higher variance introduced with more agents.

Variance in performance is an important aspect, which we will discuss further in the paper. While a single agent with more trajectories can achieve similar expected performance, parallel learners naturally exhibit smaller variance around the mean. This supported by Theorem 4.1 and the experiments in Figures 2 and 3 highlight the benefits of parallel training. A single agent tends to explore the entire state space, leading to higher variance in state distribution and greater sample complexity compared to the parallel case, in which the policies are less stochastic.

Is there a reason why the gap in state entropy decreases as the number of agents increases?

In designing the experiments, we aimed for a fair comparison. Comparing parallel agents, each playing one trajectory at a time against a single agent with the same interaction budget, would overestimate the parallel learners' advantage. Instead, we chose a more challenging setup where the single agent has a significantly larger interaction budget than each individual parallel agent. This setup allows the single agent to develop a stronger policy, reducing the gap in state entropy. However, when considering the offline RL setting, the advantage of parallel learning becomes more evident due to the higher variance induced by the policy of the single agent that need to visit more states, respect to a specialized parallel policy that concentrate faster.

Baselines makes it hard to place this work within the literature.

As our paper is the first to address this specific problem of state entropy maximization in parallel MDPs, we do not have a direct baseline with which to compare. However, we did compare against a random policy (gray bar in Figure 3 and 4) and a single policy, which can be seen as replicas of a MaxEnt algorithm across the parallel MDPs (the objective is the same as MaxEnt, although we used our implementation instead of the one of the original paper). Those are the baselines that the reviewer also mentioned, and we believe they are the most relevant. We will make this information clearer in the paper.

We sincerely appreciate the reviewer's time and effort in evaluating our work and are grateful for the opportunity to provide further clarifications. We also thank the reviewer for pointing out the typo errors; we will address them in the final version.

If the motivation is for the speed, how gradient descent step slow down the computation?

We are not fully sure to understand reviewer's question here. We provide a tentative reply below. If the reviewer feel we are not addressing their point, we will be more than happy to provide further considerations.

The discussion on the cost of the gradient calculation is an excellent point. We have not analyzed the computational cost of calculating the gradient at each step, which is negligible in our experiments. However, in more complex domains, a vectorized calculation of the gradient (which is what the reviewer suggests?) will definitely be beneficial from the computational cost perspective. We will provide this important consideration in the manuscript.

As a result, they induce distributions with ‘lower’ entropy compared to a single policy covering the entire space. Can the authors elaborate on how to get this conclusion from Theorem 4.1?

We acknowledge that we may not have fully clarified the use of the findings from Theorem 4.1, thus we will provide extended intuition in a revised version of the manuscript.

We designed Equation 1 to intrinsically motivate each agent to reduce the portion of the state space it explores, encouraging diversity. This leads to an induced empirical state distribution with lower entropy due to the small size of the support of the states visited by each single agent.

As outlined in Theorem 4.1, a lower entropy state distribution means that fewer samples are needed to realize the target distribution approximately.

We sincerely appreciate the reviewer's time and effort in evaluating our work, and we are grateful for the opportunity to provide further clarifications.

Why are the agents incentivized to be different rather than all become the same policy with uniform coverage over states? Is it because if the entropy of each agent’s distribution is low, then the empirical estimation error will be lower? Is the efficiency of parallel exploration better than single-agent exploration shown by sample efficiency or convergence rate?

Precisely, the reviewer is right: If each agent's policy has low entropy, then the empirical realization will concentrate faster to the target distribution. This finding is supported by Theorem 4.1. Since the entropy term appears in the numerator of the samples lower bound, we will need fewer samples (smaller n) to concentrate around the target distribution. Even if a policy with uniform expected coverage over the states exists (it does not typically), a single realization from this policy may not have uniform coverage. Appropriately specialized policy can still be preferable.

Consider a two-room gridworld with two specialized parallel agents, each assigned to a specific room. In a single realization, the state distribution will be uniform because each agent deterministically explores its designated room.
In contrast, a single agent following a maximum entropy policy has a higher variance in its state distribution. This means that it is not guaranteed to visit both rooms in a single realization, as its exploration is probabilistic rather than deterministic.

In parallel exploration, how does the entropy of each individual dataset look like and how different (e.g., KL divergence) are the datasets between different agents?

Thanks to the insightful question posed by the reviewer, we can further clarify that under this objective formulation, each learner is intrinsically encouraged to minimize entropy along its own trajectory. This naturally leads to the emergence of specialized policies across different regions of the state space, as illustrated in Figure 10. Indeed in the same figure where the action distributions are plotted, in the parallel case each agent tends to follow a more deterministic policy, naturally dividing the state space among the m agents. In contrast, a single agent aiming to maximize the entropy of its state distribution spreads its actions more uniformly.

In line 240-247, why can the log tricks be applied when $d_p$ is the mixture distribution, which does not only depend on $π_i$?

Since agents have independent policies, the gradient of each agent’s policy with respect to its parameters depends only on the states it has visited itself. Specifically, changing the policy parameter $θ_i$ of the i-th agent does not influence the trajectory generated by others.

Missing Reference

Regarding the references, we thank the reviewer for pointing out the interesting papers about coordination, which we will mention in an updated version of the manuscript. Below we explain how they differ from our work:

• Trajectory Diversity for Zero-Shot Coordination: We note that the paper addresses the problem of zero-shot coordination in a setting that is related to MARL. In MARL, multiple agents are acting in the same environment, where state transitions depends on the joint action $a_t = (a_{1t}, ..., a_{kt})$. In contrast, in our setting, multiple agents interact with independent copies of the environments, where the trajectories experienced are also independent. Moreover, even if in the Diversity objective considered in Section 4.2 and ours have some similarity in nature, their objective is not intended to maximize entropy, but only diversity among the policies. We appreciate the reviewer’s suggestion and will cite the paper in the final version to clarify our position.

• Maximum Entropy Population-Based Training for Zero-Shot Human-AI Coordination: As in the previous example, the main difference with this work is related to the construction of the environment. The definition of the Two-Player MDP positions this paper in the MARL setting, where the agents create dependent trajectories. For completeness in positioning, our paper will include it within our reference list.

We sincerely appreciate the reviewer's time and effort in evaluating our work and greatly value their insightful comments and suggestions. To clarify the key points of discussion and our design choices, we provide the following responses.

Why didn’t the authors compare the proposed approach with diversity-promoting methods like DIAYN or diversity-centered MARL approaches?

• MARL: We want to underline an important difference between the typical MARL setting and ours. In MARL, multiple agents are acting in the same environment. They need coordination because their trajectories are dependent. In our setting, multiple agents interact with independent copies of the environments. We show that coordination is useful in specializing the objective of each single agent, but their trajectories are independent. This makes the two settings significantly different.

• Celebrating Diversity in Shared Multi-Agent Reinforcement Learning: While the paper introduces policy diversification via mutual information maximization, it remains within the MARL framework, which we aim to differentiate from. Since the agents share policy parameters in a non-reward-free setting, we did not initially consider it. The key distinction is that our agents are fully independent, driven solely by the entropy of the mixture state distribution. We appreciate the reviewer’s suggestion and will cite the paper in the final version to clarify our position.

• DIAYN: We note that the intended use of DIAYN is substantially different than our setting. In the original paper, the authors use DIAYN to learn diverse skills, which are specialized policies or options that may be combined in the same environment to achieve complex goals. Here, we want to learn diverse policies to collect maximum entropy data across parallel simulators. However, we agree with the reviewer that DIAYN could be adapted to our setting, making the comparison potentially interesting. We will include a comparison with DIAYN in a revised version of the manuscript.

How would the method perform in more complex environments beyond gridworlds? Have the authors considered extending the approach to continuous state and action spaces?

We fully agree on the importance of extending our approach to continuous state and action spaces, which we see as a natural direction for future work. Our PGPSE algorithm can be adapted to these settings by computing trajectory entropy using non-parametric estimators, as explored in works like Task-Agnostic Exploration via Policy Gradient of a Non-Parametric State Entropy Estimate and Behavior From the Void: Unsupervised Active Pre-Training. This work serves as a foundational step in advancing parallel learning, focusing on defining the setting and establishing the theoretical basis for replica learners.