Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper addresses approximating equilibrium strategies in adversarial team games (ATGs).  The paper claims the following contributions: (1) It is “the first method for refining strategies by subgame solving in ATGs,” which it does by generating a “blueprint strategy” using a column-generation algorithm (with a time limit).  (2) it develops the Team-maxmargin algorithm, which is motivated by the existing maxmargin algorithm.  This algorithm in experimental evaluations “reduces the gap between the values provided by the equilibrium strategy and the blueprint.”

strengths_and_weaknesses: Up-front comment so that my review can be taken in proper context: This paper is in the rather niche area of solving zero-sum games, an area that has been developed extensively over the last decade or two primarily by a handful of research groups.  While being familiar with that area, I am not immersed in it, nor have I followed the notation, terminology, and advancements extremely closely.  Typically, however, I can follow papers in this area.  But I had difficulty following the details of the paper and its high-level message.   I followed the terminology and notation well for a while as I read into the paper, but then the overwhelming number of terms, etc. caused me to begin to lose context (and hence interest).  That said, during my efforts, I noted that the paper is written cleanly and carefully, and appears to be technically sound.  The paper exhibits a high amount of technical knowledge, I just couldn’t follow it the whole paper through.  On the downside, I also failed to grasp the key technical messages of the paper (what makes it tick? What knowledge generalizes?) within the time-limits that I had (being an emergency reviewer for this paper).

With that context in mind, here is my evaluation of the contributions of the paper:

(1) Is the claim that the paper is the first to present “a method for refining strategies by subgame solving in ATGs” substantiated in the paper?  No.  I recommend that this claim be removed from the paper.  First, it would be impossible to substantiate.  Second, the contribution of the paper likely wouldn’t be reduced even if the claim was proven to be false.  Third, the claim hurts the paper in that it focuses the reader on whether it really is the first rather than the actual content of the paper.  Thus, I think the paper would be better if the claim were removed.

(2) While I found the team-maxmargin algorithm difficult to follow, the empirical results across four different zero-sum games do appear to indicate that it does reduce the gap between the values provided by the equilibrium strategy and the blue print.  I find it nice that the paper considers the four games.

Is the algorithm novel?  I believe it is.  The knowledge development is somewhat incremental in that the approach builds well upon existing work in the well-developed area.

Is the contributed knowledge important?  It depends on how much one values game playing.  It certainly is a fun topic, though one could argue that such game-playing is unlikely to lead to useful applications in the near future.  Even still, it is possible that knowledge generated in this domain could become useful outside of the niche area.  And this paper represents an impressive effort that can expand knowledge for those in the area.

questions: I'd be happy for the authors to correct anything in my review that is incorrect or denotes a misunderstanding of the paper's contributions.
limitations: Please see the previous sections
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper focuses on solving large adversarial team games, which include both cooperation and competition. They extend the subgame solving technique of solving huge two-player zero-sum games, which computes a blueprint strategy offline and refines it online. The proposed approach is based on team-belief DAG for the gadget game and column generation algorithm for refining the blueprint strategy. They empirically evaluate the proposed approach to see if the blue strategy is improved.
strengths_and_weaknesses: Existing algorithms are hard to solve large games, e.g., the performance of (column generation) CG is constrained by the requirement of memory and iterations. To overcome this challenge, this paper extends the subgame-solving technique to AGT by handling its unique property in AGT.
However, this proposed subgame-solving technique still uses CG for both the blueprint and the subgame-solving procedure. Then this proposed algorithm may still suffer the limitation of existing algorithms.

This work aims to solve large games, but games used in experiments are very small, and all of them can be solved efficiently by existing algorithms, e.g., algorithms in [20]. Even in these small games, e.g., Leduc poker games, the gap between the equilibrium value and the refinement value is still very large. If this proposed solving algorithm cannot perform well in these small games, it is hard to imply that it can perform well in larger games.

It is interesting to see the performance of the algorithms in [20] or [21] using the same time as the subgame solving algorithm

The following multiagent learning-based algorithm for TMECor that is not limited by memory should be a baseline.\
Cacciamani F, Celli A, Ciccone M, Gatti N. Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems 2021 May 3 (pp. 269-278).

Line 3 of Algorithm 1: ‘alt’ ->’all’
questions: No
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a modification of subgame refinement for adversarial team games. An abstract strategy is refined for the public states encountered in the game with additional iterations using a modification of the max-margin gadget. The empirical evaluation on multiple games that can completely fit into memory shows that most of the gap from the optimal solution can be removed by this method.
strengths_and_weaknesses: Decomposition on solving large imperfect information games in a relevant problem and this paper makes an incremental, but solid step in generality of this approach. I am not aware of any other work on subgame refining in team games, or even imperfect recall games in general. The paper is well written, reasonably easy to follow, and I did not find any serious technical mistakes.

The experiments are sufficiently thorough for a conference paper. They show a clear merit of the approach. On the other hand, they fail to explore more widely the practical applicability tradeoffs. How much larger games are now solvable with this approach? One of the key complications of the presented approach is the use of DAG strategy representation, which is certainly important if the game is supposed to fit into the memory. Subgame solving is likely to push the boundary a little, but combining it with depth-limited solving would most likely be much more impactful. With a value funcion the difference between DAG and tree representation would become much less relevant.

