Enhancing Diversity In Parallel Agents: A Maximum State Entropy Exploration Story
Authors: Vincenzo de paola
Riccardo Zamboni
Mirco Mutti
Marcello Restelli
Venue: ICML 2025 poster (2025)
Keywords: Maximum State Entropy
Parallel Reinforcement Learning
Agents' Diversity
Primary area: reinforcement_learning

Abstract: Parallel data collection has redefined Reinforcement Learning (RL), unlocking unprecedented efficiency and powering breakthroughs in large-scale real-world applications. In this paradigm, $N$ identical agents operate in $N$ replicas of an environment simulator, accelerating data collection by a factor of $N$. A critical question arises: *Does specializing the policies of the parallel agents hold the key to surpass the $N$ factor acceleration?*
In this paper, we introduce a novel learning framework that maximizes the entropy of collected data in a parallel setting. Our approach carefully balances the entropy of individual agents with inter-agent diversity, effectively minimizing redundancies. The latter idea is implemented with a centralized policy gradient method, which shows promise when evaluated empirically against systems of identical agents, as well as synergy with batch RL techniques that can exploit data diversity.
Finally, we provide an original concentration analysis that shows faster rates for specialized parallel sampling distributions, which supports our methodology and may be of independent interest.

Enhancing Diversity In Parallel Agents: A Maximum State Entropy Exploration Story
Vincenzo De Paola Riccardo Zamboni
Mirco Mutti? Marcello Restelli
Abstract
comes an objective per se, in order to foster the collection of maximally informative data.
Parallel data collection has redefined Reinforce- ment Learning (RI.), unlocking unprecedented efficiency and powering breakthroughs in large- scale real-world applications. In this paradigm, N identical agents operate in N replicas of an envi- ronment simulator, accelerating data collection by factor of N. A critical question arises: Does spe- cializing the policies of the parallel agents hold the key to surpass the N factor acceleration? In this paper, we introduce a novel learning frame- work that maximizes the entropy of collected data in a parallel setting. Our approach carefully balances the entropy of individual agents with inter-agent diversity, effectively minimizing re- dundancies. The latter idea is implemented with a centralized policy gradient method, which shows promise when evaluated empirically against sys- tems of identical agents, as well as synergy with batch RL techniques that can exploit data diver- sity. Finally, we provide an original concentration analysis that shows faster rates for specialized par- allel sampling distributions, which supports our methodology and may be of independent interest.
A common formulation of the latter pure exploration setting is state entropy maximization (Hazan et al., 2019), in which the agent aims to maximize the entropy of the data distribu- tion induced by its policy. The state entropy objective has been widely studied in the literature, c.g., to provide data col- lection strategy for offline RI. (Yarats al., 2022; Park et al., 2023), experimental design (Tarbouriech & Lazaric, 2019), transition model estimation (Tarbouriech et al., 2020), and as surrogate loss for policy pre-training in reward- -free settings (Mutti & Restelli, 2020). All of the above uphold the status of state entropy maximization as a flexible tool for exploration. To this day, however, an important gap remains in how to deploy state entropy maximization on parallel simulators.
Let picture an illustrative example to guide our thoughts: A robotic arm control task. We may want the robot to be able to perform a wide range of tasks, such as interacting with a diverse set of objects. A good strategy is to exploit a simulator of the robotic arm to learn good manipulation policies in advance, instead of relying on costly online in- teractions, which exploration may be unsafe. Since not all of the future tasks may be known in advance, one could opt for state entropy maximization, in order to collect ex- ploration data once and for all. Collecting those data on complex simulators may be inefficient though, resulting in long simulation times. However, one crucial advantage of sampling in simulation rather than the physical system that the sampling process does not have to be sequential.
1. Introduction
Exploration, or taking sub-optimal decisions to gather in- formation about the task, lies at the heart of Reinforcement Learning (RL., Bertsekas, 2019) from its very foundation. When the task of interest is defined through reward func- tion, exploration shall be carefully balanced with the ploitation of the current information maximize the re- wards collected over time (Mnih et al., 2013). When task is not known at the time of the interaction, exploration be-
In many modern simulators (NVIDIA Isaac Sim; Genesis, 2024; Todorov et al., 2012), the process of learning is ac- celerated by instantiating vectorized instances of agents and environments simultaneously. Parallelization was shown to be a game-changing approach that allowed for umprece- dented performance in standard RL (Espeholt et al., 2018), and the use of multitude of identical agents operating copies of the same environment allowed RL systems to tackle increasingly complex and large-scale problems. While the maximum entropy formulation has been widely adopted in prior works, how to better take advantage of parallel exploration agents is still to be investigated.
AIRLAB, Politecnico di Milano, Milan, Italy 'Technion, Is- rael Intitute of Technology, Haifa, Israel. Correspondence to: Vin- cenzo De Paola <vincenzo, depaola@polliiainc polimi.it>> Riccardo Zam- boni griccardo.zambont @ polimi.it>.
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Enhancing Diversity in Parallel Agents
This is far from being a trivial problem. Zhong et al. (2024) recently showed that not explicitly caring for redundant be- haviors among the agents often results in inefficient use of computational resources, which is why parallelization is employed in the first place. Additionally, as highlighted in Rudin et al. (2022), solving complex problems necessi- tates intelligent strategies for constructing experience that accelerate algorithmic convergence. This challenge is fur- ther compounded in scenarios where access to real-world process data is limited, examples are scarce, or simulators are computationally expensive. Following these considera- tions, our study is centered around the following questions:
We provide numerical experiments to corroborate our findings, both in terms of state entropy maximization and batch RL on the collected data (Section 6).
2. Preliminaries
Before diving into the technical contributions of our work, we introduce the notation and the relevant background.
Notation. We denote [N] := 21. N for a con- stant N < co. We denote set with a calligraphic letter A and its size as [A], We denote A²
the T-fold Cartesian product of A. The simplex on A is denoted as A := {p E [0. E.EA p(a) = } and A denotes the set of conditional distributions p : A + Ag. Let X' random variables on the set of outcomes X' and correspond- ing probability measures px, Px', we denote the Shannon entropy of X as H(X) - ExEx Px Px(x)) log (1)) and the Kullback-Leibler (KL) divergence as DKL (Px (px:)
How should parallel agents optimize their policies for efficient exploration? What is the best way to leverage parallelism in state entropy maximization?
ExEx Px (a)) log(px (x))
In this paper, we generally address this question by extend- ing state entropy maximization to incorporate the role of parallel agents, enabling a deeper investigation into their ex- ploration efficiency. First, we introduce a specific problem formulation that can explicitly leverage parallelism. Rather than considering agents independently, we look at them a whole, and consider the distribution single one virtual agent would induce if it was following a uniform mixture of the agents' policies. Additionally, we theoretically char- acterize how the entropy of the distribution of state visits concentrates in the single-agent and parallel-agent cases and demonstrate the significant impact of parallelization on the rate of entropy stabilization and exploration diversity. Then, we shift our attention to how to solve the problem of parallel state exploration in practice, by proposing policy gradient strategy (Williams, 1992) that explicitly optimizes for the objective at hand. Finally, we use illustrative experiments to show that the proposed algorithm is indeed able to optimize for the state entropy and that the induced behavior enables agents to balance individual exploration with inter-agent di- versity. This synergy is particularly relevant when integrated with batch RL techniques (Levine et al., 2020).
Interaction Model. As a base model for interaction, we consider a finite-horizon Parallel Markov Decision Pro- cess (PMDP, Sucar, 2007) without rewards. A PMDP Mp = (M.)aejm) consists of m E N+ copies of the same MDP M, = (S, T. 1t), composed of a set S of states and set A of actions, which we let discrete and finite with size |S], |A| respectively. A set of m independent agents interact with each copy M,, according to the fol- lowing protocol. At the start of an episode, the initial state is drawn from an initial state distribution só ~ p. Then the i-th agent takes action aj and the state transi- tions to sf P(-Is) af) according to the transition kernel P : S x A + As- Those steps repeated until sty is reached, being T < co the horizon of an episode. The i-th agent takes actions according to a policy x' E Ag such that x' <'(a'ss²) denotes the conditional probability of taking action a' upon observing s². Overall, we refer with parallel policy the collection of policies म. = =TT))e(mi) Each interaction episode is collected into trujectory 7' == (s6, ais.... ......, s - 11 stp) E KC- S x AA, where K. is the set of all trajectories of length T.
-
Trajectory and State Distributions in MDPs. Here we consider a single MDP M,, for the purpose of expanding the connection between trajectories and distribution over states, temporarily dropping the index from all the quantities. policy π interacting with M4, induces a distribution over the generated trajectories. In particular, set of n E N+ trajectories
Original Contributions. the following contributions:
Throughout the paper, we make
We define the problem of State Entropy Maximization in Parallel MDPs (Section 3);
We provide high-probability concentration bounds de- scribing the rate at which the entropy of empirical distri- butions converges to the entropy of their stationary distri- butions. The proofs employ novel techniques that may be of independent interest (Section 4);
(Tz)se(x) are distributed according to probability measure Px E Ax defined as:
a Pr (T) II (()..)
T-1
II
π ( st.)) st.j. a..)- t=
We introduce a policy gradient algorithm to take advan- tage of parallel agents for maximizing the entropy of the visited states (Section 5);
IIn general, we will denote the set of valid per-agent policies with IT' and the set of joint policies with II.
2

---

