- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies how to approximate Nash equilibria in large, sequential, two-player zero-sum games with continuous action space. As action discretization may disregards the relationships among discrete actions and ordinary policy gradients may not converge, the paper proposes Magnetic Mixture Policy Optimization that combines Gaussian mixture policies, Magnet KL regularization, self-play. It gives some guarantee under quite restrictive conditions, and evaluate the proposed method on some continuous-action games.
Critical strengths
The potential contribution is showing that this combination can produce effective mixed strategies in continuous action games with relatively few environment interactions.
Critical weaknesses
I found this draft difficult for human to read, as it uses many concepts/notions without properly defining them, and suddenly presents a pile of sentences without a coherent reasoning. This gives me impression that the writing may have relied heavily on LLMs. I personally have no objection to using LLMs to assist with writing, but I think at least one of the authors should read once the generated content from beginning to end to check the readability.
For example, the second and third paragraphs of the Introduction section.
From the summary given by AI, the draft seems to focus on games with continuous action spaces. The proposed method combines several well-established techniques, i.e., magnetic mirror descent, Gaussian mixture models, and KL regularization. Honestly, I struggle to find any genuinely novel insights or ideas beyond this combination of existing tools.
Questions for authors
See above
3 comments
I appreciate the revisions to the introduction. But I still found the results in Sections 2 and 3 difficult to verify. My main concern is that the convergence analysis covers a single Gaussian, while MMPO jointly learns a Gaussian mixture. In my view, a convergence claim for the full algorithm would require substantial additional work.
All references below are to the revised manuscript.
My main concern is the gap between the motivation for MMPO and the setting covered by its theory. The paper motivates learned Gaussian mixtures through games in which equilibrium play requires randomization over several distinct actions. Theorem 1 establishes convergence for a single Gaussian with a fixed magnet. When multiple Gaussian components are learned jointly, both their weights and their parameters change, and the theorem does not establish convergence for those coupled updates.
Section 2 assumes compact action sets (line 74), whereas the Gaussian policies in Theorem 2 have unbounded support. How are samples outside the action set handled? If they are clipped to the boundary, please justify why the stated exploitability bound still holds.
Section 3.3 uses an upper bound on the mixture KL divergence as a surrogate regularizer (lines 206–209). This bound can be loose. Could the authors clarify how this surrogate gap affects the policy updates?
I found the theoretical results in Sections 2 and 3 difficult to verify because several definitions are implicit or appear only after the notation is used. For example, Theorem 1 states that the iterates converge to the unique solution of (line 170). Even after chasing down the proof, I couldn't find the precise inequality. It would also help to state both explicitly before the theorem, specify the coordinates in which and are defined, and explain the roles of , , and when they first appear. This is a minor presentation issue, but it significantly affects readability.
Thank you for the ongoing discussion and for pointing out problems with the presentation of the paper!
Mixture of Gaussians theory
Theorems 1-3 use a parametrization of strategy as a single Gaussian, and we are explicit about this in the paper. The goal of those theorems is not to say how the whole MMPO converges. They only serve as supporting arguments for using KL regularization for the Gaussian heads (similarly, Section 3.1 argues the same for the categorical head).
We would like to be clear that we are not claiming that MMPO is guaranteed to converge to a Nash equilibrium. To the best of our knowledge, there is no scalable policy-gradient algorithm for sequential continuous action games that models mixed actions and provably converges to Nash equilibrium. MMPO serves as a heuristic algorithm for these types of problems. While it may be possible to define a restricted class of games in which MMPO would provably converge, our approach was to empirically demonstrate that MMPO finds strong strategies across domains where gradient-based algorithms are unlikely to provide guarantees, such as sequential games or games with continuous support.
Compact action sets
Thank you for pointing this out. This is an oversight on our side, because in Theorems 2 and 3, we implicitly assumed that even if the action sets are defined over compact sets, the utility function can be extended beyond this legal action set with the same bounded second derivative. We have added a note that the Gaussian mean is within the action set (line 155), Assumption 2, which explicitly states that it uses the extended utility over the whole real number set, and an explanation for this assumption (lines 189-195). We also modified the bodies of the Theorems and propositions to directly use this new assumption.
In our implementation, when an action outside of this set is sampled, we clip it to the set. With the clipping, the same proof no longer holds, because it breaks the monotonicity assumption, so it may require additional steps to find a bound for that setup. Again, the point of Theorems 1-3 is only to show the benefit of the Gaussian KL regularization, that is why we did not try to construct a proof for the clipping setting, since the Theorems already assume an idealized setting.
Theorem 1
The fact that the converges to the unique solution directly follows from the last line of the proof. By Proposition 1, there is a unique solution. By Eq. (2), . We have explicitly added this to the proof for completeness.
KL divergence estimate
We have run an experiment in which we trained the MMPO using either the true KL divergence estimator or our weighted-sum estimator. The entire experiment is in Appendix D.5. With both KL estimators, the MMPO converges to roughly the same value. We also show in that experiment how the two estimators differ during one run.
We would like to defend ourselves against the AI claims. This paper was not written by AI. We did use LLMs to polish the writing, as we acknowledged in the paper. However, all of the presentation decisions were ours, including the decision to explain why mixing between several distinct strategies is done this way. The concepts discussed in Paragraphs 2 and 3 of the introduction are standard in game theory, including the fact that optimal strategies often require mixing among several actions. Below we expand on the topics of those paragraphs. If the reviewer thinks it is appropriate to expand in the paper as well, we can also include such expansions in the camera-ready version of the paper.
Paragraph 2
Paragraph 2 aims to show that in adversarial problems, if one player always follows the same deterministic strategy, it can be exploited. Consider Rock-paper-scissors, if one player always plays Rock, then a rational opponent will always pick Paper and win every time. It is known that the optimal strategy in Rock-Paper-Scissors is to mix all 3 actions with equal probability. This paragraph argues that the same thing happens even when the actions are continuous rather than discrete.
One may argue that the Gaussian reparametrization already mixes between several actions. However, if we consider the penalty kick in football (soccer), and the action as the angle at which the ball is kicked. Let us assume that the optimal strategy for such a scenario mixes equally often between kicking the leftmost and rightmost parts of the net, without shooting in the middle. Such a strategy is impossible to model with a single Gaussian. This motivates our use of a Gaussian mixture model rather than a single Gaussian, as in PPO or SAC.
Paragraph 3
Paragraph 3 then explains that if you naively use policy-gradient algorithms, such as PPO, in discrete action games, they will not converge to the optimal strategy. For example, in Rock-paper-scissors, PPO does not converge to a uniform strategy (this is similar to the behavior we show in Figure 7 in the Appendix for continuous matching pennies). This is a problem that has been well studied in prior work. To the best of our knowledge, the only truly scalable approach that converges to these optimal strategies in discrete action games is to use KL regularization (as in algorithms such as RNaD, MMD, or NashPG). This paragraph motivates why MMPO uses the KL-divergence regularization. We further expand on this in Section 3.2, where we show that the KL divergence is indeed beneficial in the Gaussian reparametrization.
Whole method
MMPO parametrizes the strategy as a Gaussian mixture model because it has greater expressive power than a single Gaussian and allows for mixing among several, possibly vastly different, actions. MMPO has two heads: one Gaussian head predicts K means and standard deviations, while the second categorical head predicts a categorical distribution over those components. Section 3.1 explains that MMPO needs to use KL divergence in the policy-gradient loss for the categorical head, because otherwise the categorical head may end up in a Rock-Paper-Scissors scenario, where it fails to converge to an optimal mixture of the individual components. Section 3.2 shows that using the KL-divergence for the Gaussian head is beneficial, because it can guarantee its convergence in games where plain PPO would not converge, which we empirically verify in Section 4.1. Section 3.3 then only formalizes the whole policy-gradient loss of MMPO.
Known components
While we agree that our work can be viewed as a combination of known components, that does not mean it lacks valuable insights. We show that naively applying PPO to continuous action games can yield suboptimal strategies (Sections 4.1-4.3). We prove that the theoretical guarantees of KL-regularization translate from discrete action games to some classes of continuous action games when using Gaussian reparametrization. We also explain that naively extending the PPO to a mixture of Gaussians without the KL-divergence for the categorical head may result in the cyclical behavior seen in discrete action games. This means that the KL divergence for the categorical head is not merely an arbitrary choice but a principled solution. We would argue that the fact that our work uses known concepts but warns about the potential dangers of their combination and shows how to combine them well is a strength of the approach, not its weakness.