Open-Ended Learning in General-Sum Games: The Role of Diversity in Correlated Equilibrium

My main concern is the quality of the writing. I had trouble understanding the main ideas of the paper, mainly because there were many confusing definitions and notational jumps. Here are some concerns, in no particular order.

1. In 2.1, the definition of a "game" seems to be a complete-information, alternating-move sequential game. But the paper is general to incomplete-information or simultaneous-move settings as well, so I think that the definition of game should be changed to accomodate that. In fact, since the paper doesn't care about the sequentiality at all, why not just use normal-form games throughout?

2. The citation of [Farina et al 2020, Marris et al 2022] for correlated equilibrium is strange---especially the former, as the concept it discusses isn't CE. For CE I believe the correct citation is [Aumann 1974].

3. The definition of $\epsilon$-CE used here is a bit strange. Indeed, it seems to imply that the uniform-random policy is a $1/N$-CE, where $N = \min_i |\Pi_i|$ (which could be very large), and that not every $\epsilon$-CE is an $\epsilon$-CCE. Perhaps it would be better to define $\epsilon$-CE with the set of swap deviations instead of the set of internal deviations (see e.g. [Blum & Mansour 2007]). But also this doesn't seem to matter much to the rest of the paper, so I mostly disregard it.

4. In the diversity metric definitions (3) and (4):

   a. the metric seems to depend on the ordering in which the profiles are added (i.e., on which strategy is the new one). Perhaps then the diversity metric should be expressed as a two-argument function, $\text{Div}(\Pi_i, \pi_i')$, so that this dependence is clear.

   b. The definition of occupancy measure should be stated in the text.

   c. Since Nash equilibria are not generally unique, (4) is not well-defined until a specific NE is selected. This should be explicitly stated and discussed.

   d. It is unclear how the definition $\text{Div}(\cdot)$ relates to the function $f(\cdot)$ used later in the paper. In particular, it appears as if the diversity metric $\text{Div}(\cdot)$ is built to affect how new policies are introduced (i.e. to affect the best-response oracle, which is the thing picking the $pi_i'$), whereas the rest of the paper concerns the meta-solver. How are these related? This to me is a crucial point, because $f$ is used liberally in the remainder of the paper.

The experimental evaluation is also not very convincing. On the single example in which the authors do a comprehensive test against other metrics, the proposed method, which is a combination of two prior methods, performs second-worst, being outperformed by both of the prior methods individually.

A Blum & Y Mansour. "From External to Internal Regret", JMLR 2007

• It's not clear to me why we should want to "increase the sampling probability assigned to diverse policies" nor that this is well defined.
  • The diverse policies are not necessarily profitable in equilibrium.
  • If our population is diverse then this suggests we want a uniform distribution. Otherwise, the population isn't diverse, and then increasing the sampling probabilities of diverse policies would reduce return.
  • How would this claim apply to deterministic versus stochastic policies? Including purification of policy subsets?
• The contributions of this paper appear marginal, as it suggests using existing diversity measures to solve for maximum welfare coarse correlated equilibrium (MWCCE).
  • The paper frames itself as solving for CE and CCE generally but only has an evaluation for MWCCE.
  • The interesting ablation study of different diversity metrics is shown only on a single game (3-player Kuhn poker).
  • The empirical performance of "Diverse CCE" only shows a benefit over a baseline in one of the three games studied.

In its current state, this paper is not ready for publication. Most of the issues are in the writing of the paper. In my reading, I was unable to find explanations for key parts of the algorithm. There are also some minor issues: it's not intuitive to me why the definition of diversity expectation would be good, which would be fine if the experiments convincingly showed that the algorithm is good, but they don't. (Maybe the definition of diversity expectation is a good one, but the paper didn't show me that it is.)

• The algorithm is not clearly explained: I feel like this paper is missing a paragraph or a section, because Section 4 and Algorithm 1 should explicate the algorithm. However, to my reading, they do not. The paper does not explain what MS is, which is the most important part of the paper. (Without stating the specific choice of MS, Algorithm 1 seems to be equivalent to PSRO.) I infer that MS does the computation described in Section 3.3, but this does not seem to be explicitly stated anywhere! And even if I make this inference, I don't know whether it is Equation 14 (General support) or Equation 15 (Full support) which is being calculated. The paper also does not explain what DM is, although I infer that it is the diversity measure from Equation 6.

• However, this also seems undefined! Section 3.1 explains how sum of diversity expectations is calculated based on each player's diversity measure $f_{i|l,m,...q}$, which is defiend in terms of $f$. However, as far as I can see, the choice of $f$ used in the experiments was never described! (I cannot even infer the choice of $f$, since Section 2.4 describes two different diversity measures, and states that this work uses a combination of them, with the method of combination left undefined.)

• Presumably the output of DCO is supposed to be a D(C)CE, but this is never stated. It should be stated. It should also be stated and proved that the termination condition given in Algorithm 1 leads to the output being a D(C)CE.

• I don't entirely understand the sentence in Section 3.1: "Inspired by JPSRO, we use a quadratic function as the optimization objective". If my interpretation is correct, JPSRO uses the Gini impurity as an objective, which is quadratic. Here, I don't see why you would be inspired to maximize $(f^\top \sigma)^2$ -- aren't both of those vectors non-negative, so maximizing their square is equivalent to maximizing the original thing?

• It's stated in Section 3.1 (and throughout the paper) that "our objective it to increase the sampling probability assigned to diverse policies. This is achieved by maximizing the sum of each player's policy diversity expectations, thereby ensuring that the more exploratory policies play a more significant role in approximating the full game (C)CE." I don't immediately see why this objective is achieved by maximizing the sum of each player's policy diversity expectations. Maybe I am misunderstanding, but as defined, it seems that each $f_{i|l,m,...q}$ is dependent on the set of player $i$ policies, but is not dependent on their distribution over those policies. It would be helpful for the paper to explain or give intuition for why the policy diversity expectations achieve this goal.

• On that note, it would be good for the paper to include qualitative examples of things like the policy diversity expectation value for different strategy profiles, and especially for the difference in distributions over a given set of strategy profiles for D(C)CE vs. MG(C)CE.

• Results are not convincingly strong. Only in 3-Player Kuhn Poker is the novel method clearly better. 2 of the 3 experiment games are 2-player, not multi-player.

Minor:

• the first paragraph of Section 3 mentions "MGCE" but this is not defined anywhere.
• Game notation (Section 2.1) could use work. Probably should clarify in the first sentence that this describes sequential games. Policies are not defined. State transitions are not defined. In the description of meta-game, should it say that "a meta-strategy is used to denote the probability distribution over policy profiles" instead of "over policies"? And perhaps a more suitable name for "meta-strategy" would be "joint meta-strategy"?
• Notation in Section 2.2 could also be more clear. It could be specified what the summation in Inequality (1) is over. Sigma is defined in 2.1 using brackets but is used in 2.2 with parentheses. Underneath it says it can be written as $A_i \sigma$ but neither of those symbols are defined (it is not explicated anywhere that they are vectors). I would appreciate a citation for the statement that the maximum sum of social welfare under CEs is greater than or equal to that under NEs. Should it say that "The NE are located on the boundary" instead of "The NE is located on the boundary"? In the definition for NE, the symbol $\sigma(\pi_i)$ is used, and although it's clear to someone familiar with the topic what this means, it's not defined anywhere and could be confusing for some readers. In the definition for CCE, should it say "only consider deviating before" instead of "only consider deviating until"? Also, this "recommended policy" is referenced to define CCEs, but is not previously mentioned in the definition of CEs, so the reader doesn't know what a "recommended policy" is. For the definition of CCEs (inequality 2), the foralls should be clearly restated instead of implied, otherwise the definition of $i$ is not clear.
• Section 2.3 uses the term "Meta-Solver (MS)" but doesn't describe what it is or give any examples (e.g. Nash Equilibrium solver). The symbol $u^*_i$ is used but not defined anywhere.
• Section 3.2 is titled "Existence of the Equilibrium" but it seems to me to concern the uniqueness of the equilibrium and not the existence of the equilibrium.
• Section 4: "it differs from other algorithms by assigning greater sampling probabilities to more diverse policies": could this be made more precise or expanded upon? What is a "more diverse policy"? When does it assign greater sampling probability? (in the meta-solver?)
• Section 6: The sentence "In [multi-player general-sum games], players aim not only to coordinate their policies or actions within a unified join policy but also seek to maximize overall social welfare" seems wrong to me. That may be the players' goal, or it may be the algorithm designer's goal, but generally players just care about their own utility, right? Unless the setting is intended to be fully cooperative.

Nitpicks / typos:

• Abstract: "The primary in this work"
• Introduction: "frameowrk"
• Quotation marks in Section 2.1 are both in the same direction for "game of games"
• Section 2.1: "used to denoted" should be "used to denote"
• Section 2.2: it's weird that the original Aumann paper is not cited here for the definition of CE (I know it was cited earlier, in the Introduction, but should it be cited here?)
• Section 2.4: Perhaps rearrange the first sentence so it says "... the diversity of player $i$'s population $\Pi_i ...$, given the opponent's policy $\pi^l_{-i}$ is denoted by ..." to emphasize that the diversity is of a population and conditional on an opponent's policy?
• Section 3: grammar - "The sampling probability of the policy is closer to the uniform distribution, the entropy or Gini impurity is larger." Also, the "sampling probability of a policy" is referred to a few times but as far as I can tell it's not precisely defined what it means.
• Section 3: should "regular term" be "regularization term"? This would also benefit from a quick explanation of "policy exploitability (PE)"
• should "the corresponding expected return (ER)" be "the corresponding expected returns (ER)"?
• Section 5 (page 8): "the weight K of the diversity term should be smaller than ..." the fraction has a typo?
• Figure 1 x-axis should be "Iterations" not "Itertions"

Although the paper studies an interesting setting the implementation feels somewhat lacking. First, I would expect the experimental results to actually showcase and discuss the actual diversity of the found solutions but this is surprisingly not really explored. Instead the paper only focuses on the extent in which these new techniques find states of low exploitability. I find this to be a critical weakness of the paper and I would be very interested in a deeper dive that tries to explore what are the properties of the solutions found and not whether they are epsilon equilibria for small enough epsilon.

Even the current experimental implementation leaves something to be desired. For example, it is stated that the stated performance of the technique is for a choice of internal parameters which is "selected appropriate through extensive hyper-parameter tuning". Is this an apple to apple comparison with other techniques?

The theoretical analysis of the paper is not particularly deep. Finally, the paper showcases some obvious typos or undefined notations that indicate a bit of rushed implementations. Examples include: Page 3. \Pi^{O:T}_{-i} from Marris et al paper not defined. Page 4. In Equation 4 \rho is not defined. Page 8 In all figures Itertions-> Iterations.