Enhancing Diversity in Parallel Agents
From the realization of these trajectories, one can extract their empirical distribution Pr. Ax defined p (T) 1 + 1(T; T), where Tj is the trajectory at episode j in the history of interactions. Additionally, a trajectory obtained from an interaction episode induces an empirical distribution over states d, E As given by
while the states are distributed according to the following mixture distribution:
m (s).
dry (8)
m
1=1
Collecting data from all agents induces an empirical (paral- Iel) distribution over states which we denote as de.p E As. so that it is possible to define the mixture distribution as the expectation of the empirical state distribution under the par- allel policies, namely dr, (8) p.d..-pp, (s)) This object allows to define objectives specifically designed for PMDPs, that are then able to leverage their structural properties. First of all, we introduce the following:
T-1
dn(s) nT
Σ
Σ
= 5) As.
With slight overload of notation, we will denote as d,, Pr an empirical state distribution obtained from a sequence of trajectories of length I", and with T. ~ p a sub-trajectory of length t < T drawn from Pn- Finally, we denote the expectation of the empirical state distribution under the policy ı as (s) Rdd,, (s)), such that dz E As is called the state distribution induced by n.
Definition 3.2 (Parallel I Learning Objective in Infinite Tri- als). Let Mlm a PMDP, then the corresponding infinite trials objective can be defined as:
(T)) _ H(dxp):== - dr, (b) log
State Entropy Maximization in MDPs. In standard RL (Sutton & Barto, 2018), an agent interacts with environment to maximize the (cumulative) reward col- lected from the MDP. In the absence of a reward, previous works (Hazan et al., 2019; Mutti & Restelli, 2020; Mutti et al., 2021) investigated the effects of optimizing a different metrie, namely the state entropy H. defined as:
eES
Now, while this objective will be shortly shown to enjoy rather interesting concentration properties, we are building over the motivating interest of exploring with a handful of trials. These considerations lead to:
Definition 3.3 (Parallel Learning Objective in Finite Trials).
H. (T) & H(d,): Σ (s) log d (s). SES
Let Mm PMDP with an interaction over n E N episodes, then the corresponding finite trials objective can be defined as:
More recently, Mutti et al. (2023) noted that only finite number of episodes (called trials) can be drawn in many practical scenarios. When only trajectories can be ob- tained, they propose to focus on d, rather than its expec- tation d,, translating the infinite-trials objective of Eq. (2) with the finite-trials version
Jo A Ed.,p Prp H(dn..).
We are now ready to state the novel problem of interest:
Parallel State Entropy Maximization
max Jn(Tp) max (Ed., H(dms)) (1) Tlll
Js A Ed, H(dz).
mp Ell
The Jensen's inequality relates the two formulations as (x) 2 (T)...
We denote by TØ E arg max, Jp(T) a parallel policy that maximizes the parallel states entropy. In the next sections, we will show that Parallel Learning Objectives enjoy ex- tremely nice properties: first of all, they concentrate faster than their non-parallel counterparts, motivating the need for parallel exploration; moreover, they can be easily optimized in a decentralized fashion through policy gradient methods.
3. Problem Formulation
In this section, we extend the concept of state entropy novel objective able to incorporate parallel agents interact- ing with independent copies of the environment. In order to do so, we first need to introduce the following objects:
4. Fast Concentration of the Entropy in Parallel Settings
Definition 3.1 (Distributions in PMDPs). Let Mp a PMDP with an interaction over n E N episodes. then overall set of trajectories {rj (rjj) is distributed according to the following probability measure:
In this section, we present theoretical results that illus- trate how the (infinite-trials) entropy of the state (or tra- jectory) distribution concentrates. We will use these results to demonstrate the significant impact of parallelization on the rate of entropy stabilization and exploration diversity.
TT
Pa,(T) (T) =
(7)
P (T)).
m
j=1
3

---

Enhancing Diversity in Paraliel Agents
Key Remarks. While the following theorems are instan- tiated for state distributions, they are of broader theoretical interest and apply equally to distributions over trajectories. ? Additionally, we adopt the convention of referring to the entropy and variance of distributions rather than those of random variables, as a slight abuse of terminology, since these quantities are technically defined for random variables but naturally extend to their associated distributions.
vironment for a total of samples. This setting induces mixture distributions dr, and empirical mixture distribu- tions dn.p defined in the previous sections.
The entropy of the mixture distributions decomposes as follows:
H(dx,)) - 1 VIR
H(d + 1 Σ ==0
(
We start by analyzing the entropy of state distributions in MDPs, for which the following result holds:
where the first term is the average entropy of the individual agent distributions, and the second term captures diversity among these distributions via the KL divergence. By analyz- ing this decomposition, we can get insights into the potential advantages of parallel exploration versus single-agent explo- ration. To achieve high-entropy mixture distributions, have two key strategies:
Theorem 4.1. Let de be the (categorical) distribution induced by ι over the finite set S with [S] = S, and let dn be the empirical distribution obtained from n independent samples drawn from dæ. Then, for any e <> O, the the following bound holds:
6 Var(da)
PP ((o(dd))-H(dd))-- exp
25 exp 22²)2(d)))
Homogeneous Exploration: All agents follow the same entropy-maximizing policy, leading to mixture with an entropy equivalent to that of a single agent (the average of the entropies is equal to the single-agent en- tropy, and the second term in the above decomposition is equal to zero). The primary benefit of parallelism, in this case, is computational speedup rather than sample complexity reduction.
where (d,)) and (dzz) denote the entropy of the empirical and true distributions. respectively, and =
Var(d=)= =E (eee)))d((((())))))))))))))) (=) - ds)) is the variance of a random variable associated with the categorical distribution dz. Furthermore, to ensure this concen- tration with confidence 6, the number of samples n must satisfy the following lower bound:
Diverse Exploration:
Agents follow distinct policies with lower individual entropy, but their induced distribu- tions are maximally different. Here, the average en- tropy remains low, but the overall mixture entropy is high due to diversity (i.e., high values of the KI. diver- gences).
2dd))(d=)
28
N
In
Var(d>>) 5
This theorem establishes an upper bound on the probability that the entropy difference between the true and empiri- cal distributions exceeds c. Specifically, the probability of large deviations between these two entropies decreases exponentially with n, with the rate of convergence influ- enced by the entropy of the true distribution d' Notably, as (d,) lim Var(d.) 0, distributions with lower entropy require fewer samples for concentration, implying they are easier approximate empirically. The full proof can be found in Appendix A.
For example, if m agents induce distributions with disjoint supports, the entropy of the mixture increases by log(m) while maintaining low individual entropy, enabling faster concentration. However, if the agents' distributions overlap, the average KL divergence term decreases, necessitating higher individual entropies to maintain high mixture entropy, thereby increasing sample complexity.
This analysis shows that parallel exploration is beneficial not only for reducing data collection time but also for improving sample efficiency by enabling broader state-space coverage with fewer samples.
Primary Insight. This result suggests key advantage of parallel exploration: when multiple agents explore the envi- ronment simultaneously, each can focus on different regions of the state space. As a result, they induce distributions with lower entropy compared single policy covering the entire space.
5. Policy Gradient for Parallel Exploration with a Handful of Trials
We now consider the case of PMDPs with m parallel agents, each independently collecting n/m samples from the en-
As stated before, a core motivation of this work is address- ing the problem of exploration in practical scenarios, where a strong parallelization of the environment is used to over- come the difficulty to sample from complex simulators or even physical instantiations of the agents. In such setting, it
2The number of samples will represent the number of episodes for trajectory distrihutions the number of steps for state distributions.

---

