Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors introduce a novel algorithm, Safe Exploitation Search (SES), that allows trading off safety and opponent exploitability in imperfect information zero-sum games. SES comes with theoretical upper bounds for exploitability, and lower bounds for performance. Unlike previous approaches, SES can be efficiently computed in an online fashion. The authors complement their theoretical investigation by a series of experiments using opponents of varying strength on two different poker variants.
 
strengths_and_weaknesses: # Strengths

The paper is well-written and organised, the authors' claims and results are clearly presented and, to the best of my assessment, sound. SES is addressing a well-motivated need, and is a useful contribution to the community.

# Weaknesses

* The paper should be spell-checked - there are quite a few minor issues.


questions: * I am mildly confused by your use of $v$, which is defined conditioned on both an infoset AND action, but the action is later frequently omitted (such as in Equation (2)). What happens to the action?

* How does the uncertainty arising from opponent modeling propagate into SES? Can SES be modified to take uncertainty over the opponent model into account?


limitations: The authors do a good job of discussing both limitations of their work, as well potential negative social impact.

# raised score to 7 after rebuttal
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper introduces a search algorithm for imperfect-information games that balances between opponent exploitation and being unexploitable by adding a parameter to interpolate between the two extremes. The authors present experimental results in a variety of games showing that the algorithm achieves most of the benefits of both, having both low exploitability and is able to exploit effectively.
strengths_and_weaknesses: The paper is well-written and easy to follow. It places its results well in the context of related search algorithms. Also, the results are convincing.

The weakness is the novelty. The algorithm essentially just interpolates between two already-known search algorithms. Moreover, I think the algorithm is essentially identical to the one already used in DeepStack (see the "Opponent Ranges in Resolving" section in the appendix). The main difference being that the authors propose using a model of the opponent as the policy, whereas DeepStack used its own policy net.

Update: Based on the author responses it's true that DeepStack is not the right comparison. However, the technique in the paper does appear to be a rather straightforward interpolation of Maxmargin and Unsafe search. For that reason I am still somewhat concerned about the novelty of the algorithm.
questions: Are there differences between this algorithm and the one used in DeepStack?
limitations: The authors have adequately addressed limitations.
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: In zero-sum games, opponents with limited rationality can be exploited if they do not play Nash equilibrium strategy. 
An exploiter can refine its precomputed blueprint (an approximate NE strategy) in the visited subgames as the game is played online, to take advantage of the opponent's irrational play, using Safe Exploitation Search (SES).
The refinement is done by optimizing a function which trades off safety and exploitation, set by a hyperparameter "alpha". 
Authors show safety and opponent exploitation bounds based on this hyperparameter, and uncertainty in modelling the opponent and approximation error of the blueprint or newly found strategy.
In practical terms, the player's strategy in a subgame is found using a special gadget game, which is an alpha-combination of max-margin gadget (for safety) and value solving subgame (for opponent exploitation).
strengths_and_weaknesses: 
Strengths:

- Explicit bounds on safety and opponent exploitation in terms of alpha.
- Empirical results on two poker games that show safety and exploitation as function of tradeoff alpha, and with different opponent modelling errors.
- Comparison with prior algorithm RNR, which is more computationally demanding. SES significantly outperforms RNR in both safety and exploitation.
- Ablation study of SES, where opponent strategy is fixed in the value-solving subgame -- performs worse than original. (A possible takeaway is that ranges+CBVs are enough for exploitation search).

Weaknesses:

- Authors do not explain how they compute opponent CBVs needed for max-margin gadget. (I suspect they computed these recursively over the whole game tree).
  Computing opponent CBVs can be non-trivial in large-scale problems, especially when we try to incoporate opponent modelling. This relates to following point: The work does not use depth-limited subgames (with value function evaluations), and cannot be therefore used efficiently to solve large-scale problems. In fact, authors claim L50 "enables our method’s scalability to large games such as Texas Hold’em", which they i) do not demonstrate and ii) is probably difficult due to computation of opponent CBVs.
  I advise this to be mentioned explicitly in the paper and weaken the claim of scalability. (i.e. claim it is future work, and not done by this paper).
- L7-8: "SES smoothly interpolates between the two extremes of online strategy refinement" -- There is no "smoothness" proposition in the paper, only  upper and lower bounds on exploitability and safety, respectively. (For a claim of smoothness I would expect something like a proof of Lipschitz continuity with respect to hyperparameter alpha.)


Other comments:

- L246-L247: Since σ^S_1 is the best-response to σ^S_2 and the two parts only differ at how to go to each infoset of player 1, player 1 will also keep his strategy the same in both parts. -- This is likely not true. If it was, there is no point in creating copies of the S into S_1 and S_2 in the first place? The top chance node/P1 node can change the expected utilities u(z)*reach_prob_{1,2,c}(z) and hence PL1 NE strategy in the two subgames.
- L248: I^i_1 unclear which infosets these refer to, are these the top infosets of the subgame S?
- L249: "the objective of a Nash Equilibrium of p2" -- NE are solutions to the max-min optimization. Just maximizing for one player is not enough to find a NE in a game.
- L250: Maximization is not well defined.
- Appendix A: Resolve Current Node is not defined.
- Appendix D: Figure 4: Top/Bottom should be Left/Right.
- The $\mathcal{S}$ is used as a disjoint set of subgames S (Thm 4.1), but should it not be the set set of subgames visited in an online play? (I.e from root to terminal).

questions: What is the reason for using precomputed blueprint for P2? Would not the algorithm work with no blueprint strategy? If I understand it correctly, blueprint is used only for theoretical derivations, to ensure strategy is well defined for the whole game (outside of the searched path).

limitations: Author claim their work does not pose negative societal impacts. Although opponent exploitation in games like Poker can have limited social impact, in general algorithmic exploitation of human irrationality in decision-making under uncertainty can have grave negative social impact and should be properly discussed.
review_title: null

Meta-review: metareview: This paper proposes an algorithm for searching for safe opponent exploitation strategies. The algorithm is based on alternating between a a safe max-margin search and an unsafe exploitation search. The paper provides strong theoretical guarantees for the algorithm, and some experiments that show the advantages of this algorithm. The reviewers found the paper well written and the idea of the algorithm interesting. A concern raised by one reviewer is the limited novelty of this work, since it is an application of DeepStack. Another reviewer shared this concern during the discussion, but argues that the paper still has merits because of the provided theoretical bounds and experiments. 
confidence: Less certain
Decision: Accept