Tree Search for Simultaneous Move Games via Equilibrium Approximation

1. The paper's writing and formatting are poor, with some images, tables, and equations arranged in a cluttered, two-column layout (e.g., Figures 1 and 4, Tables 1 and 2, and Equations 1-5), making the document look disorganized. Additionally, citation formatting is incorrect; in the ICLR template, \citep should be used instead of \citet when authors or publications are not part of the sentence.
2. The paper lacks theoretical support. While it spends much space arguing that CCE is superior to min-max, it does not demonstrate that the combination of EXP3-IX and depth-limited d-MCTS can ultimately converge to CCE.
3. The terminology is somewhat unprofessional. Typically, simultaneous-move games are not categorized as partially observable games, as standard Markov or stochastic game definitions allow for simultaneous moves. If the authors intend to contrast with traditional perfect information games, they should instead use “imperfect information games”.
4. The paper makes several unsupported claims. For example, in line 35, the assertion that "successes in partially observable settings have been more muted" overlooks numerous well-known works in this setting (e.g., DeepStack, AlphaStar, OpenAI Five, DeepNash). Similarly, line 46 claims that "playing according to a CCE gives you performance guarantees against any opponent in competitive tasks," which is inaccurate—CCE does not ensure performance guarantees except in 2P0S games, where it aligns with Nash equilibrium.

The technical contribution is not sound.

The paper has several weaknesses which prevent me from recommending it for acceptance.

I think the actual description of the algorithm is unclear. At inference time, what is the tree-search algorithm? Appendix A.5 suggests that there will be a game tree and an MCTS-like algorithm (as does the title of the paper), but Section 4 suggests that the method is no-regret algorithms using 0-step lookahead (just q-values)?

The experiments performed also don't test the core hypothesis of the paper -- that the algorithm computes a CCE. The experimental results are also fishy, and hyperparameters are not given for the baselines. Perhaps my biggest issue with the paper is that in the experiments, CFR does not perform well on "Goofspiel-6", but one would expect CFR to be able to compute a close Nash equilibrium in the game. The experimental code for CFR does not seem to be in the code linked in the appendix.

The paper's driving motivation is convergence to CCE. However, the experiments measure head-to-head winrates. Head-to-head winrates already seem less preferable than head-to-head EV (since agent 1 may have +EV against agent 2 despite having a lower winrate). However, to measure convergence to CCE in small, 2P0S games, one could simply compute exploitability.

The paper should cite other methods that use neural nets and tree search to compute a CCE.

• For example, ReBeL 0 and Deepstack/Student of Games 1 use CFR, where the players' marginal time-averaged strategies form a N.E. in 2P0S games, because their joint time-averaged strategy is a CCE 2.
• Research in Diplomacy, a simultaneous-move multiplayer game, also uses neural nets, lookahead, and no-regret dynamics: [3], [4].
• There is also a rich line of research into q-learning for equilibria in stochastic games. Although mostly in the 2-player setting, the approach is similar to this paper and should be cited. The research starts with Littman's seminal minimax q-learning, and the related works section of this paper ([5]) gives a good overview of modern developments.

I believe this existing research contradicts the statement in the abstract: "Neural network supported tree-search has shown strong results in a variety of perfect information multi-agent tasks. However, the performance of these methods on partial information games has generally been below competing approaches."

This approach works well for zero-sum, perfect information games like chess or Go, but when we move into the realm of partial information games, the min-max paradigm becomes inappropriate.

I would say the min-max paradigm is still valid in partial information games. The difference is between 2P0S and general-sum/multiplayer. Also, the paper should mention somewhere that the "productized" policies (each player playing their own marginal, time-averaged policies) of a CCE are Nash equilibria in the 2P0S setting.

The limitation for equilibrium approximation algorithms is that they are not easily applied to tasks with larger state and action spaces. The majority of testing regarding such algorithms have been on small tasks.

I don't think this is true.

Using the regret bound provided by Neu (2015), it becomes clear that 800 time steps is insufficient for this method. At 800 time steps, the theoretically guarantees provided by EXP3-IX are very poor: we have not yet found the best action.

Why do we refer to a "best action"? Why do we expect that action probabilities stabilize? The guarantee is convergence to a CCE, not a "best action" (which isn't well-defined), no? A CCE is a distribution over joint actions.

[3]: Learning to Play No-Press Diplomacy with Best Response Policy Iteration [4]: https://arxiv.org/abs/2210.05492 [5]: https://arxiv.org/abs/2306.05700

• It is a little difficult to follow the first part of section 4.1
  • e.g. the writing suggests the value network only takes joint actions as inputs, I assume it also takes the state? The equations 1 through 5 could also use a bit more explanation.
• I am not sure about the argument made that the PSRO methods are not designed to work in large environments - e.g. Towards Unifying Behavioural and Response Diversity for Open-ended Learning in Zero-Sum games (Liu et al. 2021) applied a diversity aware PSRO to Google Research Football and subsequent PSRO papers have done the same
• My main concern with the paper is that whilst the body of the paper provides a good high-level overview of the framework, some potentially key details for both understanding (e.g. The explanation of EXP3-IX usage is limited and it is difficult to follow how one would implement it) and re-implementation are buried in the appendix / the provided code.