Enhancing Diversity in Parallel Agents
is crucial to achieve good performances over a finite number of realizations, and for this reason our attention now shifts towards finite trials objectives. Specifically, we will focus on the single trial case, i..., n = 1, and show that rather than instantiating m copies of the same algorithm, the paral- lel learning objective allows for an alternative formulation, where agents explicitly leverage parallelization. The core idea lies in the implementation of policy gradient of the parallel formulation of Eq. 3.3 set of parametric policies me; S + A where 0g E O C R& is parameter vector in a d-dimensional space, uniquely associated with the agent i. The parallel policy is then defined as T = (IT,, (efm)-
Algorithm 1: Policy Gradient for Parallel States
Entropy maximization (PGPSE)
1: Input: Episodes N, Trajectories K, Batch Size
B, Learning Rate a, Parameters = (0') [0'))e()
2: for e E f do
3: for itr E [I....,.1 B} do
4: for l: E ,l,,...,K. K} do
5:
T m0 {Sample parallel trajectories]
6: log TO. + - T-
t=1 Va log TO 84)
7:
(s()) f km 1iit== 1 8)
m.J.T
8:
VoJ(O) + log To, H(dp)
9:
end for
In the following, we derive the gradient of the parallel ob- jective with respect to the policy parameters. For the sake of simplifying the notation, we will refer to dn.p as dp for simplicity. Starting from the cost function:
10: end for
11: VoJ(O) + 1 VoJ(O)
B
12:
0 + 0+0+aV (V
13: end for
(TT) = / Pa, Pa, (d)))((d)),
14: Output: Policies गe (Tz die(m)
we take the derivative with respect to the parameters 0,: (J(p))
Thus, the partial gradient update consists of an internal sum- mation over the log of the i-th policy executed by agent i, as it interacts over the horizon T. experiencing various action- state combinations. This internal summation is further ag- gregated across the external summation over K trajectories. This estimator approximates the true gradient by averag- ing the score function of sampled trajectories, weighted by the entropy of such induced state distribution. By limiting parallel agents to experience only one trajectory per each, we average over mini-batch B }(T:));=1 to reduce the variance of the reinforce estimator, with B [B] being the batch-size. The pseudo-code of the resulting Algorithm, called Policy Gradient for Parallel States Entropy maximiza- tion (PGPSE), is reported in Algorithm 1.
f Pa, (m, (g)d))
00.
00;
Since 0, only appears in Pa, (.), we can then write:
(x(p) = / @ppn (dp) H(dp),
00;
00;
Now, we can employ standard log-trick arguments after noticing that the parameter 02 only appears in agent i's policy, that is conditioned over the respective trajectory Ti, allowing one to write:
(dp) 00;
Olog To, (a]]s() 00,
PTp (dp)
6. Empirical Corroboration
1=0
Then, after substituting back into the original integral we get:
We report numerical experiments in simple yet illustrative domains to demonstrate the advantage of exploration with distinct parallel agents over single agents. The section is organized into three parts:
(T(p)) = f 00,
ff PTy (dp) log No, H(dp)-
defining the so-called score function as log Te. Et= Vo log No, (oels)), with To, (asls:) being the prob- ability for agent i of taking action ag in state 8; in trajectory TG. On the other hand, one should note that the entropy is computed over the empirical distribution dp induced by all the agents. In other words, each agent can independently perform gradient updates via joint estimation of the en- tropy feedback. In the following, we estimate the gradient of the parallel objective [(TT) with respect to its policy pa- rameters O, using an unbiased Monte-Carlo estimator over K E N sampled parallel trajectories:
This part analyzes the results of the learning process based Algorithm 1, eval- uating the performance of the learned policy in terms of normalized entropy and support size.
Policy Gradient Optimization:
Dataset Entropy Evaluation: This part takes a deeper look at the entropy of a dataset collected from the policies trained as in the previous section.
This part provides a comparative analysis of how the dataset collected with parallel maximum entropy agents benefits the performance of offline RL.
Offline RL:
K
[O,T( ~
Vo log no. (dinassix)) ml(d)).
For all the experiments, we consider variations of discrete grid world domains, which we depicted in Appendix (see
K
Rm
5

---

Enhancing Diversity in Parallel Agents
Agents
Agent =
Agents
Agent =
0.8
Nomallzes States Enerpyy
Normattzed Entropy
Normalized States Entrapy
Normal Steve seees Emora
0.8
3.9
0.6
0.0
0.6
9.9
0.5
0.5
0.5
0.5
0.4
0.4
0.4
10k
5k
18k
18k
56
10
Updates
Updates
Updates
Updates
(a) State Entropy (Room-der)
(b) State Entropy (Room-stoc)
(c) State Entropy (Maze-det)
(d) State Entropy (Maze-stoc)
35
20.0
17.5
20
15.0
Support
12.5
15
10.0
75
5.0
Updates
Updates
Updates
Updates
(c) Support size (Room-det)
(f) Support size (Room-stoc)
(g) Support size (Maze-der)
(h) Support size (Maze-stoc)
Figure 1. The top row (a-d) shows the progression of normalized state entropy across different environments, while the bottom row (c-h) depicts the corresponding size of the support of the entropy. Each plot shows the performance of parallel agents (2 or 6) against single agents taking and trajectories, respectively. We report average results and standard deviation over 5 independent runs.
Figures 5. 6). One family (referred to as Room) composed of two rooms connected by a narrow corridor, with total of 43 states and 4 actions (one move in each direction). The other (referred to as Maze) is a maze of various connected paths, with same number of total states and actions as before. For each family, we consider a deterministic version (der) and a stochastic version (stoc) which the agent's chosen actions are flipped to random actions with some probabil- ity, Appendix reports further experimental details, with additional visualizations and results.
gorithms with varying number of agents, the performance reported function of the policy updates, which translate
to B m K x T total interactions with the environment. Across the board, the performance of parallel agents (solid lines) consistently outperforms the single agent counterparts (dashed lines). Indeed, they achieve higher entropy values, thanks to their ability to explore more states as is evident from the larger size of the support. This behavior can be attributed to the intrinsic diversity introduced by parallel agents: To optimize the team state distribution, each agent learns individual behavior that is synergic with the others.
Policy Gradient Optimization. First of all, we test the ability of PGPSE (Algorithm 1) in addressing maximum state entropy exploration with parallel agents. We run mul- tiple instances of the algorithm with an increasing number of agents m (2, 4, 6).² As baseline, we consider the performance of the same algorithm training single agent for the finite-trial objective (Eq. 2), with a number of trials K' matching the number of trajectories taken by the parallel agents. We compare the results in terms of (normalized) state entropy and the size of the entropy support (i.e., the number of unique visited states) in all the domains.
Dataset Entropy Evaluation. Then, tested the ca- pabilities of the trained policies in collecting diverse periences, by analyzing the properties of single dataset. Figure 2 illustrates the normalized empirical state entropy of each dataset collected by the m agents, compared against the entropy of the dataset collected by a single agent over = m trajectories (trained to maximize the entropy on the corresponding number of trajectories), and random policy,
To construet these datasets, we sample trajectory per agent from the parallel policies, evaluating them across five seeds. This procedure reveals that datasets generated through parallel exploration exhibit higher entropy than those collected by a single agent or a random policy. is noteworthy that experience collected in parallel also ex-
Figure/ 1 reports the resulting learning curves, obtained over five independent runs. For fair comparison of al-
'In the main text omit the result with 4 agents, which reported in Figure 7 the Appendix.
6

---

Enhancing Diversity in Parallel Agents
Agents Agent
Agents
Agent 6K Random
0.7
0,6
0.
0.6
Succeds Batt
Normalge Entrook
Wormataze Entragn
0.5
0.4
0.3
03
022
0.
(a) Success Rate, Parallel Dataset (Room-det)
(b) Success Rate, Parallel Dataset (Maze-det)
Number of Agents
Nurvoer Agents
(a) Dataset Entropy (Room-det) (h) Dataset Entropy (Room-stoc)
1.0
1.0
0.0
Success Bate
Entrgg
0
0.6
0.
0.5
Normafzed
0.4
0.
03
Looal Posi Exon
Doal Postion
(c) Success Rate, Single Agent Dataset (Roum-det)
(d) Success Rate, Single Agent Dataset (Muze-det)
0.0
00
Number Agents
Agents
Dataset Entropy (Maze-det) (d) Dataset Entropy (Maze-stoc)
Figure Entropy evaluation the dataset generated by sampling from parallel policies, compared against both random and single- baselines across different environments. With notation K' K denoted the set in which the single agent had access to a multiple m of trajectories available to the parallel agents. We report average and standard deviation over 5 independent runs.
0.5
0.6
0.4
0.0
0.0
(c) Success Rate, Random Dataset (Room-der)
Success Rate, Random Dataset (Maze-der)
hibits minimal variance across runs, indicating that agents tend to generate trajectories in a quasi-deterministic manner, preserving consistency in the collected data.
for various goal positions: Each subplot depicts the agent's 's ability to reach a goal state posi- tioned different location (one for each state). The results refer to datasets obtained over 5 independent runs.
Figure 3. Offline Q-learning
Offline RL. Finally, we address the following ques-
tion: Can datasets collected with parallel maximum en- tropy agents benefit offline RL algorithms? One practical application of the policies learn with PGPSE, in line with the motivation of this work, is utilize the experience gained during the exploration phase construct informative datasets for offline RL (Yarats et al., 2022).
offline RL success rate on each dataset relabeled, one for every possible goal state, ordering the results according to their respective success rate. Notably, a dataset collected with parallel agents allows achieve the best offline RL performance across large number of states, far greater than datasets collected with single maximum entropy agent or random policy. In Appendix C, we provide further heatmaps visualizations showing the goal positions that offline RL algorithm is able to reach (Figure 9), and how each dataset looking terms of their empirical state distribution (Figure 8).
Starting from the datasets collected as for Figure 2, we re- label the transitions with sparse reward functions, assigning rewards of +1 for a specific goal state and 0 otherwise. We then train an agent with offline Q-learning (Watkins Dayan, 1992). At each training step, the agent samples mini-batch of transitions (s, a, s') from the dataset and updates its Q-value as Q(s, a) Q(s,a) [r max,' Q(s', a') Q(s, a)] where a is the learning rate, is the discount factor, and max, Q(s', a') represents the best estimated discounted future reward.
Takeaways. Parallel State Entropy Maximization leads to better exploration, diverse data collection and improved performances in offline learning in PMDPs.
In Figure 3, we report the barplots of the corresponding

---

Enhancing Diversity in Parallel Agents
7. Related Work
Diverse Skills Discovery. The problem of learning set of diverse skills and/or policies is somehow linked to the problem of diversifying exploration via parallelization, and it has been addressed by a plethora of recent works (Hansen et al., 2019; Sharma et al., 2020; Campos et al., 2020; Liu & Abbeel, 202 la; He et al., 2022). The results provided by Gregor et al. (2017); Eysenbach et al. (2019) are particu- larly relevant for this work, in which the mutual information between visited states and skills is maximized, toghether with the ones in Zahavy et al. (2022), that explicitly maxi- mizes the diversity between policies.
In the following, we summarize the most relevant works this paper sets its root in, spanning from entropy maximization, multi-agent exploration to diverse skill discovery.
State Entropy Maximization. State entropy maximiza- tion in MDPs has been introduced in Hazan et al. (2019), from which followed a variety of subsequent works focusing on the problem from various perspectives (Lee al., 2019; Mutti & Restelli, 2020; Mutti et al., 2021; 2022a;b; Mutti, 2023; Zhang et al., 2021a; Guo et al., 2021; Liu & Abbeel, 2021b;a; Seo et al., 2021; Yarats et al., 2021; Nedergaard & Cook, 2022; Yang & Spaan, 2023; Tiapkin et al., 2023; Jain et al., 2023; Kim et al., 2023; Zisselman et al., 2023; Zamboni et al., 2024a:b; 2025).
8. Conclusions
This paper targeted the critical challenge of efficient explo- ration in reinforcement learning, particularly in scenarios with slow environment simulators limited interaction bud- gets. We introduced a novel parallel learning framework that leverages the power of multiple agents to maximize state entropy while explicitly promoting diversity in their exploration strategies. Unlike traditional approaches that rely on multiple instances of identical agents, our method, PGPSE based on policy gradient techniques. employs a cen- tralized learning mechanism that balances individual agent entropy with inter-agent diversity, effectively minimizing redundancy and maximizing the information gained from parallel exploration.
Policy Gradient. In the RL literature, first-order meth- ods have been extensively employed to address non-concave policy optimization (Sutton et al., 1999; Peters & Schaal, 2008). In this work, we proposed a vanilla policy gradi- ent estimator (Williams, 1992) as a first step, yet several further refinements could be made, such natural gradi- ent (Kakade, 2001), trust-region schemes (Schulman et al., 2015), and importance sampling (Metelli et al., 2018).
Exploration with Multiple Agents. The problem of exploration in the presence of multiple agents is a vast and diverse topic. Among others, concurrent exploration (Guo & Brunskill, 2015; Parisotto et al., 2019; Jung et al., 2020; Chen et al., 2022; Qin et al., 2022) has focused on scenarios where multiple agents operate within the same environment and learn simultaneously. Of particular interest are the works that investigate the role of information sharing be- tween the agents (Alfredo& & Arjun, 2017; Holen al., 2023)
Our theoretical analysis demonstrated the significant impact of parallelization on the rate of entropy stabilization and exploration diversity. Specifically, we showed that parallel agents, by focusing on different parts of the state space, can achieve faster convergence to high-entropy distributions compared to a single agent. These theoretical findings were strongly corroborated by our empirical results on various gridworld environments. PGPSE consistently outperformed single-agent baselines in terms of both state entropy and sup- port size, demonstrating the effectiveness of our diversity- promoting approach.
or the ones that characterize the theoretical conditions for efficient coordinated exploration to happen and scale (Di- makopoulou& & Van Roy, 2018; Dimakopoulou et al., 2018). Finally, exploration in Multi-Agent RL (MARL, Albrecht et al., 2024) has gained attention but was almost limited to reward-shaping techniques based on many heuristics Wang al. (2019); Zhang et al. (2021b); Xu et al. (2024). In par- ticular, Zhang et al. (2023) proposes a term maximizing the deviation from (jointly) explored regions. Yet, we highlight a key distinction: In conventional MARL, multiple agents operate concurrently within a shared environment, requiring coordination due to the interdependence of their trajectories; In contrast, our setting involves multiple agents interact- ing with independent instances of the environment. While coordination remains beneficial for enabling specialization and aligning agents with distinct objectives, their trajecto- ries are decoupled. This structural difference fundamentally separates our framework from typical MARL formulations like Li et al. (2021), Zhao et al. (2021) and Lupu et al.
Furthermore, we showed that the datasets collected by par- allel agents exhibit higher entropy and lead to improved performance in offline settings, highlighting the practical value of our method for data-efficient learning. While our results are promising, we acknowledge certain limitations. Our current framework evaluated primarily on discrete gridworld environments. Future work will involve extend- ing PGPSE to continuous and more complex environments, such as those found in robotics and control problems. Future work will extend, the concept of state entropy maximization to the trajectory based one, with centrally, the benefit of parallelizing the exploration strategy to achieve wider and diverse skills acquisition over complicated real world prob- lems. These extensions will be crucial for demonstrating the scalability of our approach to a broader use case.
(2021).
8

---

Enhancing Diversity in Parallel Agents
Impact Statement
In International Conference on Learning Representations, 2019.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Genesis. universal and generative physies engine for robotics and beyond, December 2024. URL https: //github. wwwuu.ccm//aooo cac.aut...o/eeeeeii--aaaaa...... Genesis.
Acknowledgment
Gregor, K., Rezende, D. J., and Wierstra, D. Variational intrinsic control. In International Conference on Learning Representations, 2017.
This paper is supported by FAIR (Future Artificial Intelli- gence Research) project, funded by the F program within the PNRR-PE-AI scheme (M4C2, Invest- ment 1.3, Line Artificial Intelligence). This work is supported by Siemens Digital Industry Italy.
Guo, Z. and Brunskill, E. Concurrent PAC RL. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
References
Guo. Z. D., Azar, M. G., Saade, A., Thakoor, S., Piot, B., Pires, B. A., Valko, M., Mesnard, T.. Lattimore, T., and Munos, R. Geometric entropic exploration. arXiv preprint arXiv:2101.0205. 2021.
Albrecht, S. V., Christianos, F., and Schäfer, L. Multi- Agent Reinforcement Learning: Foundations and modern approaches. MIT Press, 2024.
Alfredo. C. and Arjun, C. Efficient parallel methods for deep Reinforcement Learning. In The Multi-disciplinary Con- ference on Reinforcement Learning and Decision Making (RLDM), pp. 1-6, 2017.
Hansen, S., Dabney, W., Barreto, A., Warde-Farley, D., Van de Wiele, T., and Mnih, V. Fast task inference with variational intrinsic successor features. In International Conference on Learning Representations, 2019.
Bertsekas, D. Reinforcement Learning and optimal control, volume 1. Athena Scientific, 2019.
Hazan, E., Kakade, S., Singh, K., and Van Soest, A. Prov- ably efficient Maximum Entropy Exploration. Interna- tional Conference Machine Learning, pp. 2681-2691. PMLR, 2019.
Campos, V., Trott, A., Xiong, C., Socher, R., Giró-i Nicto, X., and Torres, J. Explore, discover and learn: Unsuper- vised discovery of state-covering skills. In International Conference on Machine Learning, 2020.
He, S., Jiang, Y., Zhang, H., Shao, J., and Ji, X. Wasser- stein unsupervised Reinforcement Learning. In AAAI Conference on Artificial Intelligence, 2022.
Chen, Y., Dong, P., Bai, Q., Dimakopoolluu, M., Xu, W., and Zhou, Z. Society of agents: Regret bounds of concurrent thompson sampling. Advances in Neural Information Processing Systems, 35:7587-7598, 2022.
Holen, M., Andersen, P.-A., Knausgård, K. M., and Good- win, M. Loss and reward weighing for increased learning in distributed Reinforcement Learning. arXiv preprint arXiv:2304.127785 2023.
Dimakopoulou, M. and Van Roy, Coordinated explo- ration in concurrent Reinforcement Learning. In Interna- fional Conference on Machine Learning, pp. 1271-1279.
Jain, A. K., Lehnert, L., Rish, I., and Berseth, G. Maximum state entropy exploration using predecessor and succes- sor representations. In Advances in Neural Information Processing Systems, 2023.
PMLR, 2018.
Dimakopoulou, M., Osband, I,, and Van Roy, B. Scalable ordinated exploration in concurrent Reinforcement Leam- ing, Advances in Neural Information Processing Systems, 31, 2018.
Jung, W., Park, G., and Sung, Y. Population- -urioondguudddddd parallel policy search for Reinforcement Learning. arXiv preprint arXhv:2001.02907 2020.
Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dun- ning, I., Legg, S., and Kavukcuoglu, K. Impala: Scal- able distributed deep-rl with importance weighted actor- learner architectures. CoRR, abs/1802.0156/ 2018. URL http: arxii..iivv///vv. org/ abs/ 1802. 01561.
Kakade, S. M. A natural policy gradient. In Advances in Neural Information Processing Systems, 2001.
Kim, D., Shin, J., Abbeel, P., and Sco, Y. Accelerating Reinforcement Learning with value-conditions state en- tropy exploration. In Advances in Neural Information Processing Systems, 2023.
Eysenbach, B., Gupta, A., Ibarz, J., and Levine, S. Diversity is all you need: Learning skills without reward function.

---

Enhancing Diversity in Parallel Agents
Lee, L., Bysenbach, B., Parisotto, E., Xing, E., Levine, S., and Salakhutdinov, R. Efficient exploration via state marginal matching, arXiv preprint 19x.v21906.05274, 2019.
Mutti, M., De Santi, R., and Restelli, M. The importance of non-Markovianity in maximum state entropy explo- ration. In International Conference Machine Learning, 2022a.
Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline Rein- forcement Learning: Tutorial, review, and perspectives open problems. CoRR, (tbss/20050014333 2020. URL https: htaps:///rxxxvi org/ hbtg//bs//aa 000..00050..0.......
Mutti, M., Mancassola, M., and Restelli, M. Unsupervised Reinforcement Learning in multiple environments. In AAAI Conference on Artificial Intelligence, 2022b.
Mutti, M., Santi, R. D., Bartolomeis, P. D., and Restelli, M. Challenging common assumptions in convex Reinforce- ment Learning, 2023. URL https: http://axxvvvoooo
Li, C., Wu, C., Wang. T., Yang, J., Zhao, Q., and Zhang, C. Celebrating diversity in shared multi-agent Reinforce- ment Learning. CoRR, abs/2106.02195, 2021. URL https: /atp://aaavv////aa/eaaeeaaeaaava www./bggg////oooooo//.../...eeee
abs/2202. 01511.
abs 2106. 02195.
Nedergaard, A. and Cook, M. k-Means Maximum Entropy Exploration. arXiv preprint 2rXiv:2205.15022 2022.
Liu, H. and Abbeel, P. APS: Active pretraining with suc- cessor features. In International Conference on Machine Learning, 2021a.
NVIDIA 2021 2021. http:://eeeelopr...iiiiaacccsaas
Isaac
Sim.
NVIDIA.
Liu, H. and Abbeel, P. Behavior from the void: Unsuper- vised active pre-training. Advances in Neural Informa- tion Processing Systems, 2021b.
Parisotto, E.,, Ghosh, S., Yalamanchi, S. B., Chinnaobireddy,
V., Wu, Y., and Salakhutdinov, R. Concurrent meta Rein- forcement Learnnng arXiv preprint 1931v:1903.02710, 2019.
Lupu, A., Cui, B., Hu, H., and Foerster, J. Trajectory diver- sity for zero-shot coordination. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Confer- ence on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 7204-7215 PMLR, 18-24 Jul 2021. URL https: http://pooceeennss///ee mlr. press satass/vl33 /t1///11///////// Lupulla.... html..
Park, S., Ghosh, D., Eysenbach, B., and Levine, HIQL: Offline goal-conditioned RL with latent states as actions. Advances in Neural Information Processing Systems, 36: 34866-34891, 2023.
Peters, J. and Schaal, S. Reinforcement Learning of motor skills with policy gradients. Neural Networks, 2008
Metelli, A. M., Papini, M., Faccio, F, and Restelli, M. Pol- icy optimization via importance sampling. Advances in Neural Information Processing Systems, 2018.
Qin, C., Wen, Z., Lu, X., and Van Roy, B. An analysis of ensemble sampling. Advances in Neural Information Processing Systems, 35:21602-216111 2022.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I,, Wierstra, D., and Riedmiller, M. A. Play- ing ATARI with deep Reinforcement Learning. CoRR, abs/1312.5602, 2013. URL http://arxiv.org abs/1312.5600
Rudin, N., Hoeller, D., Reist, P., and Hutter, M. Learning walk minutes using massively parallel deep rein- forcement learning. In Conference on Robot Learning, pp. 91-100. PMLR, 2022.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, 2015.
Mutti, M. Unsupervised Reinforcement Learning via state entropy maximization. PhD Thesis, Università di Bologna, 2023.
Sco, Y., Chen, L., Shin, J., Lee, H., Abbeel, P., and Lee, K. State entropy maximization with random encoders for efficient exploration. In International Conference on Machine Learning, 2021.
Mutti, M. and Restelli, M. An intrinsically- mottvvated ap- proach for learning highly exploring and fast mixing poli- cics. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5232-5239, 2020.
Sharma, A., Gu, S., Levine, S., Kumar, V., and Hausman, K. Dynamics-aware unsupervised discovery of skills. In International Conference on Learning Representations, 2020.
Mutti, M., Pratissoli, L.,, and Restelli, M. Task-agnostic exploration via policy gradient of a non-paramctric state entropy estimate. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9028-9036. 9036,, 2021.
Sucar, L. E. Parallel markov decision processes. Advances Probabilistic Graphical Models, pp. 295-309, 2007.
10

---

Enhancing Diversity in Paraliel Agents
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An introduction. MIT press, 2018.
Yarats, D., Fergus, R., Lazaric, A., and Pinto, L. Rein- forcement Learning with prototypical representations. In International Conference on Machine Learning, 2021.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for Reinforcement Learning with function approximation. In Advances in Neural Informa- tion Processing Systems, 1999.
Yarats, D., Brandfonbrener, D., Liu, H., Laskin, M., Abbeel, P., Lazaric, A., and Pinto, L. Don't t change the algorithm. change the data: Exploratory data for offline Reinforce- ment Learning. arXiv preprint arXiv: 22.2221..3444 13425, 2022.
Tarbouriech, J. and Lazaric, A. Active exploration in Markov decision processes. In International Conference on Artificial Intelligence and Statistics, 2019.
Zahavy, T., Schroecker, Y., Behbahani, F., Baumli, K., Flen- nerhag, S., Hou, S., and Singh, S. Discovering policies with DOMiNO: Diversity optimization maintaining near optimality. arXiv preprint
Tarbouriech, J., Shekhar, S., Pirotta, M., Ghavamzadeh,
2022.
M., and Lazaric, A. Active model estimation in Markov decision processes. In Conference on Uncertainty in Artificial Intelligence, 2020.
Zamboni, R., Cirino, D., Restelli, M., and Mutti, M. How explore with belief: state entropy maximization in POMDPs. In Proceedings of the 41st International Conference Machine Learning, ICML'24. JMLR.org, 2024a Zamboni, R., Cirino, D., Restelli. M., and Mutti, M. The limits of pure exploration in POMDPs: When the observation entropy is enough. RLJ, 2:676- 692, 2024b. URL https://// cs. umass amass.edd/ 2024 / Saapess/PapesSe
Tiapkin, D., Belomestny, D., Calandriello, D., Moulines, E., Munos, R., Naumov, A., Perrault, P., Tang, Y., Valko, M., and Menard, P. Fast rates for maximum entropy exploration. In International Conference on Machine Learning, pp. 34161-34222 PMLR, 2023.
Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics engine for model-based control. In 2012 IEEE/RS/ Inter- nutional Conference on Intelligent Robots and Systems, pp. 5026-5033. IEEE, 2012. doi: 10. 10.1109/RRS.20122 6386109.
Zamboni, R., Mutti, M., and Restelli, M. Towards principled multi-agent task agnostic exploration. arXiv preprint arXiv:2502.08366 2025.
Towers, M., Kwiatkowski, A., Terry, J., Balis, J. U., Cola, G. D., Deleu, T., Goulão, M., Kallinteris, A., Krimmel, M., KG, A., Perez-Vicente, R., Pierré, A., Schulhoff, S., Tai, J. J., Tan, H., and Younis, O. G. Gymnasium: A standard interface for Reinforcement Learning envi- ronments, 2024. URL https: //ta:://aariiie /ttpxaaxvvvvoo///////a org/ abs/ 2407.17032
Zhang, C., Cai, Y., Huang, L., and Li, J. Exploration by maximizing Rényi entropy for reward-free RL framework. In AAAI Conference Artificial Intelligence, 2021a.
Zhang, S., Cao, J.. Yuan, L., Yu, Y., and Zhan, D.-C. Self-motivated multi-agent exploration. arXiv preprint #iXiv:3311.0208: 2023.
Zhang, T., Rashidinejad, P., Jiao, J., Tian, Y., Gonzalez, J. E., and Russell, S. MADE: Exploration via maximizing deviation from explored regions. Advances in Neural Information Processing Systems, 34:9663-9680, 2021b.
Wang, T, Wang, J., Wu, Y., and Zhang, C. Influence- based multi-agent exploration. arXiv preprint arXiv:1910.05512, 2019.
Watkins, C. J. and Dayan, P. Q-leariing Machine learning, 8:279-292, 1992.
Zhao, R., Song, J., Hu, H., Gao, Y., Wu, Y., Sun, Z. and Wei, Y. Maximum entropy population based training for zero-shot human-ai coordination. CoRR, abs/2112.11701, 2021. https::///a/ abs /ts/2212.11177
Williams, R. J. Simple statistical gradient-following algo- rithms for connectionist Reinforcement Learning. Ma- chine Learning, 8:229-256, 1992.
Zhong, D., Yang, Y., and Zhao, Q. No prior mask: Elimi- nate redundant action for deep reinforcement learning, In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 38, pp. 17078-17086, 2024.
Xu, P., Zhang, J., and Huang, K. Population- di- verse exploration for sparse-reward multi-agent tasks. In Proceedings of the Thirty-Third International Joint Con- ference on Artificial Intelligence, pp. 183-291, 2024.
Zisselman, F.,, Lavie, I., Soudry, D., and Tamar, A. Explore to generalize in zero-shot RL. In Advances in Neural Information Processing Systems, 2023.
Yang, Q. and Spaan, M. T. CEM: Constrained entropy maximization for agsk-agn safe exploration. In AAAI Conference on Artificial Intelligence, 2023.

---

Enhancing Diversity in Parallel Agents
A. Main Proofs and Additional Results
the following, we present the proofs of the theoretical results that highlight how the entropy of the distribution of state or trajectory visits concentrates in the single-agent and parallel-agent cases.
Concentration Properties.
Theorem A.1. Let d be the (categorical) distribution induced by a over the finite set S with |S] S, and let dn be the empirical distribution obtained from a independent samples drawn from dg. Then, for any c > O, the following bound holds:
var((=))
-n com 2S²
P (P((d))-H((d))>- 25 exp
where (dn)) and (d=)) denote the entropy of the empirical and true distributions, respectively, and Var(dz) = Eee[s (s) (s)) the variance of a random variable associated with the categorical distribution d Fur- thermore, to ensure this concentration with confidence 1 ô, the number of samples a must satisfy the following lower bound:
2 Inn n N Var(d)
25
Proof. The proof consists three main steps. In order to keep the derivation agnostic from the state or trajectory- setting, we will now introduce a different yet equivalent notation: let p be a categorical distribution over a finite set with | = K, and let ý be the empirical distribution obtained from n.
Decomposing the Problem via Union Bound. First, we expand the entropy terms to highlight the contribution of the single components:
K
K
1 pi
1
P(H(p) H(D) > e) S P
Σ
Pt log
Ô: log
P
Σ h(p)) - 1((e)) >E)
Pi
where p; P(X = æ;)) and hxx) = x log (#).
Applying the union bound to the previous result, we get:
K
Σ P (h(p:))((fa) :
P(H(p) - -H(P) e) <
(2)
Bounding the Entropy the Components using Linear Approximation. Now, we focus on finding an upper bound to (p:)) h(.).. We introduce a lower bound to h(f)) obtained by a combination of functions that are linear in the deviation [ps pel:
h(p,) )p: Psl min(pi, -pi) h(pp))
h(p:)lp: - Pzl
h(p)) 2 h(p.)
Pc(1 pt)
As consequence
h(pp) Ip: pel p;(1 pi)
Pr(1 (((1-
P -(())) > 6) S
>e) < [p: Pol
(3)
h(ps)
Thanks to this last inequality, we can now focus on the concentration inequality of the Bernoulli distributions associated with the parameters Pi.
Applying a Concentration Inequality for Bernoulli Distributions. Finally, we use concentration inequality on the estimation of Bernoulliddistribueed parameter to express this probability bound in terms of the variance of pa (Var(p;) = pc(1 - (.)).
Leveraging Chernoff bound for Bernoulli distributions, we get:
P(pp - pul <) e mDRi(vetellee + + (=DDks(p-ellp)) S 2e 3,,11-1, 2e 2Varty
(4)
12

---

Enhancing Diversity in Parallel Agents
2
(p;) Var(p:)
Var(p.) H(p,)
Values
0
0.2
0.4
0.6
0.8
Pi
Figure 4. The plot shows that (p.) and Var(p.) are concave symmetric function with their maximum located at = 0.5, while Varee)] a convex symmetric function with minimum located at pı 0.5.
We now complete the proof by combining the results Eqs (2), (3), and (4):
K P(H((p) - H(D) > 2) P h(p.) h(p,)
K P
Pr(1- pi) Kh(p))
K
m
P: Pul
<
(5)
In order to remove the summation over the K components of the distribution, we need to find lower bound to the term p.(1 (1-pp)) that is independent of the specific component parameter p,. Here, we show the chain of passages that achieve this (((()))
goal:
Pt(1 - p.) 2 min
P.(1 all-pi pp). max; Pt(1 - p.).
Eip(L- 2
Var(p)
min
Hp)):) max; Hp)p:)
K max; HP
KHZ
The motivations for each step
1. H(p.)) 2 h(p.).
2. The value of p: that minimizes p=(1-ps) the one with the highest entropy (see Figure4). The ration between the "P(p.)
variance p(1 - p) and the squared entropy H²(pp is symmetric about p and it has negative derivative for p and positive derivative for 1. Since the higher the entropy H(p,), the higher is also the variance p; Pi), we can restate the minimization problem as the ratio of two maximization problems.
3. The the numerator the maximum variance, which can be lower bounded by the average variance.
4. The maximum entropy among the Bernoulli distributions associated with all the components is upper bounded by the entropy of the categorical distribution p.
Leveraging this result in Eq. (5) concludes the proof.
13

