Towards Principled Unsupervised Multi-Agent Reinforcement Learning
Authors: Riccardo Zamboni
Mirco Mutti
Marcello Restelli
Venue: NeurIPS 2025 poster ()
Keywords: unsupervised reinforcement learning
state entropy maximization
multi-agent reinforcement learning
convex reinforcement learning
Primary area: reinforcement_learning

Abstract: In reinforcement learning, we typically refer to *unsupervised* pre-training when we aim to pre-train a policy without a priori access to the task specification, i.e., rewards, to be later employed for efficient learning of downstream tasks. In single-agent settings, the problem has been extensively studied and mostly understood. A popular approach casts the unsupervised objective as maximizing the *entropy* of the state distribution induced by the agent's policy, from which principles and methods follow. In contrast, little is known about state entropy maximization in multi-agent settings, which are ubiquitous in the real world. What are the pros and cons of alternative problem formulations in this setting? How hard is the problem in theory, how can we solve it in practice? In this paper, we address these questions by first characterizing those alternative formulations and highlighting how the problem, even when tractable in theory, is non-trivial in practice. Then, we present a scalable, decentralized, trust-region policy search algorithm to address the problem in practical settings. Finally, we provide numerical validations to both corroborate the theoretical findings and pave the way for unsupervised multi-agent reinforcement learning via state entropy maximization in challenging domains, showing that optimizing for a specific objective, namely *mixture entropy*, provides an excellent trade-off between tractability and performances.

