Towards Principled Unsupervised Multi-Agent Reinforcement Learning

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.

Question 1 (difference between regularized MDPs and convex Markov games)

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.

Question 2 (is the mixture objective novel?)

Kolchinsky 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.

Question 3 (why using a trust-region?)

In 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.

Question 4 (soft Bellman operators)

Even 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.

Question 5 (Figure 2 (right))

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.

Questions 6 (why post-learning is not better)

Figure 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.

References:

[1] Geist et al. A Theory of Regularized Markov Decision Processes. ICML 2019.

[2] Pajarinen et al. Compatible natural gradient policy search. Machine Learning 2019.

[3] Yu et al. The Surprising Effectiveness of PPO in Cooperative, Multi-Agent Games. NeurIPS 2022.

[4] Zhang et al. Variational Policy Gradient Method for Reinforcement Learning with General Utilities. NeurIPS 2020.

[5] Takacs. Non-Markovian processes. Stochastic Process 1966.

[6] Whitehead and Lin. Reinforcement learning of non-Markov decision processes. Artificial Intelligence 1995.

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.

Question 1

Even 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.

Question 2

With 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.

Question 3

More precisely, $\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)$ with $\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}}.$

We will include this definition in the manuscript. Thank you for giving us the opportunity to clarify this point as well.

Question 4 and 5

In 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.

References:

[1] Zhang et al. Variational Policy Gradient Method for Reinforcement Learning with General Utilities. NeurIPS 2020.

[2] Takacs. Non-Markovian processes. Stochastic Process1966.

[3] Whitehead and Lin. Reinforcement learning of non-Markov decision processes. Artificial Intelligence 1995.

Thank you for your dedicated rebuttal. My concerns have been addressed.

I suggest you may add clarifications in Question 1 (the applicability of Bellman operator), Question 3 (the notation) and Question 4 (the definition of post-learning) in the main paper.

Due to that I believe the existing score can well weigh the contribution of this paper (e.g. lacking large-scale experiments), I would retain the score, but strongly recommend to get this paper accepted.

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.

General clarification: Is the mixture entropy objective well-founded?

Let 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).

Now, 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? Whenever 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.

A 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.

Nonetheless, 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.

Question 1

We thank the Reviewer for spotting the typo in Line 118: $d_k$ should be $d_K$.

Question 2.1

If 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).

Question 2.2

The 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).

Question 2.3

In many settings (see the discussion above and an example of practical applications) clustering is exactly what one wants to achieve.

Question 3.1

The 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.

Question 3.2

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). We 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).

References:

[1] Hazan et al., Provably efficient maximum entropy exploration. ICML 2019.

[2] Mutti and Restelli. An intrinsically-motivated approach for learning highly exploring and fast mixing policies. AAAI 2020.

[3] Liu and Abbeel. Behavior from the void: Unsupervised active pre-training. NeurIPS 2021.

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.

Clarification on the ideal objective, joint and mixture entropy comparison

Just 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]).

Our 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.

We believe the most natural state entropy formulation in Markov games is the joint state entropy. However, it comes with some important drawbacks:

• 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];
• Concentration. The empirical entropy concentrates as $\sqrt{K^{-1}}$ for $K$ trajectories (see Th. 4.2);
• 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.

In 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).

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 $\sqrt{(K|\mathcal{N}|)^{-1}}$ for $K$ trajectories and $|\mathcal{N}|$ agents (see Th. 4.2);
• 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.

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. At 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.

Question 1

As 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.

Question 2

The 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.

References:

[1] Hazan et al., Provably efficient maximum entropy exploration. ICML 2019.

[2] Mutti and Restelli. An intrinsically-motivated approach for learning highly exploring and fast mixing policies. AAAI 2020.

[3] Liu and Abbeel. Behavior from the void: Unsupervised active pre-training. NeurIPS 2021.

[4] Beirlant et al. Nonparametric entropy estimation: An overview. 2001.