Summary
This paper asks and answers the question: "In what games does self-play (with regret-minimizing algorithms) in multiplayer imperfect-information games perform well?"
The motivation behind the question is that such algorithms, such as multiplayer versions of CFR (which has theoretic guarantees in 2-player zero-sum games), have empirically performed well in some multiplayer games, despite no previous theory guaranteeing that they will do so. (The salient example is no-limit Texas Hold'em, in the work "Superhuman AI for multiplayer poker", Brown & Sandholm 2019.)
This paper answers the question primarily by looking at the concept of the coarse correlated equilibrium (CCE), since that is what the policies of the regret-minimizing players will converge to. The authors show that if games can be decomposed into a bunch of 2-player constant-sum games, called a constant-sum polymatrix (CSP) game, and the CSP game fulfills some additional properties, then we can bound the worst-case performance of a player's CCE strategy. They also show that even in games which can't be factored into polymatrix games (which is most games), we can project them into the space of CSP games, and still bound the worst-case performance of each player's CCE strategy.
They also refine the analysis further by examining worst-case performance only against other self-play strategies. Finally, they perform experiments on multiplayer Leduc poker, and show that the empirical worst-case performances are within the bounds predicted by their theory.
Strengths
- I think this is an excellent paper. The question it asks and answers is fascinating, and one that I think was begging to be examined for several years now. Therefore, I judge this paper to be a significant contribution to science.
- The results of the paper are novel and nontrivial.
- The paper is well-written. The writing is clear and understandable. The introduction explains the background and motivates the problem well.
Weaknesses
The paper mentions no-limit Texas hold'em as a motivating real-world positive example of self-play working in multiplayer games. I also suggest that the authors mention some real-world negative examples -- for example, FAIR's line of work on Diplomacy, particularly the self-play agents performing poorly against humans in "No-Press Diplomacy from Scratch", Bakhtin et al 2021 https://arxiv.org/pdf/2110.02924.pdf (the problem is the motivation of "Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning" Bakhtin et al 2022: "the resulting agent DORA does very well when playing with other copies of itself. However, DORA performs poorly in games with 6 human human-like agents.")
typo on line 336: "with ... be the set"
Questions
It's not clear to me how important the caveat in Footnote 3 on page 8 (section 6) is. So CFR does not necessarily converge to a CCE. The experiments in Section 6 use CFR. Is my interpretation correct that you take the marginal strategies of the CFR iterates, and hand-wavingly say that we can assume they are marginal strategies of (a distribution converging to)
a CCE, even though they're not?
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The authors adequately addressed the limitations.