Towards Principled Unsupervised Multi-Agent Reinforcement Learning
Riccardo Zamboni Politecnico di Milano riccardo. zamboni @pol imi
Mirco Mutti Technion
Marcello Restelli Politecnico di Milano
Abstract
In reinforcement learning. we typically refer to unsupervised pre-training when we aim to pre-train policy without priori access to the task specification, i.e., rewards, to be later employed for efficient learning of downstream tasks. In single- agent settings, the problem has been extensively studied and mostly understood. A popular approach casts the unsupervised objective as maximizing the entropy of the state distribution induced by the agent's policy, from which principles and methods follow. In contrast, little is known about state entropy maximization multi-agent settings, which are ubiquitous in the real world. What are the pros and cons of alternative problem formulations in this setting? How hard the problem theory, how can we solve practice? In this paper, we address these questions by first characterizing those alternative formulations and highlighting how the problem, even when tractable in theory, is non-trivial in practice. Then, we present a scalable, decentralized, trust-region policy search algorithm to address the problem in practical settings. Finally, we provide numerical validations to both corroborate the theoretical findings and pave the way for unsupervised multi-agen reinforcement learning via state entropy maximization showing that optimizing for a specific objective, namely mixture entropy, provides an excellent trade-off between tractability and performances.
challenging domains,
Introduction
Multi-Agent Reinforcement Learning [MARL, Albrecht et al., 2024 recently showed promising results in learning complex behaviors, such as coordination and teamwork [Samvelyan et al. 2019]. strategic planning in the presence of imperfect knowledge (Perolat al., 2022]. and trading [Johanson] et al. 2022). Just like in single-agent RL, however, most of the efforts are focused on tabula rasa learning, that is, without exploiting any prior knowledge gathered from offline data and/or policy pre-training. Despite its generality, learning tabula rasa hinders MARI. from addressing real-word world situations, where training from scratch slow, expensive, and arguably unnecessary [Agarwal et al.. 2022). In this regard, some progress has been made techniques specific to the multi-agent setting, ranging from ad hoc teamwork Mirsky et al. 2022 to zero-shot coordination (Hu et al. 2020), but understanding of what be done instead of learning tabula rasa is still limited.
In single- agent RL, unsupervised pre-training frameworks [Laskin et al. 2021) have emerged as viable solution: a policy is pre- pre-trained without priori access to the task specification, i.e., rewards, to be later employed for efficient learning downstream tasks. Among others, state-entropy maximization [Hazan et al.] 2019 [ee et al. 2019) was shown to be a useful tool for policy pre- training (Hazan al. 2019 Mutti al. 2021 and data collection for offline learning (Yarats et al.) 2022). In this setting, the unsupervised objective is cast maximizing the entropy of the state distribution induced by the agent's 's policy. Recently, the potential entropy objectives MARL was empirically corroborated by plethora of works [Liu et al. 202 Zhang al. 2021b Yang al. 2021
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Xu et al. 2024] investigating entropic reward-shaping techniques to boost exploration in downstream tasks. Yet, to the best of our knowledge, the literature still lacks a principled understanding of how state entropy maximization works in multi-agent settings, and how it can be used for unsupervised pre-training- Let us think of an illustrative example that highlights the central question of this work: multiple autonomous robots deployed in factory for production task. The robots' main goal is to perform many operations over large set of products, with objectives ranging from optimizing for costs and energy to throughput, which may change over time depending Arguably, trying to learn each possible task from scratch is inefficient and unnecessary. On the other hand, one could think of first learning to cover the possible states of the system and then fine-tune this general policy over a specific task. Yet, if everyone is focused on their own exploration, any incentive to collaborate with each other may disappear, especially when coordinating comes at cost for individuals. Similarly, covering the entire space might be unreasonable in most real-world cases. Here are looking for third alternative.
the market's condition.
Research Questions:
(Q1) Can we formulate multi-agent counterpart of the unsupervised pre-training via state entropy maximization in a principled way?
(Q2) How are different formulations related? Do crucial theoretical differences emerge?
(Q3) Can explicitly pre-train policy for state entropy maximization in practical multi-agent scenarios?
(Q4) Do crucial differences emerge in practice? Does this have an impact on downstream tasks learning?
Content Outline and Contributions. First, in Section 3. we address (Q1) by showing that the problem can be addressed through the lenses of a specific class of decision making problems, called convex Markov Games [Gemp et al.] 2024, Kalogiannis et al., [025], yet it can take different, alternative, formulations. Specifically, they differ on whether the agents are trying to jointly cover the space through conditionally dependent actions, they neglect the presence of others and deploy fully disjoint strategies, or they coordinate to cover the state space beforehand, but taking actions independently as components of mixture. We formalize these cases into three distinet objectives. Then, in Section[4] we address (Q2), highlighting that these objectives are related through performance bounds that scale with the number of agents. We also show that only the joint mixture objectives enjoy remarkable convergence properties under policy gradient updates in the ideal case of evaluating the agents' performance over infinite realizations (trials). However, as one shifts the attention the more practical scenario of reaching good performance over a handful, or even just one, trial, we show that different objectives lead to different behaviors and mixture objectives do enjoy more favorable properties. Then, in Section 5] we address (Q3) by introducing decentralized multi-agent policy optimization algorithm, called Trust Region Pure Exploration (TRPE), explicitly addressing state entropy maximization pre-training over finite trials. Finally, we address (Q4) by testing the algorithm on some simple yet challenging settings, showing that optimizing for a specific objective, namely mixture entropy, provides an excellent trade-off between tractability and performances. We show that this objective yields superior sample complexity and remarkable zero-shot performance when the pre-trained policy is deployed in sparse reward downstream tasks.
2 Preliminaries
In this section, we introduce the most relevant background and the basic notation.
Notation. We denote [N] := 21,2... N) for a constant N < cp. We denote a set with calli- graphic letter A and its size as [A|. For a (finite) set A = {1. 2................ J. we denote -i A/(i)
the set of all its elements but i. AA = x x A is the 7-fold Cartesian product of A. The simplex on A is A == {o E [0. 1|| E p(a) = 1} and A denotes the set of conditional distributions
p: P A - Ag. Let X, X' random variables on the set of outcomes X' and corresponding probability measures Px', we denote the Shannon entropy of X as H(X)
ExEx Px (1)) log(px (z))
and the Kullhack-Leibhe (KI.) divergence as DKL. (px lpxx)) E x Px (x) log(px (x)/px(()),
We denote (X1,.... Xr) a random vector of size T and x[t] its entry at position t E [T].

---

Interaction Protocol. As model for interaction, we consider mhritehorizonn Markov Games [MGs, Littman 1994] without rewards. A MG M := SN, p. T') a set S S of states, and set of (joint) actions A = (ii which we assume to be discrete and finite in size |S], |A| respectively. At the start of an episode, the initial state 81 of M is drawn from an initial state distribution μ E As. Upon observing $1, each agent takes action aj e A,, the system transitions to $2 ~ P(-|s1, @1) according to the transition model P e AS S.AA The process repeated until $T is reached and ST is generated, being T < dp the horizon of an episode. Each agent acts according to a policy, that can be either Markovian when the action is only conditioned on the current state, i.e., x² AS or non-Markovian when the action is conditioned on the history, i.e., '' E A [ Also, we will denote as decentralized iireeeeddfffofmtinnn policies the ones conditioned on either S; or S x A for agent i, and centralized inliiieeddifommttionnn ones the ones conditioned over the full state state-actions sequences. It follows that the joint action is taken according to the joint policy Ag 3 π = (x')=[
is composed of set of agents N,
Induced Distributions. Now, let us denote as S and S; the random variables corresponding to the joint state and i-th agent state respectively. Then the former is distributed as d= E As. where d (s) = $ [ Pr(st s|x, pi), the latter is distributed as dī As. where dī (s:) + E Pr(st, s, p)). Furthermore, let us denote with s, a the random vectors corresponding to sequences of (joint) states, and actions of length T, which are supported in AA respectively. We define p" ASTXAT, XAT, where p" (s, a) [ Pr(st s(t], a aft)). Finally, we denote the empirical state distribution induced by K e N+ trajectories [sk] as (s(s) = KT 2ne[K] >eerr [(s = s).
Convex MDPs and State Entropy Maximization. In the MDP setting (WV - 1), the problem of state entropy maximization can be viewed as a special case of convex RL [Hazan et al.] 2019 Zhang et al.) 2020 Zahavy et al. 2021]. In such framework, the general task is defined via an F-bounded concave utility function F As - (-00, FJ. with F < c0, that is a function of the state distribution d= This allows for generalization of the standard RL objective, which is linear product between a reward vector and the (actionction) distribution [Puterman 2014). Usually, some regularity assumptions through the following smoothness assumption:
enforeed on the function F. In the following, we align with the literature
Assumption 2.1 (Lipschitz). A function A - R is Lipschitz for some constant L << x,, or L-Lipschitz for short, if holds F(x) - F(y)l < L||z - yli. V(z, v) E A?.
More recently, Mutti et al. [022aa noticed that in many practical scenarios only a finite number of K E N+ episodes/trials can be drawn while interacting with the environment, and in such cases one should focus on dx rather than d'' As a result, they contrast the infinite-trials objective defined as (T) := F(d)) with a finite-trials one, namely Çx (x( : Bdg-pg F(dx), noticing that convex MDPs (cMDPs) are characterized by the fact that (x(T)) & Gz differently from standard (linear)
MDPs for which equality holds. In single-agent convex RL, state entropy maximization is defined as solving cMDP equipped with an entropy functional Hazan et al. 2019]. namely F(d")= (d").
Interestingly, even in single-agent settings, the infinite- anfinite-trials state entropy objective can be formulated as non-Markovian reward, as the value of being in a state depends on the states visited before and after that state As consequence, is not possible derive Bellman operators of any kind (Taáács) 1966. Whitchead and Lin [995] Zhang et al. 2020). Conversely, for lnite-trials formulations, it possible to define a Bellman operator by extending the state representation to include the whole trajectories of interaction. Unfortunately though, even this option is intractable as the size of such an extended MDP will grow exponentially?
3 Problem Formulation
This section addresses the first of the research questions outlined in the introduction.
In general, will denote the of valid per-agent policies with II' and the of joint policies with II. 'In practice, the function can be either convex. concave, or even non-convex. The term is used to distinguish the objective from the standard (linear) RL objective. We will assume F is concave if not mentioned otherwise. 'B conditioning with respect to the policy, such a reward would result to Markovian. However. the contraction argument does not appear to hold for a Bellman operator over this kind of policy-based rewards.
Indeed, the optimization of the finite- trial formulation is NP-hard Mutti et al. 2023).
3

---

(Q1) Can we formulate a multi-agent counterpart of the unsupervised pre-training via state entropy maximization principled way?
In fact, when reward function is not available, the core of the problem resides in finding well-behaved problem formulation coherent with the task. Gemp et al. (2024) recently intro- duced convex generalization of MGs called convex Markov Games (cMGis, namely a tuple P,F. My = A, pr, p., T), that consists in a MG equipped with (non-linear) functions of the stationary joint state distribution F. We expand over this definition, by noticing that state entropy maximization can be casted as solving a cMG equipped with an entropy functional, namely F(.) := (-). Yet, important new questions arise: Over which distributions should agents compute the entropy? How much information should they have access to? Can we define objectives accounting for finite number of trials? Different answers depict different objectives.
Joint Objectives. The first and most straightforward way to formulate the problem is to define it as in the MDP setting, with the joint state distribution simply taking the place of the single-agent state distribution. In this case, we define infiiit--rrils and finite-tritn Joint objectives, respectively
=((())
{<x(T))= == dx~pk
F(dx)) (I)
max EII NEEN]
max
(II (II NEEN]
In state entropy maximization tasks, an optimal (joint) policy will try to cover the joint state space uniformly, either in expectation over finite number of trials respectively. In this, the joint formulation is rather intuitive as describes the most general case of multi-agent exploration. Moreover, as each agent sees difference in performance explicitly linked others, this objective should be able to foster coordinated exploration. As we shall see, this comes at a price.
Disjoint Objectives. One might look for formulations that fully embrace the multi-agent setting, such as defining a set of functions supported on per-agent state distributions rather than joint distributions. This intuition leads to infinite-trials and finite-trials Disjoint objectives:
max x r'el''
:=
max Si (T) r'ent
:=
E AK
F(dK,))
(2)
SE[N]
According to these objectives, each agent will try to maximize her own marginal state entropy separately, neglecting the effect of her actions over others performances. In other words, we expect this objective to hinder the potential coordinated exploration, where one has to take as step down as so allow a better performance overall.
Mixture Objectives. At last, we introduce a problem formulation that will later prove capable of uniquely taking advantage of the structure of the problem. First, we introduce the following:
d
((s.)
d(s.)
S
Assumption 3.1 (Uniformity). The agents huve the same state space S = Sj (iv N x N
d(s S
S
Under this assumption, we will drop the agent sub- script when referring to the per-agent states and use S instead. Interestingly, this assumption allows us to define a particular distribution:
d(s
d<((8)
1
Σ e KE[M]
W
Figure 1: The interaction on the left induces different (empirical) distributions: Marginal distributions for agent 1 and agent over their respective states; a joint distribution over the product space; a mixture distribu- tion over common space, defined as the average. The mixture distribution is usually less sparse.
We refer to this distribution as mixture distribution, given that it is defined as a uniform mixture of the per- agent marginal distributions. Intuitively, it describes the average probability over all the agents to be in a common state & E S, in contrast with the joint
'One should notice that even in cMGs where this is not (even partially) the case, the assumption can be enforced by padding together the per-agent states.

---

distribution that describes the probability for them to be in a joint state or the marginals that describes the probability of each one of them separately. Figure provide a visual representation of these concepts. Similarly to what happens for the joint distribution, one can define the empirical distribution induced by K episodes as (3) = [ Eie dx,;(3) and d' Big-pr [dx]. The mixture distribution allows for the definition of the Mixture objectives, in their infinite and finite trials formulations respectively:
max (STTIIt))))) NGENT
==
max (xtell)) Ha[N]
{<x(T)= = E F(dx)}
(3)
When this kind of objectives is employed in state entropy maximization, the entropy of the mix- ture distribution decomposes H(d") = N EieNy] H H(T)) प Lieta] DRr.(d) (1] and one remarkable scenario arises: Agents follow policies possibly inducing lower disjoint entropies, but their induced marginal distributions are maximally different. Thus, the average entropy remains low, but the overall mixture entropy high due diversity (i.e., high values of the KL divergences). This scenario has been referred to in KKllchinsky and Tracey [2017] as the clustering scenario and, in the following, we will provide additional evidences why this scenario is particularly relevant.
Formal Characterization of Multi-Agent State Entropy Maximization
In the previous section, provided principled problem formulation of multi-agen aalti- state entropy maximization through an array different objectives. Here, we address the second research question:
(2) How are different formulation. related? Do crucial theoretical differences emerge?
First of all, we show that if we look at state entropy maximization tasks specifically, i.e. cMGs Mr equipped with entropy functionals F(.) == (-), all the objectives in infinite-trials formulation can be elegantly linked one to the other though the following result:
Lemma 4.1 (Entropy Mismatch). For every cMG for a fixed (joint) policy π = (TT))eN the infinite-trial objectives are ordered according to:
H(d=) W
Σ H(d)) & H(d") & sup H(d)) + log(IN)) & H(d")= + log([W]) ME[M]
W
The full derivation of these bounds is reported in Appendix This set of bounds demonstrates that the difference in performances over infinite-trials objective for the same policy can be generally bounded as function of the number of agents. In particular, disjoint objectives generally provides poor approximations of the joint objective from the point of view of the single-agent, while the mixture objective guaranteed be a rather good lower bound the joint entropy as well, since its over-estimation scales logarithmically with the number of agents.
It is still an open question how hard it is to actually optimize for these objectives. Now, while general cMGs My are an interaction framework whose general properties are far from being well-understodd, they surely enjoy some nice properties. In particular, it is possible exploit the fact that performing Policy Gradient [PG, Sutton et al. 1999 Peters and Schaal 2008 independently among the agents is equivalent running PG jointly, since this is done over the
common objective for Potential Markov Games [Leonardos et al., 2022 (see Lemma B.5 Appendix B.... This allows us to provide rather positive answer, here stated informally and extensively discussed in Appendix [..]]
Fact 4.1 (Anformal) Sufficiency of Independent Policy Gradient). Under proper assumptions, for ev- ery cMG My, independent Policy Gradient over infinite trials non-disjoint objectives via centralized- information policies of the form π (T' ' A ><s[A]] converges fast.
This result suggests that PG should be generally enough for the infinite-triale optimization, and thus, in some sense, these problems might not be of so much interest. However, cMDP theory has outlined that optimizing for infinite-trials objectives might actually lead to extremely poor performance as soon as the policies are deployed over just handful of trials, i.e. in almost any practical scenario [Mutti al, [223). We show that this property transfers almost seamlessly to eMGs as well, with interesting additional take-outs:
5

---

Theorem 4.2 (Finite-Triaa Mismatch in cMGs). For every cMG My equipped with a L-Lipschitz function F, let K No be a number of evaluation episodes/triass, and let E (0, 1] be a confidence level, then for any (joint) policy π (r' E IT')) KE(N) it holds that
S| log(2T/0)
2|5| log (2T/6)
(5x(T) - Soo (T)] & VTV
(sk(T) - (T) V
K
K
2 log 28)
(xo & LT
W
In general, this set of bounds confirms that for any given policy, infinite and finite trials performances might be extremely different, and thus optimizing the infinite-trials objective might lead to unpre- dictable performance at deployment, whenever this is done over a handful of trials, This property
inherently linked to the convex nature of cMGs, and Mutti et al. [2023] introduced it for cMDPs to highlight that the concentration properties of empirical state-distributions Weissman et al. (2003 allow for nice dependency settings, the result portraits a more nuanced scene:
the number of trials in controlling the mismatch. In multi-agent
(i) The mismatch still scales with the cardinality of the support of the state distribution, yet. for joint objectives, this quantity scales very poorly in the number of agents 0 Thus, even though optimizing infinite-triall joint objectives might be rather easy in theory Fact|4.1 suggests, it might result in poor performances in practice. On the other hand, the quantity is independent of the number of agents for disjoint and mixture objectives.
(ii) Looking at mixture objectives, the mismatch scales sub-linearly with the number of agents N. In some sense, the number of agents has the same role as the number of trials: The more the agents the less the deployment mismatch, and at the limit, with V - oc, the mismatch vanishes completely | In other words, this result portraits striking difference with respect to joint objectives: When facing state entropy maximization over mixtures, a reasonably high number of agents compared to the size of the state-space actually helps, and simple policy gradient over mixture objectives might be enough.
Remark 1. Although we do not claim that the mixture objective is the one-fits-all solution, is nonetheless well-founded. In particular whenever the rewards the agents will face in downstream tasks are equivalent for every agent, as it happens in relevant practical settings. When, on the other hand, the agents will aim to visit every joint state while solving for a specific task the joint entropy objective preferable, although it may be impractical: We report Appendix A an overall comparison of the two options, providing motivating example well.
Remark 2. Fact [4. is valid for centralized centralized-information policies only. Up our knowledge, no guarantees are known for decentralized dicentrraizee--iffoomattin policies even in linear MGs. Interestingly though, the unite-trials formulation does offer additional insights on the behavior of optimal decentralized- information policies: The interested reader can learn more about this in Appendix B.2
5 An Algorithm for Multi-Agent State Entropy Maximization in Practice
As stated before, a core drive of this work is addressing practical scenarios, where only a handful of trials can be drawn while interacting with the environment. Yet, Th. im2]iis that optimizing for infinite-trials objectives, as with PG updates in Fact 4.1] might result in poor performance at deployment. As result, here we address the third research question, that is:
(Q3) Can we explicitly pre-train a policy for state entropy maximization in practical mulli-agent scenarios?
To do so, we will shift our attention from infinite trials objectives to finite trials ones explic- itly, more specifically on the single-trial case with K = 1. Remarkably, it is possible to
'Indeed, in the case of product state-spaces S & the cardinality scales exponentially with the number of agents I.V.
In this scenario, all the bounds of Lemma 4.1 linking different objectives hecome vacuous.
For instance, when for agents the reward r(s, s') is different from r(s', .s), Le. the order matters.

---

directly optimize the single-trial objective in multi-agent cases with decentralized algorithms: We introduce Trust Region Pure Exploration (TRPE), the first decentralized algorithm that ex- plicitly addresses single-trial objectives in cMGs, with state entropy maximization cial case. TRPE takes inspiration from trust-region based methods as TRPO [Schulman et al.] 2015] due to their ability to address brittle optimization landscapes in which small change into the policy parameters of each agent may drastically change the value of the objective func- tion and the use of the trust region, like in TRPE, allows for accounting for this effect While the TRPE algorithm is new, the benefits of trust-region methods multi-agent settings recently enjoyed ubiquitous success and interest for their surprising effectiveness Yuu et al. 2022
spe-
In fact, trust-region analysis nicely align with the properties of finite-triall formu- lations and allow for an elegant exten- sion to cMGs through the following.
Trust Region Pure Exploration (TRPE)
Algorithm:
1: Input: exploration horizon T, trajectories N, trust-region threshold 6, learning rate 1)
Definition 5.1 (Surrogate Function over a Single Trial). For every cMG My equipped with a L-Liipshitz function let d1 be a general single-trial triial distribu- tion di = ddi,di,s, di3, then for any per-agent deviation over policies x (m', ")), tt = =("', (#', it is possible to define a per-agent Surrogate Func- tion (T//T) of the form L (+/x))-
2: Initialize 0 = (0* X=[[]]
frnnschittiinntioonn F,
2, ... until convergence do 4: Collect N trajectories with Te = (TTa kepv
3: for epoch
for agent i 1,2, concurrently do
6: Set datasets D {(5) (f)
7:
h 0, 0. =
8:
while DRL ( & do Compute (B( (6)) via IS as in Eq. 44 0 0% + 1y V 0% (0%
Edi-p7 F(d)) where p² is the per-agent importance-weight coefficient ((a'(+]['T P//a -i/pp = [EE(T)] ((11)
10:
11:
h h+1 1
12:
end while
13:
B -- 8%
From this definition, it follows that the trust-region algorithmic blueprint of Schulman et al. 2015) can be directly applied to single-trial formulations, with a parametric space of stochastic differ-
14:
end for
15:
end for
16:
Output: joint policy no (Tr
entiable policies for each agent o (T) Oi E e
c IR9).
In practice, KL-divergence is employed for greater scalability provided a trust-region threshold d, we address the following optimization problem for each agent:
max L'((' (8')
s.t. DKL ( &
where we simplified the notation by letting (0000/0) =- L' (Tr TT- ///i//o To)
10
The main idea then follows from noticing that the surrogate function in Def. 5.1 consists of an Importance Sampling (IS) estimator [Owen] 2013). and it is then possible to optimize it in fully decentralized and off-policy manner [Metelli et al. 2020, Mutti and Restelli 2020 More specif- ically, given a pre-specified objective of interest C E (G1, Si. (1), agents sample N trajectories {(s,,, a,) In)) [N[]v] following a (joint) policy with parameters O,- = (0), 0 They then compute the values of the objective for each trajectory. building separate datasets D = {(s),, a (f Jee[N] and using it to compute the Monte-Carlo approximation of the surrogate function, namely
(3((0//0))
1 N
Σ [N[
Pog.rg SP'
i.n Po
II Tbe (at, (2t,t))ss sE[T]
(4)
and CP is the plug-in estimator of the entropy based on the empirical measure di (Paninski] 2003
Finally, at each off-policy iteration h, each agent updates its parameter via gradient ascent 0 h+1
0f +n o4 Lt /0 until the trust-region boundary is reached, i.e., when it holds DKL, (TT) (T > 8.
The psudo-code of TRPE is reported in Al Algorithm T
We remark that even though TRPE is applied to
PPrevious works have connected the trust region with the natural gradient Pajarinen et al.
2019
#1 ---- g-1
"More precisely, L (m ag / :/TO)) F.
F, T
To
/pr
F(d)).
7

---

Mixture
Disjoint
Uniform
3.90
misture entrayy
1.05
3.80
24
(c) Mixture
(d) Joint
12
Samples
x10
Samples
x10
(a) Joint Entropy
(b) Mixture Entropy
(e) Disjoint
(f) Uniform
Figure 2: Single-trial Joint and Mixture Entropy induced by different objective optimization along a
T = 50 horizon. (Right) State Distributions of two agents induced by different learned policies. We
report the average and 95% confidence interval over 4 runs.
state entropy maximization, the algorithmic blueprint does not explicitly require the function F to be the entropy function and thus it is of independent interest.
Limitations. The main limitations of the proposed methods are two. First, the Monte-Carlo estimation of single-trial objectives might be sample-ineffiient in high-dimensional tasks. However, more efficient estimators of single-trial objectives remain an open question single-agent convex RL as well, as the convex nature of the problem hinders the applicability of Bellman operators. Secondly, the plug-in estimator of the entropy is applicable to discrete spaces only, but designing scalable estimators of the entropy in continuous domains is usually a contribution per [Mutti al., 2021
Empirical Corroboration
In this section, we address the last research question, that is:
(Q4) Do crucial differences emerge in practice? Does this have an impact on downstream tasks learning?
by providing empirical corroboration of the findings discussed so far. Especially, we aim to answer the following questions: (Q4.1) Algorithm aactually capable of optimizing finite-trials objectives? (Q4.2) Do different objectives enforce different behaviors, as expected from Section (3 (Q4.3) Does the clustering behavior of mixture objectives play a crucial role? If yes, when and why?
Throughout the experiments, we will compare the result of optimizing finite-trial objectives, either joint, disjoint, mixture ones, through Algorithm via fully decentralized policies. The experiments will be performed with different values of the exploration horizon T' so as to test their capabilities in The full implementation details are reported in Appendix C
different exploration efficiency regimes [
Experimental Domains. The experiments were performed with the aim to illustrate essential features of state entropy maximization suggested by the theoretical analysis, and for this reason the domains were selected for being challenging while keeping high interpretability. The first is a notoriously difficult multi-agent exploration task called secref room [MPE, Liu et al. 2021 referred as Env. (i). In such task, two agents are required to reach a target while navigating over two rooms divided by door. In order keep the door open, least one agent have to remain on switch. Two switches are located at the corners of the two rooms. The hardness of the task then comes from the need of coordinated exploration, where one agent allows for the exploration of the other. The second is a simpler exploration task yet over high dimensional state-space, namely 2-agent instantiation of Reacher [MaMuJoCo, |eng al., 2021]. referred to as Env. (ii). Each agent corresponds one joint and equipped with decentralized information policies. In order to allow for the use of plug-in estimator of the entropy (Paninski] 2003). each state dimension was discretized over 10 bins.
State Entropy Maximization, As common for the unsupervised RL. framework Hazan et al. 2019
Laskin et al. 2021 Liu and Abbeel| 2021b Mutti al. 2021] Algorithm T was first tested in her
"The exploration horizon I', rather than being given trajectory length, has to be seen a parameter of the exploration phase which allows to tradeoff' exploration quality with exploration efficiency.
Fe highlight that all previous efforts in this task employed hand, we are interested on the role of the entropic feedback in fostering coordination rather than full-state conditioning, thus employed decentaalized-informatooon policies.
intrrliized-fffmmmttioo policies. On the other

---

Mixture
Joint
Disjoint
Random Inirialization
ROGD-
Averagefeltum
Averageleitum
Averagoilatum
6000
8000
10000-
2000
0.00 0.25
0.75 1.00 125 Samples
1.50
XI0
Semples
x16
Zere Shot
Post Leaming
(a) MA-TRPO + TRPE
(b) MA-TRPO+ + TRPE
(c) MA-TRPO + TRPE Pre- Training
Pre- Pre-Training (Env. (i), 7 = 150)
Pre-Training (Env. (i), T 50)
(Env. (ii), T 100)
Figure 3: Effect of pre-training in sparse-reward settings. (Left) Policies initialized with either Uniform or TRPE pre-trained policies. (Right) Policies initialized with either Zero-Mean or TRPE pre-trained policies. We report the average and 95% c.i. over runs over worst-case goals.
ability to optimize for state entropy maximization objectives, thus in environments without rewards. In Figure 2 we report the results for a short, and thus more challenging, exploration horizon (T' 50) over Env. (i), as it is far more interpretable. Other experiments with longer horizons or over Env. (ii) Interestingly. at this challenging exploration regime, when looking at the joint entropy in Figure 2a joint and disjoint objectives perform rather well compared to mixture ones terms of induced joint entropy, while they fail to address mixture entropy explicitly, as seen in Figure 26] On the other hand mixture- objectives result in optimizing both mixture and joint entropy effectively, as one would expect by the bounds in Th. 4.1 By looking the actual state visitation induced by the trained policies, the difference between the objectives is apparent. While optimizing joint objectives, agents exploit the high-dimensionnalty of the joint space to induce highly entropic distributions even without exploring the space uniformly via coordination (Fig. 2d); the same outcome happens in disjoint objectives, with which agents focus on over-optimizing over restricted space loosing any incentive for coordinated exploration (Fig. 2cp. On the other hand. mixture objectives enforce a clustering behavior (Fig. 2e and result in better efficient exploration
can be found in Appendix
C
Policy Pre- Pre-Trainig via State Entropy Maximization. Importantly, while metrics in Fig. 2 are indeed interesting qualitative metrics, especially to understand how the unsupervised optimization process works, they do not fully capture the ultimate goal in a vacuum: the ultimate goal of unsu- pervised (MA)RL to provide good pre-trained models for (MA)RL, As such, the most important experimental metric to look at is the return achieve in downstream tasks, where the policy optimizing the mixture entropy fares well in comparison to others. Thus, we tested the effect of pre-training poli- cies via state entropy maximization as a way to alleviate the well-known hardness of -rward settings. In order to do so, we employed a multi-agent counterpart of the TRPO algorithm Schulman eet al. 2015) with different pre-trained policies. First, investigated the effect on the learning curve in the hard curd-exploration task of Env. (i) under long horizons (T = 150). with a worst-case goal set on the opposite corner of the closed room. Pre-training via mixture objectives still lead to faster learning compared to initializing the policy with a uniform distribution. On the other hand, joint objective pre-training did not lead to substantial improvements over standard initializations. More interestingly, when extremely short horizons were taken into account (T 50) the difference became appalling. shown in Fig. Ba pre-training via mixture-based objectives lead faster learning and higher performances, while pre-training via disjoint objectives turned out to be even harmful (Fig. (b)). This was motivated by the fact that the disjoint objective overfitted the task over the states reachable without coordinated exploration, resulting in almost deterministic policies, as shown in Fig. 5 in Appendix(C C Finally, we tested the zero-shot capabilities of policy pre-training on the simpler but high dimensional exploration task of Env. (ii), where the goal was sampled randomly between worst-case positions at the boundaries of the region reachable by the arm. As shown in Fig. 4p both joint and mixture were able to guarantee zero-shot performances via pre-training compatible with MA-TRPO after learning over 2e4 samples, while disjoint objectives were not. On the other hand, pre-training with joint objectives showed an extremely high- high-variance, leading to worst-case performances not better than the ones of random initialization. Mixture objectives on the other hand showed higher stability in guaranteeing compelling zero-shot performance. These results are the first to extend findings from single-agent environments [Zisselman et al. 2023 to multi-agent ones.
While it is true that mixture objectives optimization appears to lead to slower optimization, this is the result of such pathological behaviors.

---

Takeaways. Overall, the proposed experiments managed to answer to all of the experimental questions: (Q4.1) Algorithm iss indeed able optimize for finite-trial objectives: (Q4.2) Mixture objectives enforce coordination, essential when high efficiency is required, while joint or disjoint objectives may fail to lead to relevant solutions because of under or over optimization; (Q4.3) The efficient coordination through mixture objectives enforces the ability of pre-training via state entropy maximization to lead to faster and better training and even zero-shot generalization.
7
Related Works
Below, we summarize the most relevant work investigating related concepts.
Entropic Functionals in MARL. A large plcthora of works on both swarm robotics [McLurkin and Yamins 2005 Breitenmoser et al. [0100] and multi-agent intrinsic motivation, such as [Iqbal and Sha 2019 Yang et al. | [021] Zhang et al. 20216 2023 Xu et al. 2024| Toquebiau et al. 2024 investigated the effects of employing entropic- like functions to boost exploration and performances in down-stream tasks. Importantly, these works are of empirical nature, and they do not investigate the theoretical properties of eMGs or multi-agent state entropy maximization, nor they propose al algorithms able to pre-train policies without access to extrinsic rewards [4] Finally, while a similar
notion of eMGs was proposed in [Gemp al. 2024 Kalogiannis et al.. 2025 their contributions focused on the existence and computation of equilibria and performance of centralized algorithms over infinite-trials objectives.
State Entropy Maximization. Entropy maximization in MDPs was first introduced in Hazan et al. [2019] and then investigated extensively in various subsequent works [e.g.. Mutti and Restelli 2020
Mutti et al.
2021 2022b]c c Muttil [023 Liu and Abbeel 2021b a Seo et al. 2021| Yarats et al. 2021
Zhang al. 2021a| la Guo al. [022 Yuan al. 2022 Nedergaard and Cook 2022 Yang and S Spaan
2023 Dapkinn et al.
2023 Jain et al.
2023 Kim et al. 2023 Zisselman et al. [003]] Li et al.] 2024
Bolland al. 2024
Zamboni et al. 2024b De Paola al. 2025 Its infinite-trials formulation
can also be seen as a particular lar reward-free instance of state-entropy regularized MDPs [Brekelmans
jet al., 2022 Ashlag et al. 2025]. although this reduction does not alleviate the aforementioned
criticalitie litee in solving such problems in multi-agent settings. To the best of our knowledge, our work the first to study a multi-agent variation of the state entropy maximization problem.
Policy Optimization. Finally, our algorithmic solution (Algorithm) I draws heavily on the literature of policy optimization and trust-region methods (Schulman et al. 20133] Specifically, we considered an IS policy gradient estimator, which is partially inspired by the work of Metelli et al. [2020], but considers other forms of IS estimators, such as non- parametric k-NN estimators previously employed
in Mutti et al. [021]]
8 Conclusions and Perspectives
In this paper, we introduce principled framework for unsupervised pre-training in MARL via state entropy maximization. First, we formalize the problem as a convex generalization of Markov Games, and show that it can be defined via several different objectives: one can look at the joint distribution among all the agents, the marginals which are agent-specific, the mixture which is tradeoff of the two. Thus, we link these three options via performance bounds and we theoretically characterize how the problem, even when tractable in theory, is non-trivial in practice. Then, design a practical algorithm and we use it in a set of experiments to confirm the expected superiority of mixture objectives in practice, due to their ability to enforce efficient coordination over short horizons. Future works can build over our results in many directions, for instance by pushing forward the knowledge convex Markov Games, developing scalable algorithms for continuous domains, performing extensive empirical investigation over large scale problems. We believe that our work can be a crucial step in the direction of extending policy pre-training via state entropy maximization in principled way to yet more practical settings.
"The interested reader refer Mutti al. of the fundamental differences between intrinsic motivation and state entropy maximization. 15 *Conversely, the finite-trial formulation targeted by Algorithm | is not studied in the literature of regularized
202 Liu and Abbeel (0211) for extensive investigation
MDPs
10

---

References
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare. Reincarnating Reinforcement Learning: Reusing prior computation to accelerate progress. Ad- vances neural information processing systems, 2022.
Stefano V. Albrecht, Filippos Christianos, and Lukas Schäfer. Multi-Agent Reinforceeett Learning: Foundations and Modern Approaches. MIT Press, 2024. Uttphttps://www. marl maaaabooooo...... com.
Yonatan Ashlag, Uri Koren, Mirco Mutti, Esther Derman, Pierre-Lue Bacon, and Shie Mannor. State entropy regularization for robust reinforcement learning. arXiv preprint arXiv:2506.07000 2025.
Jan Beirlant, Edward Dudewicz, László Györfi, Edward C Van der Meulen, al. Nonparametric entropy estimation: An overview. International Journal of Mathematical and Statistical Sciences, 6(1):17-39, 1997.
Dimitri P Bertsekas and John N Tsitsiklis. Introduction to probability (athena scientific, belmont, ma). EKLER EK A: Siralt Istatistik Ek B: Integrallerin Saysal Hesabı EK B, 1, 2002.
Adrien Bolland, Gaspard Lambrechts, and Damien Ernst. Off-policy maximum entropy rl with future state and action visitation measures. arXiv preprint arXiv:2412.06665, 2024.
Andreas Breitenmoser, Mac Schwager, Jean-Claude Metzger, Roland Siegwart, and Daniela Rus. Voronoi coverage of non-convex environments with a group of networked robots. IEEE international conference robotics and automation, 2010.
Rob Brekelmans, Tim Genewein, Jordi Grau-Moya, Grégoire Delétang, Markus Kunesch, Shane Legg, and Pedro Ortega. Your policy regularizer is secretly an adversary. arXiv preprint 1xXiv:2203.12592, 2022.
Vincenzo De Paola, Riccardo Zamboni, Mirco Mutti, and Marcello Restelli. Enhancing diversity in parallel agents: A maximum state entropy exploration story. In Internation Conference on Machine Learning, 2025.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep Reinforcement Learning for continuous control. In International Conference Machine Learning, 2016.
Ian Gemp, Andreas Haupt, Luke Marris, Siqi Liu, and Georgios Piliouras. Convex markov games: framework for creativity, imitation, fairness, and safety multiagent learning. arXiv preprint arXiv:2410. 16600, 2024.
Zhaohan Daniel Guo, Mohammad Gheshlagi Azar, Alaa Saade, Shantanu Thakoor, Bilal Piot, Bernardo Avila Pires, Michal Valko, Thomas Mesnard, Tor Lattimore, and Rémi Munos. Geometric entropic exploration. arXiv preprint arXiv:2 101. 022055, 2021.
Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference Machine Learning, 2019.
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. "Other-Play" for zero-shot coordination. In International Conference on Machine Learning, 2020.
Shariq Iqbal and Fei Sha. Coordinated exploration via intrinsic rewards for multi-agent Reinforcement Learning. arXiv preprint arXiv: 1905. 12127, 2019.
Arnav Kumar Jain, Lucas Lehnert, Irina Rish, and Glen Berseth. Maximum state entropy exploration using predecessor and successor representations. In Advances in Neural Information Processing Systems, 2023.
Michael Bradley Johanson, Edward Hughes, Finbarr Timbers, and Joel Z Leibo, Emergent bartering behaviour in multi-agent reinforcement learning. arXiv preprint w:Xiv:2205.06660 2022.
Fivos Kalogiannis, Emmanouil- Vasileios Wlatakis-Gkarageee Ian Gemp, and Georgios Piliouras. Solving zero-sum convex markov games. arXiv preprint :05t:::20061622200 2025.
11

---

Dongyoung Kim, Jinwoo Shin, Pieter Abbeel, and Younggyo Seo. Accelerating reinforcement learning with value-conditional state entropy exploration. In Advances in Neural Information Processing Systems, 2023.
Artemy Kolchinsky and Brendan Tracey. Estimating mixture entropy with pairwise distances. Entropy. 19(7):361, 2017.
Michael Laskin, Denis Yarats, Hao Liu, Kimin Lee, Albert Zhan, Kevin Lu, Catherine Cang, Lerrel Pinto, and Pieter Abbeel. URLB: Unsupervised Reinforcement Learning benchmark. Advances in Neural Information Processing Systems ( (Datasels & Benchmarks), 2021.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdinov. Efficient exploration via state marginal matching. arXiv preprint 190.00096 2019.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. In International Conference on Learning Representations, 2022.
Hongming Li, Shujian Yu, Bin Liu, and Jose C Principe. Element: Episodic and lifelong exploration via maximum entropy. arXiv preprint arXiv:24/2.03800, 2024.
Michael L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine Learning Proceedings, pages 157-163. 1994.
Hao Liu and Pieter Abbeel. APS: Active pretraining with successor features. Conference Machine Learning, 2021a.
International
Hao Liu and Pieter Abbeel. Behavior from the void: unsupervised active pre-training. In Advances on Neural Information Processing Systems, 2021b.
Iou-Jen Liu, Unnat Jain, Raymond A Yeh, and Alexander Schwing. Cooperative exploration for
multi-agent deep reinforcement learning. In International Conference on Machine Learning, 2021.
James McLurkin and Daniel Yamins. Dynamic task assignment in robot swarms. In Robotics: Science and Systems, volume 8. Cambridge, USA, 2005.
Alberto Maria Metelli, Matteo Papini, Nico Montali, and Marcello Restelli. Importance sampling techniques for policy optimization. Journal of Machine Learning Research, 21(141) 2020.
Reuth Mirsky, Ignacio Carlucho, Arrasy Rahman, Elliot Fosong, William Macke, Mohan Sridharan, Peter Stone, and Stefano V Albrecht. A survey of ad hoc teamwork research. In European conference on multi-agent systems, 2022.
Mirco Mutti. Unsupervised reinforcement learning via state entropy maximization. PhD Thesis, Università di Bologna, 2023.
Mirco Mutti and Marcello Restelli. An intrinsically-motiitte approach for learning highly exploring and fast mixing policies. AAAI Conference on Artificial Intelligence, 2020.
Mirco Mutti, Lorenzo Pratissoli, and Marcello Restelli. Task-agnostic exploration via policy gradient of a non-parametric state entropy estimate. In AAAI Conference on Artificial Intelligence, 2021.
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Challenging com- mon assumptions in convex reinforcement learning. Advances in Neural Information Processing Systems, 2022a.
Mirco Mutti, Riccardo De Santi, and Marcello Restelli. The importance of non-Markovianity in maximum state entropy exploration. In International Conference on Machine Learning, 2022b.
Mirco Mutti, Mattia Mancassola, and Marcello Restelli. Unsupervised reinforcement learning in multiple environments. In AAAI Conference on Artificial Intelligence, 2022c.
Mirco Mutti, Riccardo De Santi, Piersilvio De Bartolomeis, and Marcello Restelli. Convex reinforce- ment learning in finite trials. Journal of Machine Learning Research, 24(250): 2023.
12

---

Alexander Nedergaard and Matthew Cook. k-means maximum entropy exploration. arXiv preprint arXiv:2205.15623, 2022.
Art B. Owen. Monte Carlo theory, methods and examples. 2013.
Joni Pajarinen, Hong Linh Thai, Riad Akrour, Jan Peters, and Gerhard Neumann. Compatible natural gradient policy search. Machine Learning, 108(8): 11444-14666 2019.
Liam Paninski. Estimation of entropy and mutual information. Neural Computation, 15(6): (566)1191-12555 2003.
Bei Peng. Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. FACMAC: Factored multi-agent centralised policy gradients. Advances in Neural Information Processing Systems, 2021.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent Reinforcement Learning. Science, 378(6623) 996, 2022.
Jan Peters and Stefan Schaal. Reinforcement learning of motor skills with policy gradients. Neural Networks, 2008.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: 1902.04043, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, 2015.
Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbecl, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. International Conference on Machine Learning, 2021.
Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient methods for Reinforcement Learning with function approximation. In Advances Neural Information Processing Systems, 1999.
Takács. Non-markovian processes. In Stochastic Process: Problems and Solutions, pages 46-62.
Springer, 1966.
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Pierre Perrault, Yunhao Tang. Michal Valko, and Pierre Menard. Fast rates for maximum entropy exploration. In International Conference on Machine Learning, 2023.
Maxime Toquebiau, Nicolas Bredeche, Faïz. Benamar, and Jae- Yun Jun. Joint intrinsic motiva- tion for coordinated exploration multi-agent deep Reinforcement Learning. arXiv preprint arXiv:2402.03972, 2024.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú, and Marcelo J. Weinberger. Inequalities for the 11 deviation of the empirical distribution. 2003,
Steven D) Whitehead and Long-Ji Lin. Reinforcement learning of non-markov decision processes. Artificial Intelligence, 73(1-2):271-306 1995.
Pei Xu, Junge Zhang, and Kaiqi Huang. Population- capsla diverse exploration for spwrse-reward multi-agent tasks. In International Joint Conference on Artificial Intelligence, 2024.
Huanhuan Yang, Dianxi Shi, Chenran Zhao, Guojun Xie, and Shaowu Yang. Ciexplore: Curiosity and influence-based exploration in multi-agent cooperative scenarios with sparse rewards. ACM International Conference Information & Knowledge Management, 2021.
13

---

Qisong Yang and Matthijs TJ Spaan. CEM: Constrained entropy maximization for task- aanostgc safe exploration. AAAI Conference on Artificial Intelligence, 2023.
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Reinforcement learning with
prototypical representations. In International Conference on Machine Learning, 2021.
Denis Yarats, David Brandffobrenner, Hao Liu, Michael Laskin, Pieter Abbeel, Alessandro Lazaric, and Lerrel Pinto. Don't change the algorithm, change the data: Exploratory data for offline Reinforcement Learning. arXiv preprint arXiv:2201.13425, 2022.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effecctiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Systems, 2022.
Mingqi Yuan, Man-On Pun, and Dong Wang. Rényi state entropy maximization for exploration acceleration in reinforcement learning. IEEE Transactions on Artificial Intelligence, 4(5):115 1154 1164, 2022.
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex MDPs. Advances in Neural Information Processing Systems, 2021.
Riccardo Zamboni, Duilio Cirino, Marcello Restelli, and Mirco Mutti. How explore with belief: State entropy maximization in POMDPs. In International Conference on Machine Learning, 2024a.
Riccardo Zamboni, Duilio Cirino, Marcello Restelli, and Mirco Mutti. The limits of pure exploration in POMDPs: When the observation entropy is enough. RLJ, 2:676-699 2024b.
Chuheng Zhang, Yuanying Cai, Longbo Huang, and Jian Li. Exploration by maximizing Rényi entropy for reward-free framework. AAAI Conference on Artificial Intelligence, 2021a.
Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for Reinforcement Learning with general utilities. Advances in Neural Information Processing Systems, 2020.
Shaowei Zhang, Jiahan Cao, Lei Yuan, Yang Yu, and De-Chuan Zhan. Self-motivated multi-agent exploration. arXiv preprint arXiv:2301. 200000080000 2023.
Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph Gonzalez, and Stuart Russell. MADE: Exploration via maximizing deviation from explored regions. Advances in Neural Information Processing Systems, 2021b.
Ev Zisselman, Itai Lavie, Daniel Soudry, and Aviv Tamar. Explore to generalize zero-shot RL. Advances in Neural Information Processing Systems, 2023.
14

---

A Further Insights on the Unsupervised Objectives.
Motivating Example. Let envision team of agents in a "search and rescue" task. In specific building (environment) the target may found different place (different rewards) and the unsupervised pre-training phase aims to prepare for all of them. Mixture entropy is good surrogate objective in this case, as the agents will split up into different portions of the buildings to traverse in order to find the target quickly.
Clarification on the Ideal Objective: Joint and Mixture Objectives Comparison
As in single-agent settings, the goal of unsupervised (MA)RL via state entropy pre-training is to learn exploration for any possible task while interacting with reward-free environment. If the tasks is assumed to be represented through state-based reward functions, the latter translates into state
coverage: The state entropy is proxy for state coverage [Hazan al. 2019 Mutti et al. 2021 Liu and Abbeel 2021b].
As consequence, the most natural state entropy formulation in Markov games is the joint state entropy. However, it comes with some important drawbacks:
The support of the entropy grows exponentially with the number of agents | so does the complexity the entropy estimation problem [Beirlant et al. 1997|
Estimation.
Concentration. The empirical entropy concentrates as v K for K trajectories (see Thm. 4.2
Redundancy. When Asm. 3.1 holds and the state space |S| is the same for every agent, the joint entropy may inflate state coverage as (s, 8') and (s', are different joint states.
In other words, the problem of optimizing the joint entropy suffers from the curse of multiagency, which particularly relevant in practice (while their difference might not be relevant in ideal settings, see Fact 4.1 and Thm. B.6
Another potential formulation is the mixture state entropy. which has the following properties:
Estimation.
The support of the entropy and therefore the estimation complexity do not grow with the number of agents;
Concentration. The empirical entropy concentrates as ((KW)) for K trajectories (see Thm. 4.2
Redundancy. For the mixture entropy objective, the joint states s') and (s', s) contributing in the same way; therefore, there no difference visiting one or the other.
The latter can be a limitation when we aim to explore all the possible joint states, e.g., when the reward functions of the agents will be different in the eventual tasks. Yet, at least the mixture entropy also a lower bound to the joint entropy objective with a log(IVV) approximation (see Lem. 4.1 and thus valid proxy also in the latter case, given the favorable estimation and concentration properties.
B Proofs of the Main Theoretical Results
In this Section, we report the full proofing steps of the Theorems and Lemmas in the main paper.
Lemma 4.1 (Entropy Mismatch), For every eMG Mn. for fixed (joint) policy = (TT))eN the infinite-trial -riils objectives are ordered according to:
H(d") W
1
Σ H(d)) M
H(d") sup H(d)) + log(IVV) H(d)) log((N]) MM[s
W
Proof. The bounds follow directly from simple yet fundamental relationships between entropies of joint, marginal and mixture distributions which can be found in Paninski (2003). Kolchinsky and
15

---

Tracey (017]] in particular:
H(d
&
Σ H(d)) iE[N]
H(d)
Σ H(d)) + Iog((W])
W
M
M
sup H( log([<]) & Hdd") + log(I-V)
M=[M]
where step (a) and (b) use the fact that d= (-)
: Li EiENy de (s) uniform mixture over the agents, whose distribution over the weights has entropy log( (W(() so as we can apply the bounds
from Kolchinsky and Tracey [2017]. Step (c) uses the fact that H (d Exe( (d) (d]1dZ)) then
taking the supremum as first it follows that supse[A]] H(d)) H(d") E JelNis H(d d di) < H (d") due to non-negativity of entropy.
Theorem 4.2 Finite-Trials Mismatch in cMGs). For every cMG My equipped with a L-Lipschitz function F, let K N+ be number of evaluation episodes/trial,, and let E (0, 1] be confidence level, then for any (joint) policy π = (x² E [T')) it holds that
S|5] log(2T/5)
2|51 (2gg(2T/))
(5x(T) - (T)) & LT
(x)(T) (T)) LT
K
K
2|S] log 28
(xx(T) - ( & ITT
W
Proof. For the general proof structure, we adapt the steps of Mutti et al. [022a for cMDPs to the different objectives possible cMGs. Let us start by considering joint objectives, then:
[<x(=) - (TO(T]]
E dx -ok
[F(dk)] -(dd))
&
[[F(dx) [d
dx dx-pk
[L|cd d=
[|dx d=1,
dg P
dx
(b)
max dk,, - dff ll [E[T]
dg-pj
where in step (a) we apply the Lipschitz assumption on to write and step (b) we apply maximization over the episode's step by noting that dx + E dx and d 7 L dj. We then apply bounds in high probability
Pr max ldx, di 20) Pr (1 ld dīl =c)
[E(T]
Pr
[dxx, dili 3
TT Pr [dk, - di >c).
with e and in step (c) we applied union bound.
We then consider standard concentration
inequalities for empirical distributions [Weissman et al.
2003 so to obtain the final bound
2|5] log(2/8)
[dk, - d, > Pr
$ 8'
(5)
K
By setting 8' = 5/T, and then plugging the empirical concentration inequality, we have that with probability least 1 1-
S|S] log (2
(x((T) Soo(T)) < LT
K
which concludes the proof for joint objectives.
16

---

The proof for disjoint objectives follows the same rational by bounding each per-agent term separately and after noticing that due to Assumption 3.I the resulting bounds get simplified in the overall averaging. As for mixture objectives, the only core difference is after step (b), where dx takes the place of dx and dx of d= The remaining steps follow the same logic, out of noticing that the empirical distribution with respect to d= taken with respect [V] K samples in total. Both the two bounds then take into account that the support of the empirical distributions have size |S] and not |S|.
B.1 Policy Gradient in cMGs with Infinite-Trian Formulations.
In this Section, we analyze policy search for the infinite-trials joint problem Soo of Eq. ( via projected gradient ascent over parametrized policies, providing in Th. [.6 the formal counterpart of Fact|4.1] in the Main paper. As side note, all of the following results hold for the (infinite-trials) mixture objective Soe of Eq. 3 We will consider the class of parametrized policies with parameters 0 E O Rd, with the joint policy then defined as To. 0 E θ x x Additionally, we will focus on the computational complexity only, by assuming access to the exact gradient. The study of statistical complexity surpasses the scope of the current work. We define the (independent) Policy Gradient Ascent (PGA) update as:
gh+1 arg max Soo (Toz) + (oo, 0,E0,
0,
1
10, 1-1 IT, 10t + o2V (6)
2n
where ITe, (.) denotes Euclidean projection onto θ and equivalence holds by the convexity of O; The classes of policies that allow for this condition to be true will be discussed shortly.
In general the overall proof is built of three main steps, shared with the theory of Potential Markov Games [Leonardos et al., 2022]: (i) prove the existence well behaved stationary points; (ii) prove that performing independent policy gradient is equivalent to perform joint policy gradient; (iii) prove that the (joint) PGA update converges to the stationary points via single-agent like analysis. order to derive the subsequent convergence proof, we will make the following assumptions:
Assumption B.1. Define the quantity A(0) := d then:
(i). X()) forms bijection between θ and X()), where @ and X(θ) are closed and convex.
(ii). The Jacobian matrix Va)(O) is Lipschitz continuous in e.
(iii). Denote 9(-) ;= (-) as the inverse mapping of X(-). Then there exists to S.t. (l9(A))
g(X) & foll> À XII for some norm and for all X, X' E X(0).
Assumption B.2. There exists L > such that the gradient VoLco (TT) is L-Lipschitz.
Assumption B.3. The agents have access to gradient oracle (-) that returns Vo, (To for any deployed joint policy Zg.
On the Validity of Assumption B.I. be well-behaved with respect to even if non-convex in general, and will allow for rather strong result. Yet. the assumptions are known to be true for directly parametrized policies over the whole support of the distribution d' [Zhang et al. 2220). and as a result they implicitly require agents to employ policies conditioned over the full state-space S. Fortunately enough, they also guarantee θ to be convex.
This set of assumptions enforces the objective Go (TT) to
Lemma B.4 (() Global optimality of stationary policies (Zhang et al. 2020 Suppose Assumption B. holds, and JF is a concave, and continuous function defined in an open neighborhood containing X(O). Let 0* be a first-order stationary point of problem (1. i.e.
Jul E eOF \))),, S.I. (u"" 0*) 0 for v
Then 0* is globally optimal solution of problem
This result characterizes the optimality of stationary points for Eq. T.. Furthermore, we know from Leonardos et al. 2202) that stationary points of the objective are Nash Equilibria.
Lemma B.5 (ii) Projection Operator [Leonardos et al. 2022). ). Let 0 == (f..... ..., Ox) be the param-
eter profile for all agents and use the update of Eq. (6) over a non-disjoint infinite-triae trials objective.
Then, it holds that
10 + +n (Tx = (all) (0) + o.0 ie[N]
17

---

This result will only be used for the sake of the convergence analysis, since it allows to analyze independent updates as joint updates over single objective. The following Theorem is the formal counterpart of Fact and it is direct adaptation to the multi-agent case of the single-agent proof by /Zhang et al. [022]] by exploiting the previous result.
Theorem 6.6 ((ii)) Convergence rate of independent PGA stationary points (Formal Fact ) Let
Assumptions B.I (./andd B.2 hold. Denote Dx =- ma | as defined in Assumption B. ii).
Then the independent policy gradient update (6) with 1j = 1/L satisfies for all l with respect to stationary (joint) policy now the following
4LL k+1
Go So (TO &
Proof. First, the Lipschitz continuity in Assumption B.2 indicates that
(Aa() (A(0")) - (VoCc - Consequently, for any 9 θ we have the ascent property:
8- <
2110 /
L
1
(=()))) (o()())) (VoCoeA((55) , 8 8h> [ 0² Co (>(0) 0.10 - gh (8)
The optimality condition in the policy update rule (6) coupled with the result of Lemma B.5 allows us to follow the same rational as ZZang et al. [2020] We will report their proof structure after this step for completeness.
L 10h+1 0²p12
(z((((0+))) > (x())))) + (VoGs g++1 1ett-00
1 -hh
I
max So0 (A(())) + (VoCGo(A(0")), 8h) 8 8h12
HEB
2
max So (1(0)) L10 0h1
HEB
max (\Oo) - L110- - 1² 0. = =((a((0*) + (1- a)) oe[0.1]
(9)
where step (a) follows from 8 and step (b) uses the convexity of A(0). Then, by the concavity of Soo and the fact that the composition À Ao 9 id due to Assumption B.T B.I have that:
Sa. (A(O.)) Co. (a) + (1 a))()") > a(x()((")) + (1 {)oo0))(0)).
Moreover, due to Assumption B. (iii) we have that:
|10a
2¹122 lla(a>(0*) (1 (1--))((01) 9(>(85))12
(10)
< a26)1((0)) - )(
< aZ6zDz
From which we get
(cc
< min
- -Go((()))) + L100 - 0/ = s(ar(0*) + (1 a))
aE|0,1]
-xx( min (1 - -G( +a² LZLEDD oe(0.1]
(11)
We define A(To) X0), then ag (x(A(T (o 3
which is the minimizer of the RHS
21
of (1T) as long as it satisfies on & 1. Now, we claim the following: If oz 2 1 then 0x+1 < 1. Further, if an < 1 then 0g+1 & on- The two claims together mean that (ax) & is decreasing and all og are in [0, 1) except perhaps 0g-
To prove the first of the two claims, assume ag > 1. This implies that Soo (A(Ta))) (A((T())) LL,3D. Hence, choosing in [II. we get
(A(00)))) (x(0)) < LEDD
18

---

which implies that a+++ < 1/2 < 1. To prove the second claim, we plug ag into 11 to get
(1- (xx()(())) (1-
- Goo (A(HH)) (A0(()())) (z(
- (x(((()))) &
4LL3D3
which shows that 0r++1 & Or as required.
Now, by our preceding discussion, for & = 1, the previous recursion holds. Using the definition of ag, we rewrite this in the equivalent form
at++1
(1
0kk ak 2
2
By rearranging the preceding expressions and algebraic manipulations, we obtain
+
OR+1
2
1
For simplicity assume that 0rg < 1 also holds. Then, as an + k, and consequenlty
- - (x(00)
4LL3D3
(A(())))) - Soo & 1+ (A (2(00))
k &
k
ALE3DR
similar analysis holds when ao > 1. Combining these two gives that Soo (A(TT)) - Soo (A(**)) <
4L D& k+1
no matter the value of ou, which proves the result.
B.2
The Use of Markovian and Non-Markovian Policies in cMGs with Finite-Trials Formulations.
The following result describes how in eMGs, as for cMDPs, -on-Marko policies are the right policy class to employ to guarantee well-behaved results.
Lemma B.1 (Sufficiency of Disjoint Non-Markv Policies). For every cMG M there exist a joint policy x (m* )eN. with x * E A.. being a deterministic Von-Markovvin policy, that a Nash Equilibrium for non-Disjoint single-trial objectives, for K = 1.
Proof. The proof builds over a straight reduction. We build from the original MG M a temporally extended Markov Game M (V, S, A. r, μr, T). A state š is defined for each history that can be induced, i.e., & E S <>> s S We keep the other objects equivalent, where for the extended transition model we solely consider the last state in the history to define the conditional probability to the next history. We introduce a common reward function across all the agents : S - R such that r(5) = (d(3)) for joint objectives and r()) = (1/N) Σxe[N] H (d)())) for mixture objectives, for all the historics of length T and otherwise. We now know that according to Leonardos et al. [Theorem 3. 2022 there exists deterministic Markovian policy म = (f*) iex, E A that is Nash Equilibrium for M. Since corresponds the set of histories of the original game, 7* maps to non-Markovian policy in it. Finally, it is straightforward notice that the NE of #* for M implies the NE of #* for the original cMG M.
The previous result implicitly asks for policies conditioned over the joint state space, happened for infinite-trials objectives as well. Interestingly, finite-trials objectives allow for a further characteriza- tion of how an optimal Markovian policy would behave when conditioned on the per-agent states only:
Lemma B.7 (Behavior of Optimal Markovian Decentralized Policies). Lei T.M = (TTius E A KEENI
an optimal deterministic non-Markovian centralized policy and nM ( 35')sENAn) the optimal Markovian centralized policy, namely RM- arg max a -=(aa=d"")))))) )etx)
(I(T). For a fixed sequence 8-1), the variance of the event of the optimal Markovian decentralized
s, St ending in state
policy TM = ( E A >e<[N] taking a* = TTMr(-(st) = (-s,),, in 8; at step is given by Var B( (TTM((* (ss, t)]]
Var
[ IE [T(TMM(a" $ s)]]]
Var a8 88(-0_))~9)
E (( [s,, ss., t))]
19

---

where sis E St is any sequence of length t such that the final state is s, i.e., sGB == (s:-1 JBs and ((x) a Bernoulli with parameter
Unsurprisingly, this Lemma shows that whenever the optimal Non-Markovian strategy for requires to adapt decision a joint state 8 according to the history that led it, an optimal Markovian policy for the same objective must necessarily be stochastic policy, additionally, whenever the optimal Markovian policy conditioned over per-agent states only will need to stochastic whenever the optimal Markovian strategy conditioned on the full states randomizes its decision based on the joint state s.
Proof. Let consider the random variable A, P. denoting the event "the agent takes action ot E A,". Through the law of total variance Bertsekas and Tsitsiklis [2002] we can write the variance of A given S and > 0 as
Var A|s, t
= IE |A2 8,
E [[ ef = B[A 8,
E
([
E Var [A|s, 1, s
+ B [[[[ss 1,
E [A|s,
E Var [A|s s, t, s)
E [8A]ss
s]
E [A|s,t,
8
E Var [|| 8, 4, 8
+ War [|ss
(12)
Now let the conditioning event s be distributed as s ~ Thx so that the condition 8, t, becomes 8 Q where s @ 8 (so. ao: ,1
St, and let the variable be distributed according to PP that maximizes the objective given the conditioning. Hence, we have that the variable A on the left hand side of (12) distributed as a Bernoulli B( (1. (a*1s t)). and the variable A on the right hand
side of (33) is distributed as Bernoulli ((TNM(a* (a* + s)). Thus, we obtain
Var [ TM (a |s, [))]
E -Ba-p.
Var [B(
s ++s] Var Bsspp, B.M
[B[ (s))))
(13)
We know from Lemma B.1 that the policy TNM is deterministic, so that Var [N(TMM (a" [s s)) = for every $ s. We then repeat the same steps in order compare the different Markovian policies:
Var (A|e, 11 () =
[
Var [[AAss
Repeating the same considerations as before we get that we can use [1) to get:
Var [B(TM(a* (s,, [s)] [)]]=
E #00' :)>p."
War
t))] + E [B(FM(a" Is s_., t))]
Var E (((((MN(("(sSSS) s@arp
Var
E [B(" (1,))
PM
C Details on the Empirical Corroboration.
All the experiments were performed over an Apple M2 chip (8-core CPU, 8-core GPU, 16-core Neural Engine) with 8 GB unified memory with a maximum time of execution of 24 hours.
The main empirical proof of concept was based two environments. First, Env. (i), the so called secret room environment Liu et al. [202T) In this environment, two agents operate within two rooms of 10 10 discrete grid. There is one switch each room, one in position (1, 9) (corner of first room), another in position (9, 1) (corner of second room). The rooms are separated by a door and agents start the same room deterministically at positions (1, and (2, 2) respectively. The door will open only when one of the switches is occupied, which means that the (Manhattan) distance between one of the agents and the switch is less than 1.5. The full state vector contains x,, locations of the two agents and binary variables to indicate if doors are open but per-agent policies
Environments.
20

---

conditioned on their respective states only and the state of the door. For Sparse- Sparse-Rewards Tasks, the goal was to be deterministically the worst case, namely (9.9) and to provide positive reward to both the agents of 100 when reached, which means again that the (Manhattan) distance between one of the agents and the switch is less than 1.5, reward of 0 otherwise. The second environment, Env. (ii), was the MaMuJoCo reacher environment [Png et al. [2021). In this environment, two agents operate the two linked joints and each space dimension is discretized over 10 bins. Per-agent policies were conditioned on their respective joint angles only. For Rewards Tasks, the goal was set to be randomly at the worst case, namely on position 0=0.2 +.211) on the boundary of the reachable area. Reaching the goal mean to have tip position (not observable by the agents and not discretized) at a distance less that 0.05 and provides a positive reward to both the agents of when reached, reward of 0 otherwise.
Class of Policies. In Env. (i), the policy was parametrized by a dense (64, 64) Neural Network that takes as input the per-agent state features and outputs action vector probabilities through last soft-max layer. In Env. (ii), the policy was represented by a Gaussian distribution with diagonal covariance matrix. It takes input the environment state features and outputs action vector. The mean is state-dependent and is the downstream output of a a dense (64, 64) Neural Network. The standard deviation is state-independent, represented by a separated trainable vector and initialized to -0.5. The weights are initialized via Xavier Initialization.
Trust Region Pure Exploration (TRPE). As outlined in the pseudocode of Algorithm T in each epoch dataset of N trajectories is gathered for a given exploration horizon T,, leading to the reported number of samples. Throughout the experiment the number of epochs e were equal to e 10k, the number of trajectories N = 10, the KL threshold = 6, the maximum number of off-policy iterations set RofLiter = 20, the learning rate was set to 77 10-5 and the number of seeds set equal to 4 due to the inherent low stochasticity of the environment.
Multi-Agent TRPO (MA-TRPO). We follow the same notation in Duan al. 2016 Agents
have independent critics (64, 64) Dense networks and in each epoch a dataset of N trajectories gathered for given exploration horizon T for each agent, leading to the reported number of
samples. Throughout the experiment the number of epochs were set equal to = 100, the number of trajectories building the batch size N 20, the KL threshold
10 4, the maximum number of 20, the discount was set to 0.99.
off-policy iterations set to Noffiter
The Repository is made available at the following Repository.
21

---

Mixture
Joint
Disjoint
Random Initialization
53.0
25.7
1/5
F20
Samplec
Gamples
Samsles
Samzles
(a) TRPE Joint Entropy
(b) TRPE Mixture Entropy (c) TRPE Entropy Agent (d) TRPE Entropy Agent (Env. (i), = 50).
(Env. (i), 7 50).
(Env. (i), 50).
(Env. (i), 50).
(e) TRPE Joint Entropy (Env. (i). 7' 100).
(I) TRPE Mixture Entropy (g) TRPE Entropy Agent (h) TRPE Entropy Agent (Env. (i) 100). (Env. (i). T 100).
(Env. (i), T' 100).
33
Sampl
Samples
Samsles
Samples
()) TRPE Joint Entropy (Env. (i), 150).
(i) TRPE Mixture Entropy (Env. (i), 150).
TRPE Entropy Agent (Env. (i), = 150).
TRPE Entropy Agent (Env. (i), T = 150).
(m) TRPE Joint Entropy (n) TRPE Mixture Entropy (o) TRPE Entropy Agent (p) TRPE Entropy Agent (Env. (ii), T 100).
(Env. (ii). T 100). (Env. (ii), T 100). (Env. (ii). T 100).
Figure 4: Full Visualization of Reported Experiments. Experiments with longer horizons highlight how the easier the task, the less crucial the distinction between the objectives is.
Disjoint
Inirialization
1,00
50.0
Samppie
(a) Entropy of Agent Policy in TRPE Training
(b) Entropy of Agent Policy in TRPE Training (i). T' - 50).
(c) Entropy of Agent I Policy TRPE Training (ii), T 100).
(d) Entropy of Agent 2 Policy TRPE Training (di). T - 100).
(i), T - 50).
Figure 5: Policiy Entropy Insights for TRPO Pretraining Env (i) and Env (ii) Lower Entropic Policies with Disjoint Objectives might justify the difference in pre-training performance even if the performances in training are similar.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Both the theoretical and the empirical claims are explicitly covered throughout the paper:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The authors included an explicit section covering the limitations of the pro- posed approach, made the assumptions underlying the models explicit and clearly stated the aim of the empirical corroboration in providing evidences of the nature of the new problem rather than confirming SOTA performances of the proposed algorithm.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions are clearly stated, and the proofs are exaustively reported in the Appendix, with references when needed.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the information needed for reproducibility has been provided in the Appendix and the repository the code has been provided as well.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
24

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
The link can be found in the appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. htcp//blcc/gudeeeeeeeeeeieeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The information can be found in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: the results are accompanied by confidence intervals.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
25

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The Appendix contains all the required information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm the paper conform with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer:[NA)
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
28

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy hate:p///eerrippc.cc///ofeeerers for what should or should not be described.
29


Reviews:
[{"review_id": "pL5Qo2Kboh", "reviewer": "Reviewer_NmC9", "summary": "This paper considers the problem of unsupervised learning in multi-agent environments with centralized learning where coordinated exploration is necessary. Analogously to the use of entropy maximization in single agent unsupervised RL, the authors propose to focus on maximizing a convex combination of the individual entropies i.e. the mixture entropy. The authors then propose an algorithm based of TRPO called Trust Region Pure Exploration for achieving unsupervised MARL. On MARL domains for testing coordinated exploration, the authors find their approach also optimizes for the joint entropy as well as the mixture entropy.", "questions": "- Looking at Figure 2, I am a bit confused about what the ideal objective is for agents in this setting. Is the goal to maximize for the joint entropy and the authors are proposing that the mixture entropy provides a less sparse signal, which counterintuitively leads to better optimization of this objective than direct optimization? Or rather are the authors suggesting that there is some perceived value to optimizing the mixture entropy itself independently of optimizing the joint entropy?\n- How were the specific policies in the right part of Figure 2 chosen i.e. after how many steps of training?", "limitations": "The theory is limited in that it does not explain the advantage of optimizing for the mixture entropy rather than the joint entropy in a formal manner.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- This paper considers an interesting and important topic. \n- Optimizing for the joint entropy would be the obvious solution for this formulation, so the proposal of optimizing for the mixture entropy is a bit unexpected.\n- It is nice that the authors can provide some degree of theoretical analysis in a mostly empirical research area.\n- I found the results in Figure 2 to be interesting and compelling.\n\n**Weaknesses:**\n- It is not clear to me what the theoretical value is of the mixture entropy objective rather than the joint entropy objective, the authors mention in the caption of Figure 1 that the joint entropy is sparser, implying that maybe the joint entropy is what we actually care about but it is easier to optimize for it with the mixture entropy. However, this does not seem supported based on the slow convergence in Figure 2a. \n- I think the domains considered were reasonable, but the breadth of domains is not that convincing when considering that there is some confusion about what the best objective to optimize for is theoretically. As such, there may be a requirement for a high amount of empirical evidence to really have confidence about an approach in this setting.", "was_revised": true, "final_justification": "**Update After Rebuttal:**\n- The author's addressed my confusion about the differences between maximizing for joint entropy and mixture entropy. I have raised the overall score of my review accordingly.", "rebuttal": "We thank the reviewer for their insightful comments. We are pleased they found the topic we covered to be \"interesting and important\", our solution \"unexpected\", with a \"nice\" theoretical analysis and \"interesting and compelling\" results. Moreover, we thank the reviewer for pointing out an important source of **confusion about what the intended learning objective** is and the strengths/weaknesses of joint and mixture formulations. **We believe this confusion is the reason behind the borderline score of the reviewer, and we therefore provide a separate clarification** before addressing questions in detail. We hope our replies will make the reviewer further appreciate our paper and increase their score accordingly.\n\n**Clarification on the ideal objective, joint and mixture entropy comparison**\n\nJust like in single-agent settings, the goal of unsupervised RL is to learn exploration for any possible task while interacting with the reward-free environment. If we assume the tasks are represented through state-based reward functions, the latter translates into state coverage. The state entropy is a proxy for state coverage (the argument may look convoluted, but it is common in the single-agent literature [e.g., 1, 2, 3]).\n\nOur work explores avenues to extend the state entropy objective from MDPs to Markov games, while **the ideal learning objective is still to pre-train an exploration policy for any task**.\n\nWe believe the most natural state entropy formulation in Markov games is the **joint state entropy**. However, it comes with some important drawbacks:\n   - **Estimation.** The support of the entropy grows exponentially with the number of agents $|S|^{|\\mathcal{N}|}$, so does the complexity of the entropy estimation problem [4];\n   - **Concentration.** The empirical entropy concentrates as $\\sqrt{K^{-1}}$ for $K$ trajectories (see **Th. 4.2**);\n  - **Redundancy.** When Asm. 3.1 holds and the state space $|\\mathcal{S}|$ is the same for every agent, the joint entropy may inflate state coverage as $(s,s')$ and $(s',s)$ are different joint states. \n\nIn other words, the problem of optimizing the joint entropy suffers from the *curse of dimensionality*, which is particularly relevant in practice (while their difference might not be so relevant in ideal settings, see **Fact 4.1**). \n\nAnother potential formulation is the **mixture state entropy**, which has the following properties:\n   - **Estimation.** The support of the entropy and therefore the estimation complexity do not grow with the number of agents;\n   - **Concentration.** The empirical entropy concentrates as $\\sqrt{(K|\\mathcal{N}|)^{-1}}$ for $K$ trajectories and $|\\mathcal{N}|$ agents (see **Th. 4.2**);\n   - **Redundancy.** For the mixture entropy objective, the joint states $(s,s')$ and $(s',s)$ are contributing in the same way; therefore, there is no difference in visiting one or the other. \n\n\nThe latter can be a limitation when we aim to explore all the possible *joint states*, e.g., when the reward functions of the agents will be different in the eventual tasks.\nAt least, the mixture entropy is also a lower bound to the joint entropy objective with a $\\log (|\\mathcal{N}|)$ approximation (see **Lem. 4.1**) and thus a valid proxy also in the latter case, given the favorable estimation and concentration properties.\n\n\n**Question 1**\n\nAs clarified above, the ultimate goal of unsupervised (MA)RL is to provide exploration for (MA)RL. This is why **the most important experimental metric to look at is the average return in Figure 3**, where the policy optimizing the mixture entropy fares well in comparison to others. The joint entropy, mixture entropy, and state coverage heatmaps of Figure 2 are interesting qualitative metrics, especially to understand how the unsupervised optimization process works, but they do not fully capture the ultimate goal in a vacuum.\n\n**Question 2**\n\nThe extracted policies were the ones at the end of the training process. Indeed, we used this plot to highlight a crucial point: While it is true that mixture entropy optimization appears to lead to *slower* optimization of joint entropy in Figure 2(a), this is because of pathological behaviors. Joint entropy optimization exploits redundancy (as explained above), while disjoint entropy optimization exploits simple and uncoordinated solutions, as Figures 2(c) and 3(a,b) confirm.\n\n**References**:\n\n[1] Hazan et al., Provably efficient maximum entropy exploration. ICML 2019.\n\n[2] Mutti and Restelli. An intrinsically-motivated approach for learning highly exploring and fast mixing policies. AAAI 2020.\n\n[3] Liu and Abbeel. Behavior from the void: Unsupervised active pre-training. NeurIPS 2021.\n\n[4] Beirlant et al. Nonparametric entropy estimation: An overview. 2001."}, {"review_id": "nYvXG8a28b", "reviewer": "Reviewer_TW4V", "summary": "This work explores unsupervised pretraining in multi-agent reinforcement learning via state entropy maximization. It introduces a novel mixture objective, which reduces joint state space dimensionality compared to traditional joint and disjoint objectives. The paper also provides theoretical analysis and presents a preliminary algorithm, TRPE, based on the proposed objective.", "questions": "1. In Line 118, is there a typo in the definition of $\\xi_K$? Should it be $F_{d_K}$ instead?\n\n2. There are some concerns regarding whether the proposed mixture objective is well-founded compared to the joint and disjoint objectives:\n\n  1). First, does maximizing the mixture entropy necessarily lead to a well-trained joint policy?\nFor example, consider two agents, $m_1$ and $m_2$, with identical action spaces ${a_1, a_2}$ and identical transitions—i.e., taking action $a_1$ leads to $s_1$, and $a_2$ leads to $s_2$. A policy such that $\\pi_1(\\cdot|s) = a_1$ and $\\pi_2(\\cdot|s) = a_2$ would maximize the mixture entropy. However, this joint policy $\\pi = {\\pi_1, \\pi_2}$ is clearly not a well-pretrained policy.\nDoes such a scenario occur frequently, especially in large models or with a large number of agents?\n\n  2). From the discussion around Line 175, it seems that the mixture entropy favors agents having completely different policies over the same part of the state space. Is such behavior desirable or reasonable from a learning perspective?\n\n  3). How can clustering, as mentioned around Line 179, be avoided? Would it be effective to add constraints or regularization terms to address this?\n\n3. There are also some concerns regarding the simulation and result comparisons between joint, disjoint, and mixture entropy/objectives:\n\n 1). In Line 329, the paper states that “joint and disjoint objectives fail to address mixture entropy.” This raises a question: is mixture entropy itself a reasonable metric for evaluating policy performance?\nWhile mixture entropy may serve as a useful surrogate objective during training, it is not necessarily a direct measure of policy quality. From an information-theoretic perspective, could the paper elaborate on the validity of using mixture entropy for performance evaluation?\n\n  2). In Figure 2 and the results on Page 22, since the algorithm is explicitly designed to maximize mixture entropy, it is expected to outperform others in terms of that metric. However, mixture entropy is not a widely accepted evaluation criterion. \n\nAs discussed in Line 73, the mixture objective is presented as a trade-off between tractability and performance. Compared with joint entropy, is it feasible to simplify the objective further, for example, by using the term $\\frac{1}{N} \\sum_i H(d_i^\\pi)$ as a new entropy measure?", "limitations": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "***Strengths***\n1. The paper is well written and easy to understand.\n2. It proposes a novel objective—the mixture objective—which has practical significance by reducing the dimensionality of the joint state space.\n\n\n***Weaknesses***\n1.  I have concerns about whether the proposed objective is well-founded, specifically, whether maximizing the mixture objective truly indicates that the policies are well trained (i.e., whether it ensures sufficient exploration). I outline related questions in the Questions section.\n2. The proposed algorithm, TRPE, appears to have limited applicability both theoretically and practically.\n\n***Overall*** \nMy primary concern is with Weakness 1. If this issue is addressed, I will consider increasing my score.", "was_revised": true, "final_justification": "It addresses my concern regarding the theoretical grounding of mixture entropy and its potential to yield better performance when tasks are similar in a multi-agent reinforcement learning (MARL) environment.", "rebuttal": "We thank the reviewer for their insightful feedback, and we are pleased they found the paper \"well written\" and appreciated the \"novelty\" of the proposed objective. Moreover, we thank the reviewer for raising a central point about whether mixture formulations are well-founded. **We believe this concern is behind the negative score of the reviewer and we therefore provide a separate clarification** before addressing questions and concerns in detail. We hope that our replies will make the reviewer better appreciate our paper and increase their score accordingly.\n\n**General clarification: Is the mixture entropy objective well-founded?**\n\nLet us first recall that the underlying goal of unsupervised (MA)RL is to learn a general exploration policy for future tasks. Without knowledge of the tasks we will face, there is no obvious way on how to achieve this ideal objective. In the single-agent literature [e.g., 1, 2, 3], state coverage has been proposed as a valid proxy, motivating the state entropy objective. In our paper, we propose three surrogate objectives (joint, mixture, disjoint) extending the state entropy idea from MDPs to Markov games, by highlighting relative strengths and weaknesses of the formulations (see also the recap of the comparison between joint and mixture in the *\"Clarification on the ideal objective\"* to Reviewer Nmc9).\n\nNow, on the **mixture objective** specifically. Although we do not claim that the mixture objective is the one-fits-all solution, **why is it well-founded?**\nWhenever the task reward we will face in the (supervised) learning stage is equivalent for every agent, it does not matter which agent is visiting which state, as long as most states are covered so that we understand where the reward is. We believe this is the case in relevant practical settings (see the example below), and we designed our experiments accordingly. In those cases, the policy trained with the mixture entropy is great: The agents coordinate on visiting different portions of the state space and maximize coverage.\n\nA **practical example** in which mixture entropy is desirable: We want to train a team of \"search and rescue\" agents. In a specific building (environment) the target may be found in different place (different rewards) and we want to prepare for all. Mixture entropy is a good surrogate objective in this case, as the agents will split up into different portions of the buildings to traverse in order to find the target quickly.\n\nNonetheless, there might be settings in which we aim to visit every joint state (for two agents, the reward of $r(s, s')$ is different from $r(s',s)$, i.e., the order matters). In those, the joint entropy objective is preferable, although it may be hard to estimate and optimize. At least, we know that the mixture entropy is also a lower bound to the joint entropy with a $\\log (|\\mathcal{N}|)$ approximation (see **Lem. 4.1**) and thus a valid proxy also in the latter case.\n\n\n**Question 1** \n\nWe thank the Reviewer for spotting the typo in Line 118: $d_k$ should be $d_K$.\n\n**Question 2.1** \n\nIf we understand the example correctly, we note that **the described joint policy actually maximizes the state coverage** and therefore would work well in settings where the task rewards are identical for all the agents (one of the two agents will surely get reward). This argument does not change when the number of agents increases. Instead, we agree that if the task rewards are not identical and require a specific agent to be in a specific state, then joint entropy may be better suited (although not necessarily easy to optimize).\n\n**Question 2.2** \n\nThe discussion around Line 175 describes how mixture entropy favors agents having **different state distributions**. The goal is not to have \"different policies over the same part of the state space\" but to visit different parts of the state space. We demonstrated empirically that indeed this behavior is desirable in some settings (see also the example above for a motivating example).\n\n**Question  2.3**\n\nIn many settings (see the discussion above and an example of practical applications) **clustering is exactly what one wants** to achieve.\n\n**Question 3.1**\n\nThe short answer is no, **the mixture entropy is not a good metric for unsupervised pre-training in a vacuum**, as well as joint and disjoint, which are all surrogates. The real metric we care about is the average return in Figure 3, while those of Figure 2 (joint, mixture, visitation heatmaps) are useful to understand policy behaviors and the training process. \n\n\n**Question 3.2**\n\n Let us note that **there is no widely accepted metric for unsupervised MARL**, as this is the first work addressing the problem. We propose three potential objectives, explaining their pros and cons (see also the general clarification above). \nWe are happy to include analyses of further objective functions, as the one proposed by the reviewer. The proposed variation  $\\sum_i H(d_i) /N$ would lead to each agent trying to maximize *their own* state entropy, without coordinating with others. This can be detrimental in some domains (see the practical example above).\n\n**References**:\n\n[1] Hazan et al., Provably efficient maximum entropy exploration. ICML 2019.\n\n[2] Mutti and Restelli. An intrinsically-motivated approach for learning highly exploring and fast mixing policies. AAAI 2020.\n\n[3] Liu and Abbeel. Behavior from the void: Unsupervised active pre-training. NeurIPS 2021."}, {"review_id": "7JyBtfNpCm", "reviewer": "Reviewer_xUL7", "summary": "This paper introduces a principled framework for unsupervised pre-training in multi-agent reinforcement learning (MARL) by maximizing the entropy of the state distribution—an approach well-studied in single-agent RL but still poorly understood in multi-agent contexts. The authors systematically analyze different problem formulations for unsupervised MARL—namely, maximizing the joint, disjoint, or mixture entropy of agents’ state distributions—and demonstrate that these alternatives have significant theoretical and practical differences, particularly in terms of scalability, convergence, and coordination. They propose a decentralized algorithm, Trust Region Pure Exploration (TRPE), designed to maximize state entropy in practical (finite-trial) MARL scenarios. Empirical results show that optimizing for mixture entropy strikes a favorable balance between tractability and coordination, yielding better sample efficiency and superior zero-shot transfer to sparse-reward downstream tasks, compared to joint or disjoint objectives. The work advances understanding of how to design unsupervised MARL pre-training objectives and algorithms, with mixture entropy emerging as the most effective approach for promoting coordinated exploration and efficient policy initialization for downstream multi-agent problems.", "questions": "1. You have mentioned the convex nature of the problem hinders the applicability of Bellman operators. Could you show me some more details about this point?\n2. The error bound of the mismatch between the ideal infinite-trial and practical finite-trial cases for the mixture entropy is interesting. Let me imagine a case where there are sufficiently many agents which can almost occupy the state space. In this situation, are explorations under the joint and mixture entropies align in practical effectiveness? However, according to Theorem 4.2 the joint entropy will still lead to some errors with finite trials, while the mismatch error of the mixture entropy will be vanished. Could you show me some reasons to explain this case?\n3. On line 275, what is the specification of the function $\\mathcal{L}^{i}(\\pi^{i}\\_{\\tilde{\\theta}^{i}}, \\pi\\_{\\theta^{-i}}^{-i} / \\pi_{\\theta})$? If I am not careless, I haven't found it across the whole paper.\n4. What does the post-learning indicate in Figure 3(c)?\n5. I have some question about the experimental setting of zero-shot situation. In my understanding, the goal of this task is to reach a position, though this position is randomised between four options. It seems like it still tests an algorithm's capability of exploring the state space as broadly as possible, since no algorithm has learned the knowledge of the newly set goals. As a result, it is not surprising that the ranking among the mixture, joint and disjoint in Figure 3(c) is almost the same as that in Figure 3(a) in general. Could you explain its meaningfulness, though I don't think it will affect my judgement on this paper?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n**Quality**: This paper is well structured and with strong motivations to drive the theory of unsupervised multi-agent pre-training. This paper is complete, including results of both ideal cases such as infinite-trial objectives and practical cases such as finite-trial cases. Especially, the result in Theorem 4.2 is inspirational, underscoring the strength of the proposed mixture entropy, which can be controlled by the number of agents. The theoretical conclusion has been well incorporated into TRPO to realize off-line learning (also off-policy) by the trick of importance sampling, which makes the theoretical result able to be verified. The empirical results reflect the correctness of theoretical results.\n\n**Significance**: The topic of pre-training is meaningful to multi-agent reinforcement learning. This paper has discussed the two common paradigms of exploration, adding one extra proposed paradigm. I believe the result can directly lead to potential applications and designs. On the other hand, the theoretical framework articulated in the paper is general enough, which I believe can be extended to other theoretical framings.\n\n**Clarity**: This paper is written in a logical way, with sharp connection to the existing work. Each section is under guidance of a research question, which makes the whole paper always follow a story line. Most of the experimental analysis is clear and reasonable.\n\n**Originality**: The theoretical result of this paper is original to my best experience, which directly extends the theory of convex Markov games, combined with clear research objectives, to fulfil a new theory for dealing with unsupervised multi-agent reinforcement learning. \n\n### Weaknesses\n**Clarity**: Although it can be observed that the authors have tried their best to simplify the symbols in presentation, there are still some confusing symbols. \n\n**Quality**: The experiments are too simple to a general paper in NeurIPS. However, since the main purpose of experiments is to verify the theoretical claims, this point can be waived from my own perspective.", "was_revised": true, "final_justification": "This paper has made a solid contribution in analyzing how different types of entropy maximization make various influences to the multi-agent reinforcement learning, as a pre-training scheme. Due to the limitation of the experiments to demonstrate its potential to the large-scale cases, I recommend to retain my score as 4, but I believe this paper is worth published on NeurIPS.\n\nDuring the rebuttal process, the authors have addressed my concerns in:\n1. why the convex nature can hinder the use of Bellman operator\n2. the influence of the thereoms in a scenario with many agents\n3. the clarification of experimental settings", "rebuttal": "We thank the reviewer for their thoughtful comments. We are especially pleased they found the topic \"meaningful\", the paper \"well structured\" and \"complete\", with \"strong motivations\", \"original\" and \"inspirational\" results, while the empirical analysis \"reflects the correctness of the theory\" and connection with existing work is \"sharp\". We provide extensive answers to their questions below in the hope they will further appreciate the paper.\n\n**Question 1** \n\nEven in single-agent settings, the state entropy objective can be formulated as a non-Markovian reward, as the ''*value*'' of being in a state depends on the states visited before and after that state. This is why **there is no hope of deriving a Bellman operator of any kind**. Since our problem is a generalization of the single-agent setting, a Bellman operator cannot be derived either. This argument is known in the literature (e.g., see [1] on convex MDPs and [2, 3] on non-Markovian rewards). We will provide those pointers in the text together with a clear explanation. Thank you for giving us the opportunity to clarify this point.\n\n**Question 2**\n\nWith many agents, the behavior resulting from the two objectives might become more similar, and we believe the mean-field game regime of $ \\mathcal N \\to \\infty $ could be an extremely interesting direction to study in future works. Yet, the upper bound in Thm. 4.2 would not be affected by having many agents. The support of the joint entropy grows exponentially with the number of agents $|S|^{|\\mathcal{N}|}$ and, as such, the more agents, the more states to cover. This can generate a significant mismatch between finite-trial and infinite-trial entropy.\n\n\n**Question 3** \n\nMore precisely, \n$\\mathcal{L}^i (\\tilde \\theta^i / \\theta^i) := \\mathcal{L}^i (\\pi^i\\_{\\tilde{\\theta}^i}, \\pi^{-i}\\_{ \\theta^{-i}} / \\pi_\\theta) = \\mathbb{E}\\_{d_1 \\sim p_1^{\\pi\\_\\theta} }\\rho^i\\_{\\pi^i\\_{\\tilde \\theta^i}, \\pi^{-i}\\_{ \\theta^{-i}} / \\pi^{i}\\_{ \\theta^{i}}, \\pi^{-i}\\_{ \\theta^{-i}}} \\mathcal{F} (d_1)$\nwith \n$ \\rho^i\\_{\\pi^i\\_{\\tilde \\theta^i}, \\pi^{-i}\\_{ \\theta^{-i}} / \\pi^{i}_{ \\theta^{i}}, \\pi^{-i}\\_{ \\theta^{-i}}} = p_1^{\\pi^i\\_{\\tilde \\theta^i}, \\pi^{-i}\\_{ \\theta^{-i}}}/ p_1^{\\pi^{i}\\_{ \\theta^{i}}, \\pi^{-i}\\_{ \\theta^{-i}}} = \\rho^i\\_{\\pi^i\\_{\\tilde \\theta^i} / \\pi^i\\_{ \\theta^i}}.$\n\nWe will include this definition in the manuscript. Thank you for giving us the opportunity to clarify this point as well.\n\n\n**Question 4 and 5**\n\nIn Figure 3(c), which **refers to the Reacher environment Env (ii)**, we compare the **zero-shot performance** of different pre-trained (and random) policies against the final policy obtained by running MA-TRPO with a randomly initialized policy, hence named \"post-learning\". (If the Reviewer still finds this terminology misleading, we are more than happy to change it.)  In Figures 3(a,b), which **refer to the Secret Room environment Env (i)**, we compare the effect of pre-training over **the learning dynamics** by running MA-TRPO with different pre-trained policies. To extract a plot similar to Fig. 3(c) for the latter experiment, one would take the initial performance of the curves in Fig. 3(a,b) and, for the \"post-learning\", the final performance of the \"Random initialization\" curve. What they would find is that mixture entropy outperforms all of the other zero-shot average returns, and it is similar to the post-learning performance.\n\n**References**:\n\n[1] Zhang et al. Variational Policy Gradient Method for Reinforcement Learning with General Utilities. NeurIPS 2020.\n\n[2] Takacs. Non-Markovian processes. Stochastic Process1966.\n\n[3] Whitehead and Lin. Reinforcement learning of non-Markov decision processes. Artificial Intelligence 1995."}, {"review_id": "wqmWz0RToF", "reviewer": "Reviewer_xd97", "summary": "The authors investigate unsupervised pre-training in multi-agent setting through the maximization of the entropy of the state distribution. They use convex Markov games to study three different settings: the joint objective (which simply looks at the entropy of the joint state), the disjoint objective (which considers maximizing each agent's entropy separately) and the mixture objective (which considers the entropy of a uniform mixture of the state distribution). The author argues the joint objective is intractible in practice while the disjoint doesn't optimize for coordination. Instead, the mixture objective is both tractable and encourages coordination. They show bounds relating these three objectives and particularly how the growing joint state space is problematic for the finite trial setting. \n\nThen, the authors propose Trust Region Pure Exploration (TRPE) a decentralized algorithm for maximizing general convex functions in multi-agent settings with finite trials. The algorithm maximizes the parameters of each policy separately by maximizing a surrogate function constrained by a KL with the previous policy. Empirically, they show that TRPE with a mixture objective enables better exploration in a secret room setting. Finally, in sparse-reward settings, the mixture objective allows for pretraining that enables both better zero-shot performance and transfer learning.", "questions": "- What is the difference between the convex Markov game setting and the regularized MDP setting with no rewards?\n- Was the mixture objective/decomposition previously applied (e.g. in Kolchinsky and Tracey) or is it a contribution of this work?\n- For TRPE, it is unclear to me what is the purpose of the trust region update and the surrogate function.\n- You mention \"as the convex nature of the problem hinders the applicability of Bellman operators\". Could a soft Bellman operator be used?\n- It is unclear to me what Fig. 2. (right) is illustrating? What is the clustering behavior?\n- Do you have any hypotheses for why the zero-shot learning seem to do better than post-learning with a random init?\n\nIf my questions are answered and the clarity of Sec. 5 is improved, I would be willing to increase my score from 4 -> 5.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The paper idea is well-motivated and addresses an important problem of entropy-based pre-training for multi-agent settings. It is indeed unclear what the best way to compute entropy would be and the paper analyzes/compares 3 relevant possibilities.\n- The authors provide relevant theoretical results for their analysis and describe their shortcomings.\n- The mixture objective has a compelling interpretation as maximizing individual entropy + KL with other policies. The theoretical advantages are also clear given Thm. 4.2 where the bound relies on $|\\tilde{S}|$ instead of the joint state.\n\n**Weaknesses**\n- Some parts of the paper were less clear, particularly TRPE and the motivations behind its design.\n- The work could benefit from further discussion of the connection with regularized MDPs (see question).\n- Related work lacks detail contrasting contributions.\n- Some typos/writing issues, for example:\n  - \"which we let discrete and finite with size\" -> which we assume to be discrete and finite in size\n  - \"mixture objectives enforce a clustering behavior (Fig. 2e) and result in a better efficient exploration\". Should be Fig. 2c\n  - \"leaded to faster learning\" -> lead", "was_revised": true, "final_justification": "The paper is well-motivated and proposes a novel approach with interesting theoretical and experimental results. My concerns regarding some details and the clarity of certain sections have been largely addressed. I have thus raised my score to \"Accept\".", "rebuttal": "We thank the reviewer for their detailed comments. We are glad they found the idea of the paper \"well-motivated\" and \"addressing an important problem\", while providing \"relevant\" theory and a \"compelling interpretation\" for the mixture objective. **We will follow the reviewer's suggestions to improve the clarity of Section 5, including the motivation behind the trust-region in TRPE, which we discuss below together with all of the other raised points**. We hope our replies will make them appreciate our work even more and raise their score accordingly.\n\n**Question 1** (difference between regularized MDPs and convex Markov games)\n\n**In the Regularized MDP, the regularization is typically a function of the policy [1] and not of the state distribution as in convex Markov games**. The latter is much harder to tackle and does not allow for soft Bellman operators (see answer to Question 4 below). Moreover, the regularized MDP is typically studied in single-agent settings.\n\n\n**Question 2** (is the mixture objective novel?)\n\nKolchinsky and Tracey studied the theoretical properties of the entropy of (general) mixture distributions and how to estimate it in general settings. As far as we know, **this work is the first considering a mixture of state distributions for unsupervised pre-training in (MA)RL**.\n\n**Question 3** (why using a trust-region?)\n\nIn our setting, **a small change into the policy parameters of each agent may drastically change the value of the objective function**, i.e., the optimization landscape is often brittle. The use of the trust region, like in TRPE, allows for accounting for this effect (previous works have connected the trust region with the natural gradient [2]). While the TRPE algorithm is new, the benefits of trust-region methods in multi-agent settings have been extensively demonstrated in previous works [3]. We will make those arguments explicit in the text of Section 5.\n\n\n**Question 4** (soft Bellman operators)\n\nEven in single-agent settings, the state entropy objective can be formulated as a non-Markovian reward, as the ''value'' of being in a state depends on the states visited before and after that state. This is why **there is no hope of deriving a Bellman operator of any kind**. Since our problem is a generalization of the single-agent setting, a Bellman operator cannot be derived either. This argument is known in the literature (e.g., see [4] on convex MDPs and [5, 6] on non-Markovian rewards). Thank you for giving us the opportunity to clarify this point.\n\n**Question 5** (Figure 2 (right))\n\n**Fig. 2 (right) provides heatmaps to visualize the empirical state distributions of the two agents in the secret room Env. (i)**. Then, the clustering behavior in this context consists of the two agents focusing on disjoint portions of the state space and therefore overall exploration of the whole space.\n\n**Questions 6** (why post-learning is not better)\n\nFigure 3(c) refers to a hard exploration task with worst-case goals over the boundaries of the area reachable by the MaMujoco Reacher arm. **Random initialization may result in joint policies that never visit the goal state, and therefore, there is no learning signal at all**. The pre-trained policy is instead visiting the goal often, even without further training.\n\n**References**:\n\n[1] Geist et al. A Theory of Regularized Markov Decision Processes. ICML 2019.\n\n[2] Pajarinen et al. Compatible natural gradient policy search. Machine Learning 2019.\n\n[3] Yu et al. The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games. NeurIPS 2022.\n\n[4] Zhang et al. Variational Policy Gradient Method for Reinforcement Learning with General Utilities. NeurIPS 2020.\n\n[5] Takacs. Non-Markovian processes. Stochastic Process 1966.\n\n[6] Whitehead and Lin. Reinforcement learning of non-Markov decision processes. Artificial Intelligence 1995."}]

Author rebuttal:

Meta-review: This paper explores unsupervised pre-training in multi-agent reinforcement learning by adapting the single-agent method of maximizing state distribution entropy. The authors analyze various problem formulations, highlighting theoretical and practical challenges. They then introduce a scalable, decentralized algorithm and show through experiments that optimizing for mixture entropy provides the best trade-off between tractability and performance for downstream tasks.

This was a strong set of reviews. The reviewers unanimously praised the paper's core idea, recognizing the problem as important and the proposed solution as novel and well-motivated. The theoretical analysis was a particular highlight, with multiple reviewers pointing to the theorems as compelling evidence for the mixture objective's advantages in balancing tractability and encouraging coordinated exploration.

Despite the positive reception, the reviewers shared a key initial concern regarding the fundamental justification for the mixture entropy objective. One point, raised by two reviewers, was whether mixture entropy is simply a computationally convenient proxy for the more intuitive joint entropy, or if it is a valuable objective in its own right. They questioned if maximizing it would truly lead to effective exploration or if it could produce undesirable behaviors. Other minor critiques included a desire for more clarity and the view that the experiments, while sufficient to validate the theory, were somewhat simple for a top-tier publication.

The authors' rebuttal was effective. They successfully addressed the main point of confusion by clarifying the theoretical grounding and distinct value of the mixture entropy objective compared to the joint entropy. The authors also clarified specific technical questions and experimental details. In the end, all reviewers concluded that the paper's strengths outweighed any initial weaknesses, leading to a consensus for acceptance.
Decision: Accept (poster)