---

Enhancing Diversity in Parallel Agents
Frank-Wolf for Parallel Exploration with Infinite Trials Frank-Wolfe Algorithms have gained much attention for their strong theoretical guarantees in MDPs (Hansen et al., 2019). In this section, show that by performing Frank-Wolfe- like updates in parallel fashion over infinite-trials objectives reported in Algorithm 2, it is possible to obtain faster convergence rates with respect to the non- non-parallel formulation, through a convenient scaling factor of I/N with N being the number of parallel instantiations. In order to allow for a simpler derivation, we will assume access to two kinds of oracles. First, some approximate planning oracles (one per each agent) that given a reward function (on states) r S - IR and a sub- optimality gap é1, returns a policy я = APPROXPLAN(T; e1) with the guarantee that H(x) 2 max (t) <1. addition, some state distribution estimate oracles (one per each agent) that estimate the state distribution d = DENSITYEST co) of any given (mon-stationary policy π, guaranteeing that ||d - do I 61. In addition, we will assume that the entropy functional H is B-smooth, BB-bounded, and that satisfies the following inequality for all X, Y:
VH(X)= - VH(Y) - 8| -
- V()( S BI; [V S B
Under these assumptions, it follows that Algorithm 2 enjoys the following:
Theorem A.2 (Convergence Rate). For any > 0, set E 0.1s, 6o = 0.13- and " 0.1|81-18-NN5 where Algorithm 2 is fur iterations over agents in parallel where:
T2 103|SIN = log 10Be
we have that:
H (TT.e.)) max H (dx) E.
Proof of Theorem A.2. Let be maximum-entroppy policy, ie. x* E argmax Hdzz).
H (ddmi.s4)) = H(1 - 17) TT + rd
2 H (dmmn)) ) + - - draaer V VH (ddd...))) - 17² Bl|ddet
d d=m.,
172
2 H (drme,))
+ N
(dains - damanes (d(mm.))
Σ
||
d
d
N2
The second inequality follows from the smoothness of H, the third applies the definition of distributions induced by mixture policies. Now, to incorporate the error due to the two oracles, observe that for each agent holds
(dat W (d (dri (H -311dmm d dl
(dx ((( ) A80 81
M (dx, (d - 2,300 E1
The first and last inequalities invoke the assumptions on the entropy functional. Note that the second inequality above follows from the defining character of the planning oracle. Using the above fact and continuing
1723 N
H H(d ( 2 H (d (d.....))) )
17 N
E(dris) draaer VH
Σ
|d
d
122
(dzm..)) + n/dd dramnr (d .)) -2,3750 1781
S
N
17² 3|S
211 - 1)) H) (dd + (Hdg)) -29850 - -761
N
The last step here utilizes the concavity of H. It follows that
14

---

Enhancing Diversity in Parallel Agents
H(d H ( - H (ddam..)) + 2ngEu + ne1 + 7 3/
N
Telescoping the inequality, this simplifies to
(d H(d (1 (1-1)) (H(())) Hd 2,50 + 51 + +1
B|S]
Be BBe-In In + 28E. + +
N
Hdzz.) ((mmuu.))
n/18
$ (11-1)" (H -H(d + 2850 +1
I Be Tn + +,30 +1 n188s
Setting 61 0.1e, en =
7= 17 log 10Be-1 leads to the final result.
Algorithm 2 Parallel Frank-Wolfe.
1: Input: Step size y), number of iterations T, number of agents N, planning oracle tolerance é > 0, distribution
estimation oracle tolerance εo > 0.
2: Set {Cj hee JEN where Tá is an arbitrary policy, aj
3: for [. = 0, .,, T do
4: Each agent call the state distribution oracle on Mmix, t La Cf):
DENSITYEST (Tmix,e, EO)
5: Define the reward function rf for each agent as
dH((X) dX
(s) V )
X=ds
6: Each agent computes the (approximately) optimal policy on ry:
7/41 = APPROXPLAN (ri,e1)
7: Each agent updates
C/+1 (m. T m(11)
(6)
4/41 ((1 -1)a,, 1)-
77)
8: end for
9: Tmix,T N Ea Ct.).
15

---

Enhancing Diversity in Parallel Agents
Figure Two rooms gridworld, with starting position in the corridor and goal state in the left bottom corner.
Figure 6. Maze gridworld, with multiple path, goal state in the upper section
B. Experimental Details
Environments. In this paper, we present two distinct grid-world environments designed to illustrate the effectiveness of parallel exploration in enabling agents to overcome exploration bottlenecks and efficiently discover optimal trajectories in both structured and intricate scenarios.. In the first, two rooms are connected through a corridor with the goal positioned in the left room. In the second one, we considered a maze-like space, with a more complex layout with many bifurcations but only one path leading to a goal. The two environments are shown in Figures 5 and 6. In the following, we briefly describe the two environments more thorough.
B.1. Room
This is 5 x 11 grid world inspired by the toy example from Towers et al. (2024). It consists of two rooms connected by a single horizontal corridor. The agent moves until reaching the goal or the episode terminates. The starting position is fixed the center of the corridor, (2, 5). The agent navigates the grid using actions from {0, 1, 2, 3). where the index indicate Move left, 1: Move down, 2: Move right, 3: Move up. The observation space represents the player's current position an index computed by obs = row x ncols + col where rows and columns are zero-indexed. For instance, the goal position (4, 0) is mapped to 4 x 11 + 0- = 44.. The total number of observations depends on the grid size. The environment is evaluated in both reward-free and sparse-reward settings, where in the latter case reward function r S x A > IR with = upon reaching the goal and 0 otherwise. Throughout the paper, we consider two configurations:
Room-der: A deterministic version where exccuting an action a under policy Ty always results in the intended movement.
Room-stoc: A stochastic variant where the agent plays the intended action with probability 1 - p and deviate from with p.
B.2. Maze
This is grid world 10 x 10. The environment consists of a discrete grid-based navigation task, where an agent must reach a goal position while navigating through structured maze. The grid is structured to restricting movement specific corridors. The agent, starts from an initial position (5, 6) and can move in four directions: up, down, left, or right, as in the B.1 case. The goal serves as the terminal state, where the episode ends upon successful navigation after number of maximum steps. Upon a different structure, the environment shares with the previous environment the reward function, the action space and the state index conversion. In the paper we present two different version of the environment as following defined:
Maze-det: A deterministic version where executing an action a under policy He always results in the intended movement.
Maze-stoc: A stochastic variant where the agent plays the intended action with probability 1 - p and deviate from it with p.
Implementation Details of Algorithm 1.
As outlined in the pseudocode of Algorithm 1, in each episode, a batch | = 40, of K trajectories are experienced by parallel learners. K is fixed during the experiment always 1, due to
16

---

Enhancing Diversity in Parallel Agents
the assumption of having access the minimum size of possible interactions that the agents can have with respect the environment. To reproduce the policy gradient performance of the single agent, this K should coincide to the number of agent m, at which the single is compared to. Indeed, in the I with respectively {2, 6] agents involved, the single agent experiences K = {2, 6} trajectories. from which the state distribution d, is derived. Over the 10k episodes, the parallel agents interact with the environment with finite trajectories of lenght 7 that in the Room-det and Room-stoc environments is set to 8, while in Maze-det and Maze-stoc, due to a bigger state space, is set to 10.
The parallel policy, as collection of parametric single policy on a Softmax function defined as:
To(als) = EnEAee e0.
0 parameters are updated via gradient ascent maximization, with learning rate set initially to 0.1 with exponential decay rate λ of 0.999. The training is performed over 5 different seeds {0, 1, 42, 1333.
C. Further Experimental Details and Analysis
The code to reproduce the experiments is made available at the following link.
C.1. Performance of Four Parallel Agents
To further validate our approach, we extend the experimental analysis presented in the main body by including results for four parallel agents. Figure illustrates the performance of this configuration terms of normalized state entropy (top row) and support size (bottom row) across the four environments: Room-del, Room-stoe, Maze-del, and Maze-stoc.
As observed, the four-agent configuration consistently outperforms the single-agent baseline, achieving significantly higher normalized entropy and support size. This demonstrates the continued effectiveness of our parallelized exploration strategy, with the centralized update mechanism of Algorithm enabling the agents to collectively learn policies that lead to more diverse and comprehensive exploration of the state space.
However, it is also evident that the marginal benefit of adding more agents diminishes as the number of agents increases. This phenomenon is likely attributable to the relatively small size of the state space in the considered environments. With more agents, the overlap in their explored trajectories increases, leading less pronounced improvement for each additional agent.
C.2. Dataset Analysis
To further understand the benefits of parallel exploration, we analyze the datasets generated by the learned parametric policies. These datasets constructed analogously to those in the single-agent case and the random policy baseline. Specifically, for each parallel-agent configuration, we sample K = m trajectories to ensure consistent comparison across settings. The mean and standard deviation of the state entropy are computed over these trajectories and averaged across the five random seeds used during training. Let's look deeply at the dataset created from the paralell agents, when interacting with the more complex Maze environment. Figures 8 present heatmaps visualizing the state occupancy distributions for the Maze environments, respectively the deterministic and stochastic case. These heatmaps provide qualitative comparison of the exploration patterns achieved by single agents, parallel agents, in the two implemented versions.
C.3. Offfine Q-Learning Implementation
While single agents might discover effective exploration strategies, is the diversity inherent to our parallel policy induction that ensures robust and consistent state space coverage, even in stochastic environments. This diversity, validated across multiple random seeds, translates into highly informative dataset for downstream learning tasks. The effectiveness of our approach is further highlighted by the fact that this valuable dataset is constructed from a mere six trajectories per agent, significant improvement over the data generated by untrained policies. Combined with an offline procedure, the parallel approach incredibly speedup the learning procedure. For the construction of Figure 3, we implement an offline Q-learning algorithm. The agent learns from a replay buffer with a batch size of 20 (s, a, s',r) interactions. The experiences collected from the parallel agents are incorporated into the replay buffer, without interacting with the environment. The Q-learning agent trained for 100 episodes, with the Q-value function Q(s, a) being updated using a learning rate of a 0.1 and a
17

---

Enhancing Diversity in Parallel Agents
Agents
Agent
Agents
Agent K' 4K
Agents
Agent K' = 6K
Normlized States Entrony
Nomolttee States Enterpy
Namalted Statess Entrmoo
Nomaliees Statees
0.0
(..0
12k
Updates
Updates
Updates
Updates
(a) State Entropy (Room-der).
(b) State Entropy (Room-stoc).
(c) State Entropy (Maze-der).
(d) State Entropy (Maze-stoc).
22.5
40
30
25
17.5
20
15.0
Support
12:5
10
10.0
10
10
Updiates
Updates
Updates
Upditee
(e) Support (Room-det).
(I) Support (Room-stoc).
(g) Support (Maze-det),
(h) Support (Maze-stoc).
Figure 7. Performance of four parallel agents. The top row (a-d) shows the progression of normalized state entropy across different environments, while the bottom row (c-h) depicts the corresponding support size dynamies. Each plot illustrates the performance parallel agents against single instance visiting number of trajectories corresponding to the number of parallel agents.
discount factor of 7 0.99 according the Bellman equation update rule.
The high quality of the dataset generated by our parallel agents is further evidenced in Figure 9. The offline agent, trained solely on this data, demonstrates significantly improved goal-reaching capabilities, even in the stochastic environment, as indicated by the broader and warmer-colored regions of the heatmap. particularly for goals distant from the starting location.
C.4. Diversity Analysis
Figure 10 provides a visual comparison of the learned policies for parallel agents versus single agents in both Room-det and Maze-det environments. In the single-agent setting (Figures 10a and 10b), the agent tends to develop policies with higher stochasticity in its action choices. This a consequence of the need to explore larger portion of the state space alone, necessitating a more randomized approach to discover high-entropy trajectories. In contrast, the parallel agent setting (Figures 10c and 10d) reveals that the centralized update mechanism, based on the aggregate state distribution d,, encourages individual agents specialize more deterministic policies.
18

---

Enhancing Diversity in Parallel Agents
(a) Parallel Agents (Maze-det).
(b) Parallel Agents (Maze-stoc).
(c) Single Agent (Maze-det).
(d) Single Agent (Maze-stoc).
Figure 8. Dataset extrapolation based on the Maze environments.
19

---

Enhancing Diversity in Parallel Agents
Parallel
Single Agent
Random
(a) Offline Goal Reachability, learning from (b) Offline Goal Reachability, learning from (c) Offline Goal Reachability. learning from the parallel agents experience.
the single agents experience.
random policy experience.
Figure Offfine Result of Gained Experience
20

---

Enhancing Diversity in Parallel Agents
+
(a) Single Agent (Room-det).
(b) Single Agent (Maze-det).
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
x+
t
+
+
+
+
+
+
+
+
+
+
+
+
+
+
(c) Parallel Agents (Room-det).
+
+
+
+
(d) Parallel Agents (Maze-det).
Figure 10. Analysis of stochasticity and determinism of parallel vs. single agents.
21


Reviews:
[{"review_id": "jdRQif5vOU", "reviewer": "Reviewer_Fend", "summary": "This paper investigates how to effectively maximize state entropy exploration in parallel agent settings. The authors propose a framework where multiple agents, each operating in separate environment replicas, are trained to collectively maximize the entropy of their visited state distribution while promoting diversity among their exploration strategies. They introduce a parallel learning objective that explicitly balances individual agent entropy with inter-agent diversity, and develop a policy gradient algorithm (PGPSE) to optimize this objective. The paper includes theoretical analysis on concentration properties showing that parallel agents with diverse policies can achieve faster convergence to high-entropy distributions compared to single agents. Experimental results on gridworld environments demonstrate that the proposed approach outperforms single-agent baselines in terms of state entropy, support size, and performance in downstream offline RL tasks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Why didn’t the authors compare the proposed approach with diversity-promoting methods like DIAYN or diversity-centered MARL approaches?**\n\n- **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.  \n\n- **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.  \n\n- **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.  \n\n**How would the method perform in more complex environments beyond gridworlds? Have the authors considered extending the approach to continuous state and action spaces?**  \n\nWe 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.", "claims_and_evidence": "The paper's claims about the benefits of parallel exploration with diverse agents are generally supported by the theoretical and empirical evidence presented. However, the claim about the superiority of their approach over existing methods is not fully supported due to limited comparison with relevant baselines. While they show improvement over single-agent exploration and random policies, they don't compare against other methods specifically designed to promote diversity among agents (like DIAYN or diversity-promoting MARL approaches). This is a limitation in evaluating the novelty and effectiveness of their contribution.", "methods_and_evaluation_criteria": "The proposed methods for parallel state entropy maximization make sense for the problem at hand. The evaluation criteria focusing on normalized entropy, support size, and downstream offline RL performance are appropriate metrics for exploration quality. The environments used (gridworlds with different complexity levels) allow for clear visualization and interpretation of results. \n\nHowever, the paper  only consider simple discrete gridworld tasks and did not consider more challenging or continuous domains. The evaluation would be more convincing if it included more challenging environments beyond gridworlds and compared against state-of-the-art exploration methods that explicitly promote diversity, such as DIAYN or diversity-centered MARL approaches like \"Celebrating Diversity in Shared Multi-Agent Reinforcement Learning.\"", "theoretical_claims": "The theoretical analysis appears sound.", "experimental_designs_or_analyses": "The experimental design is generally sound but limited in scope. However, the experiments are confined to relatively simple gridworld environments, and the paper lacks comparison with more relevant baselines that specifically address diversity among agents. This makes it difficult to assess the true novelty and contribution of the proposed approach relative to existing methods.", "relation_to_broader_scientific_literature": "The paper builds upon prior work on state entropy maximization for exploration in reinforcement learning, particularly in the reward-free setting. It extends this concept to parallel settings, which is a relevant direction given the increasing use of parallelization in modern RL systems.\n\nHowever, the paper doesn't adequately position itself relative to literature on diversity-promoting exploration strategies. Particularly missing is comparison with methods like DIAYN which explicitly maximizes diversity among skills/policies, or diversity-centered MARL approaches like \"Celebrating Diversity in Shared Multi-Agent Reinforcement Learning\" which explicitly aims to increase diversity among agents' behaviors.", "essential_references_not_discussed": "It is quite appropriate, and it will be good to discuss Celebrating Diversity in Shared Multi-Agent Reinforcement Learning.", "other_strengths_and_weaknesses": "Strengths:\n- The theoretical analysis of concentration properties provides useful insights into why parallel diversity is beneficial.\n- The formulation of the parallel learning objective is elegant and intuitive.\n- The visualization of learned policies and datasets helps in understanding the behavior of the method.\n\nWeaknesses:\n- Limited comparison with relevant baselines that specifically address diversity among agents.\n- Experiments are confined to relatively simple gridworld environments.", "other_comments_or_suggestions": "- Consider expanding the experimental evaluation to include more complex environments.\n- The visualization in Figure 10 showing the different policies learned by parallel agents is interesting, but could benefit from more quantitative analysis of the diversity.", "questions_for_authors": "- Why didn't the authors compare the proposed approach with diversity-promoting methods like DIAYN or diversity-centered MARL approaches? Such comparisons would provide stronger evidence for the novelty and effectiveness of the approach.\n- How would the method perform in more complex environments beyond gridworlds? The current environments are too simple to fully demonstrate the benefits of parallel diversity.\n- Have the authors considered extending your approach to continuous state and action spaces, which are common in real-world applications like robotics?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FLlFjz97OD", "reviewer": "Reviewer_58WA", "summary": "This paper proposes an exploration framework for parallel agents with state entropy maximization and an analysis of the framework. They showed on tabular environments that parallel exploration covers the state space better than single-agent exploration with the same compute budget. And datasets collected by parallel agents also help post offline training.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's time and effort in evaluating our work, and we are grateful for the opportunity to provide further clarifications.\n\n**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?**\n\nPrecisely, 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.  \n\nConsider 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.  \nIn 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.  \n\n**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?**  \n\nThanks 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.  \n\n**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$?**  \n\nSince 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.  \n\n**Missing Reference**  \n\nRegarding 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:  \n\n- **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.  \n\n- **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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The derivation In lines 240-247 needs further explanation.\nI did not check Theorem A.2.", "experimental_designs_or_analyses": "I reviewed the experiments and they appear sound and well-reasoned.", "relation_to_broader_scientific_literature": "This paper provides proof-of-concept analysis for parallel exploration, which is relatively new and important to the key exploration problem for RL.", "essential_references_not_discussed": "Entropy-based diversity is not something new for multi-agent RL. See [1]  Lupu, Andrei, et al. \"Trajectory diversity for zero-shot coordination.\" [2] Zhao, Rui, et al. \"Maximum entropy population-based training for zero-shot human-ai coordination.\"", "other_strengths_and_weaknesses": "The paper is well-written. The experiments provide strong support for the hypothesis that parallel exploration is more efficient. While this work focuses on tabular environments, it would be interesting to see if the algorithm and analysis can be extended to a larger state space possibly with function approximation.\nThe hypothesis that parallel exploration is more efficient because each agent can focus on a smaller region is interesting and intuitive. This is also insightful for future works on exploration. I believe it is true, but I would like to see more support for the hypothesis.", "other_comments_or_suggestions": "No.", "questions_for_authors": "The ``Main Takeout’’ section argues that each agent can focus on different regions. 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?\n2. 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?\n3. In line 240-247, why can the log tricks be applied when $d_p$ is the mixture distribution, which does not only depend on $\\pi_i$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HfarC7o2Ms", "reviewer": "Reviewer_okjP", "summary": "This paper studies how parallel training facilitates exploration in reinforcement learning. The major result is that parallel exploration can not only obtain batched acceleration compared to single-agent ones, but it’s also possible to further improve sample complexity though diversity-driven policy design. The results come from a novel and careful analysis of parallel exploration procedure and are backed up through sufficient empirical experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.  \n\n**If the motivation is for the speed, how gradient descent step slow down the computation?**  \n\nWe 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.\n\nThe 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.\n\n**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?**  \n\nWe 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.  \n\nWe 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.  \n\nAs outlined in Theorem 4.1, a lower entropy state distribution means that fewer samples are needed to realize the target distribution approximately.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This result seems to be of broader interest in RL as more and more vectorized/parallel environment simulation is available in recent literature.", "essential_references_not_discussed": "Not I aware of.", "other_strengths_and_weaknesses": "### Strengths\n\nThis paper proposed a novel problem: if we can run n agents in parallel, how should we maximize the exploration (i.e., state occupancy entropy)?\n\nTurns out the answer is not as trivial as running the same \"uniform\" policy for n agents simultaneously. A better policy is to run $n$ different policies that each maximize the exploration for a sub-region, and in aggregation, we achieve a uniform distribution overall. The reason is that running a sub-region can give us a better sample complexity in terms of estimating state transitions and probabilities. After seeing the explanation, it feels obvious but the mathematical derivations are carried out satisfyingly, in particular the decomposition insights. \n\nWhat is more surprising is the policy gradient method proposed by the authors. Turns out that the gradient of the entropy objective for each single agent can be derived in a distributed manner (with aggregated empirical distribution). Therefore a practical algorithm can be carried in terms of maximizing exploration in a non-trivial way. \n\nThe paper is well-written. The model is clear and the analysis is intuitive, and experiments are conducted satisfyingly.  \n\n### Weakness\n\nOne question is that if the motivation is for the speed, how gradient descent step slow down the computation? This is not discussed in the paper.", "other_comments_or_suggestions": "1. For clarification, in line 204, the author claims: 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?\n\n2. Line 252, typo: double \"the\"", "questions_for_authors": "if the motivation is for the speed, how gradient descent step slow down the computation? Is that possible that we can synchronize the gradients once in a while so that parallelization can be maximized?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0IicNJ2j2x", "reviewer": "Reviewer_khWs", "summary": "This paper focuses on generating diverse experience for policy gradient algorithms in reward-free settings through the use of entropy maximisation and separate parallel policies. The method proposed is Policy Gradient for Parallel States Entropy Maximization (PGPSE). The empirical results on two grid-based environments show that more diverse policies lead to a higher entropy of collected states which corroborates the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Weaknesses: I feel the significance of this work is lacking.**\n\nWe 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.\n\n**If a core motivation of this work is practical applications, then why are the environments so simple?**\n\nPlease 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.\n\n**Why was training only shown for 2, 4, and 6 agents?**\n\nGiven 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.\n\n**I would like to see a small discussion around the higher variance introduced with more agents.**\n\nVariance 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.\n\n**Is there a reason why the gap in state entropy decreases as the number of agents increases?**\n\nIn 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.\n\n**Baselines makes it hard to place this work within the literature.**\n\nAs 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.", "claims_and_evidence": "While there is theoretical evidence for this method, the empirical evidence is severely lacking for multiple reasons:\n\n1. In section 5 the authors state: “As stated before, a core motivation of this work is addressing the problem of exploration in practical scenarios, where a strong parallelization of the environment is used to overcome the hardness to sample from complex simulators or even physical instantiations of the agents.”  If a core motivation of this work is practical applications, then why are the environments so simple? They only have 43 states, which is significantly simpler than the common benchmark environments used in similar work [mujoco,atari,gym].\n\n2. Why was training only shown for 2, 4 and 6 agents? Especially since a higher K’ leads to higher state entropy and larger support size in Figure 1 (for stochastic environments). It would be interesting to see the trend of the gap between single agent and multi-agent as the number of agents grows.\n\n3. I would like to see a small discussion around the higher variance introduced with more agents. Especially in the stochastic environments, as it seems more agents may not be statistically significantly better than a single agent in those environments given the high variance.", "methods_and_evaluation_criteria": "Not comparing to other baselines makes it hard to place this work within the literature. For example, Hazan, Elad, et al [maxent] compared to a random policy, it would have been interesting to compare to MaxEnt and a random policy. Another simple baseline that seems to have been left out is N distinct agents learning without the entropy objective.\n\nAdditionally, while multiple seeds were used for this work, I’d suggest that following the advice of Argarwal et al. [rliable] and doing a more rigorous evaluation.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "Yes, experimental design is valid, except for the fact that the environments are simple.", "relation_to_broader_scientific_literature": "It is related to a wealth of exploration literature and reward-free reinforcement learning, specifically those focusing on maximum entropy learning. It is also related to policy gradient methods in general, as in most cases rollouts are done in parallel, and thus this method could be applied.", "essential_references_not_discussed": "Not that I am aware of.", "other_strengths_and_weaknesses": "**Strengths:** I think the application to offline RL is very interesting and should be further emphasised throughout the paper and tested on harder problems.\n\n**Weaknesses:** I feel the significance of this work is lacking. The authors mention a large amount of potential future research and I believe that this would need to be included for this paper to be considered for ICML.. As it stands, the environments tested are very simple and the paper lacks baselines, which makes it impossible to place in the literature. Additionally, the clarity of the writing is poor  and is a significant weakness of this work.", "other_comments_or_suggestions": "The paper is poorly written, containing numerous grammatical and formatting errors. I cannot enumerate them all here, but here are a few examples:\n1. Figures 2 and 3 lack labels for what the colours are referring to.\n2. Page 1 second last paragraph: performances -> performance\n3. Page 4 section 4: “Main Takeout” -> “Main Takeaway”\n4. Page 4 section 5: “hardness” -> “difficulty”\n5. Page 4 section 5: “our attention now shift” -> “our attention now shifts”\n6. Page 7 section 6 (Offline RL): “Can dataset collected with parallel maximum entropy agents benefit offline RL algorithms on those data?” -> “Can datasets collected with parallel maximum entropy agents benefit offline RL algorithms”\n\n-----\n\n**References**\n\n[mujoco] Todorov, Emanuel, Tom Erez, and Yuval Tassa. \"Mujoco: A physics engine for model-based control.\" 2012 IEEE/RSJ international conference on intelligent robots and systems. IEEE, 2012.  \n[atari] Bellemare, Marc G., et al. \"The arcade learning environment: An evaluation platform for general agents.\" Journal of artificial intelligence research 47 (2013): 253-279.  \n[gym] Brockman, Greg, et al. \"Openai gym.\" arXiv preprint arXiv:1606.01540 (2016).  \n[maxent] Hazan, Elad, et al. \"Provably efficient maximum entropy exploration.\" International Conference on Machine Learning. PMLR, 2019.  \n[rliable] Agarwal, Rishabh, et al. \"Deep reinforcement learning at the edge of the statistical precipice.\" Advances in neural information processing systems 34 (2021): 29304-29320.", "questions_for_authors": "Is there a reason for why the gap in state entropy seems to decrease as you increase the number of agents? In Figure 1, it seems that the gap between 6 agents and K’ = 6 is lower than 2 agents and K’ = 2.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies generating diverse experience for policy gradient algorithms in reward-free settings through the use of entropy maximisation and parallel RL training to facilitates exploration.

Reviewers okjP, Fend and 58WA praised the problem formulation of maximising the exploration of multiple agents in parallel over subregions, and the mathematical derivation. Reviewer okjP praised the writing and clarity of the paper. Reviewer khWs found the application to offline RL interesting.

Reviewer khWs had multiple concerns about the empirical evidence provided in the paper, including on the simplicity of the environments and lack of baseline, but these were addressed during rebuttal. Reviewer 58WA suggested using larger state spaces for exploration. Reviewer Fend and the authors engaged in a discussion about the relevance of a few MARL-based references.

Based on the average score of 3.25, I believe that the paper should be accepted.
Decision: Accept (poster)