Team games are becoming an established line of work. However, as the authors admit themselves, it is a special case of imperfect recall games and it is not clear to me why to study them separately. Is the subgame solving in this paper applicable also in general imperfect recall games or are there some assumptions given by the special case that are necessary?

Minor issues:

 Line 53: It seems to claim that [15] was using an offline computed blueprint strategy, which is incorrect.

Line 277: A little more details on which Caratheodory’s theorem you mean and how to use it would be appreciated.

I assume that the refinement is run from each decision node in the experiments, but I did not find it explicitly stated anywhere.

questions: Are the results transferable to general imperfect recall games?
limitations: Limitations were addressed IMO adequately and I do not see negative societal impact of the work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents a subgame solving method that extends the existing approach to solving huge two-player zero-sum games. The main improvement of this paper is to solve the online optimization strategy through subgame solving. The subgame solving method is to generate the gadget game based on the team belief DAG (TB-DAG). The blueprint strategy is refined by iterative expansion using the column-generation (CG) algorithm, and its size increases linearly with the number of best-response oracle calls. That avoids the exponential size of the whole TB-DAG when expanding in the worst case. The blueprint generated by the CG algorithm is sparse. On this basis, the max-margin optimization problem in the subgame is converted into a linear program problem, which can be solved by the state-of-the-art integer program solver. Given the best-response oracle, the solving algorithm can be found to run end-to-end in polynomial time. Finally, they experimentally evaluated their method using a standard test suite and showed that this refinement of subgame solving is effective in reducing the difference between the value provided by the equilibrium strategy and the blueprint.
strengths_and_weaknesses: 1. Originality
Compared with other adversarial team game approaches, the subgame solving approach proposed in this paper extends the maxmargin subgame solving to adversarial team games (ATGs), generates a gadget game from its TB-DAG subgame, uses the CG algorithm to generate a sparse blueprint and expand the blueprint strategy iteratively, given the best-response oracle, and enables the refinement of the blueprint strategy to approximate an exact solution.

2. Quality
The authors implement an online refinement strategy that approximates an exact solution without expanding the whole TB-DAG exponentially. However, there are the following problems in this paper.
(1) This paper lacks detailed theorems and proofs of the properties of approximation to the exact solution.
(2) There are two ways to generate sparse blueprints, but the experimental evaluation only considers the sparse blueprints generated by the CG algorithm, and not on the sparse blueprints obtained by the other method, i.e., taking an arbitrary blueprint in realization form and expressing it as a sparse convex combination by Caratheodory’s theorem. The experimental evaluation is not complete and sufficient.

3. Clarity
The paper is somehow well-structured and the language is fluent. 
(1) The paper links to the literature giving relevant game examples, but the overall process of specific solving using the approach proposed in this paper is not intuitive and clear enough. 
(2) In the experimental results, the meaning of each index in Table 1 is not explained one by one.

4. Significance
The subgame solving technique proposed in this paper is effective for reducing the difference between blueprint strategy and equilibrium strategy and extends the successful approach of solving huge two-player zero-sum games, in which the CG algorithm is a very important component of subgame solving technology. Methods similar to column generation may also be used as fundamental building blocks in solving team games. However, in the experimental results, the team structure size of the game instances given is small.

questions: 1. How does the blueprint strategy generate? How to ensure that the blueprint strategy is a suboptimal strategy? Is it possible to generate sparse blueprint strategies if the game instances are relatively huge?
2. In Section 5.2, this paper mentions how the performance of this strategy refinement method varies as \alpha varies. Due to the nature of the CG algorithms, the improvement is sometimes not monotonically increasing in the number of iterations. What is the relationship between the performance of this method and \alpha? How about the performance when \alpha is greater than 5?
3. How does the equilibrium values calculate in the experiment?
4. The format of the conference names in the references is not uniform, some are abbreviations, some are full names, and the abbreviations of the names of the same conference are not consistent.
5. Figure 5.2, mentioned in Section 5.2, does not appear in the paper, there is only Figure 1.

limitations: The premise of the subgame solving approach proposed in the paper is that the blueprint strategies are assumed to be sparse, and the paper generates sparse blueprints by the CG algorithm. However, if the blueprint strategy generated by the CG algorithm is not sparse, the solution by the approach proposed in the paper may not be achieved in polynomial time.
review_title: null

Meta-review: metareview: The most serious and focused criticism for this paper comes from a single reviewer, who also happens to be the most confident reviewer. The crux of the criticism is that the authors should have compared against the 2021 AAMAS paper, "Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies" and the algorithm described therein. The authors point out that this algorithm as designed for symmetric observations and was never tested in the more general case. The reviewer thinks it might work well in the asymmetric case. He could be right, but it seems a bit much to require the authors compare with a reviewers hunch about modifications to existing work. If we allow reviewers to drag authors down that rabbit hole, nothing might ever get published.

The sentiment of the other reviewers is weakly positive. There is general concern that the games used in the experiments are not particularly large, and overall concerns about scaling to larger games.

On the positive side, the approach does appear to be novel and it does appear to do well in the provided experiments.
confidence: Less certain
Decision: Accept