Safe Opponent-Exploitation Subgame Refinement
Authors: Mingyang Liu
Chengjie Wu
Qihan Liu
Yansen Jing
Jun Yang
Pingzhong Tang
Chongjie Zhang
Venue: ICLR 2022 Submitted (2022)

Abstract: Search algorithms have been playing a vital role in the success of superhuman AI in both perfect information and imperfect information games. Specifically, search algorithms can generate a refinement of Nash equilibrium (NE) approximation in games such as Texas hold'em with theoretical guarantees. However, when confronted with opponents of limited rationality, an NE strategy tends to be overly conservative, because it prefers to achieve its low exploitability rather than actively exploiting the weakness of opponents. In this paper, we investigate the dilemma of safety and opponent exploitation. We present a new real-time search framework that smoothly interpolates between the two extremes of strategy search, hence unifying safe search and opponent exploitation. We provide our new strategy with a theoretically upper-bounded exploitability and lower-bounded reward against an opponent. Our method can exploit the weakness of its opponent without significantly sacrificing its exploitability. Empirical results show that our method significantly outperforms NE baselines when opponents play non-NE strategies and keeps low exploitability at the same time.

Under review as a conference paper at ICLR 2022
SAFE OPPONENT-EXPLOTTAAUU SUBGAME REFINE- MENT
Anonymous authors Paper under double-blind review
ABSTRACT
Search algorithms have been playing a vital role in the success of superhuman Al in both perfect information and imperfect information games. Specifically, search algorithms can generate refinement of Nash equilibrium (NE) approximation in games such as Texas hold' em with theoretical guarantees. However, when confronted with opponents of limited rationality, an NE strategy tends to be overly conservative, because it prefers to achieve its low exploitability rather than actively exploiting the weakness of opponents. In this paper, we investigate the dilemma of safety and opponent exploitation. We present a new real-time search framework that smoothly interpolates between the two extremes of strategy search, hence unifying safe search and opponent exploitation. We provide our new strategy with theoretically upper-bounded exploitability and lower-bounded reward against an opponent. Our algorithm enables computationally efficient online adaptations a possibly changing opponent model. Empirical results show that our method significantly outperforms NE baselines when opponents play non-NE strategies and keeps low exploitability the same time. also much more efficient than previous safe exploitation baselines.
INTRODUCTION
Behind the recent breakthroughs of superhuman AIs in Go (iilerr et al. 2016 2017 Schritwiieser | (020)) heads-up up no-limit Texas hold' om (HUNL) (Brown et al. [0188] Moraveík al.] 2017] Brown & Sandholm 2019; Brown et al. 2020), and Hanabi (Lerer et al. 2020). search plays a vital role. In perfect information games, Monte Carlo tree search (MCTS) is widely applied improve policy's strength. In zero-sum imperfect information games such as poker, search algorithms are used to find a Nash equilibrium (NE) approximation in subgames encountered in real time (Brown) & SSandholm 2017 Burch et al. 2014a). They are both theoretically sounded and empirically powerful. In fully- colperatoee imperfect information games, the search algorithm proposed in Tian ett al. (2020b is proved to never be detrimental the current policy. Lerer et al. (2020) also ensures original performanee asymptotically.
In zero-sum games, NE-based search algorithms (Burch al. 2014a; Moraveik et al. 2016 Brown & Sandholm 2017] Brown et al.. 2018) find safe strategies with low exploitability and produce strong baselines against all opponents (Brown & Sandholm 2019). However, it may be overly conservative confronted with opponents with limited rationality and fail to take advantage of their weaknesses obtain higher rewards (McCracken & Bowling 2004; Johanson al. 2007: Li & Miikkulainer 2018). From the other perspective, there have been extensive studies on opponent exploitation to address the problem. Some typical works (Carmel & Markovitch 1996; Billings al. 2003 Gilpin
& Sandholm 2006 Li & Miikkulainen, 2018) model the opponent's strategy based on previous observations and then search for new strategy to exploit this model. However, these methods often neglect the significance of the strategy safety, thus being highly exploitable by the opponent. Few exceptions including Johanson et al. (2007) and Ganzfried & Sandholm (2015a) aimed to search for safe and robust counter strategies, but they computationally inefficient in an online setting where the opponent model is being updated continuously with streamed data.
In this paper, study the dilemma of safety and opponent exploitation and present new scalable real-time search framework Safe Exploitation Search (SES) that smoothly interpolates between the two extremes of strategy search, hence unifying safe search and opponent exploitation. It enables

---

Under review as a conference paper at ICLR 2022
computationally efficient online adaptations to continuously changing opponent model, which is hard to address by previous safe exploitation algorithms. The safety criterion requires the refined strategy to stay close NE, formally speaking, to expose limited exploitability against any opponents, while the opponent exploitation criterion requires the strategy to adapt to its specific opponent and to exploit its weaknesses. We propose novel maximization objective which combines the safety objective and exploitation, controlled by the exploitation level a. We construct new gadget game to optimize this objective, which enables our method's scalability to large games such as Texas Hold'en em. Theoretically, we prove that SES is guaranteed to outperform NE at the cost of some constant increase in its own exploitability confronted with non-NE opponents. Empirically, we evaluate the effectiveness of our search algorithm in 1 didactic matrix game 2 poker games: Leduc Hold' em (Southey et al. 2005) and Flop Hold' em Poker (FHP))Brown et al.) 2019). The experiment results demonstrate that our algorithm significantly outperforms NE baselines against non-NE opponents and keeps low exploitability at the same time. Additionally, SES is much more computationally efficient than previous safe exploitation baselines.
2 RELATED WORK
This paper investigates the problem of safe opponent exploitation in two-player zero-sum imperfect information games. We propose novel search algorithm which balances between NE and exploiting opponents. Two major relevant research areas are search algorithms in imperfect information games, and opponent exploitation.
Search in imperfect information games. In recent literature, search techniques are witnessed to be important developing strong Al strategies in both perfect and imperfect information games (Burch et al., 2014a; Moravcik et al. 2016; Brown & Sandholm, 2017). Texas hold 'em poker is widely employed as benchmark for imperfect information games. A primary part of the long-term research on Texas hold' em poker is the evolution of subgame solving algorithms, which aim at achieving a more accurate Nash equilibrium approximation in the subgame encountered given a pre-computed strategy for the full game which we refer to the blueprint strategy. Unsafe search (Billings et al. 2003 Ganzfried & Sandholm, 20155] Gilpin & Sandholm] 2006; 2007) estimates the subgame reach probability assuming the opponent follows blueprint, and searches for refined subgame strategy. Subgame resolving (Burch et al. (0144)) and maxmargin search (Moravcik et al., 2016) are theoretically sounded safe search algorithms which ensure that the subgame strategy obtained is no worse than the blueprint. They search in gadget game and achieve safety by providing the opponent with the option not entering the current subgame. DeepStack (Moraveík et al. 2017) and Libratus (Brown et al., 2018) build strong poker Als with the aid of search. Beyond poker, search algorithms for subgame refinement have also shown promise in improving joint strategies in cooperative imperfect information games such as Hanabi (Lerer et al. 2020) and the bidding phase of contract bridge (Tian et al. 2020a). The purpose of our search algorithm is different from previous methods in poker literature. We seek to exploit opponents while keeping exploitability low, rather than simply approximating NE.
Opponent exploitation. Most previous opponent exploitation researches (Carmel & Markovitch 1996) Billings et al., 2003) Gilpin & Sandholm [2006] Li & Miikkulainen (018) typically model the opponent's 's strategy based on previous observations and then search for new strategy to exploit this model, but put little emphasis on safety.
One similar work is Johanson et al. (2007) which proposes p-restricted Nash response (RNR) find a safe exploitation strategy to the estimated opponent's strategy. It calculates a Nash equilibrium for the whole game restricting that the opponent plays the estimated strategy fix with probability p. and any strategy with probability 1 - p. In that paper, Johanson et al. (2007) prove that p- p-RNR to fix Pareto optimal with respect to exploitation and safety. However, it does not provide an explicit bound. Additionally, whenever the estimated opponent model changes or we want to use a different p to balance between safety and exploitation, R-RR has to recompute the strategy for the whole game. It is computationally inefficient in an online setting, where the opponent model is updated after every round with new game data. Our algorithm instead takes modelling error into account and provides explicit bounds for both safety and exploitation. With the aid of real-time search, it only searches for strategies in subgames encountered instead of the whole game. Our experiments show that it is more efficient than Johanson et al. 2007
2

---

Under review as a conference paper at ICLR 2022
Ganzfried & Sandholm (2015a) study safe exploitation strategies in repeated games, which is different setting from this paper. Intuitively, it achieves safety by risking in exploitability at most what it has earned over NE in expectation in previous rounds. Therefore, its expected value in the whole repeated game is never worse than the NE, In contrast, this paper focuses on the safety of stage game strategies. Furthermore, our algorithm is complementary to Ganzfried & Sandholm (2015a). Ganzfried & Sandholm (2015a) calculate an e-safe best response for the whole game at each iteration with LP. This procedure is one of the main limitations on the algorithm's 's scalability. Our algorithm, which only refines strategies in subgames in real-time can be a possible substitute for LP.
To our knowledge, we are the first paper to investigate the safe opponent exploitation problem in subgame resolving schemes. Subgame resolving enables online adaptations to a continuously changing opponent model, eliminating the need to recompute a whole game strategy. It offers computational benefits in practical opponent exploitation circumstances.
worthwhile mentioning that there also has been extensive research (Albrecht & Stone 2018) on agent modeling. However, this paper only focuses on the theoretical and empirical results of the search algorithm, but not the agent modeling techniques. We can use off-the-shelf agent modeling algorithms to estimate opponent's strategies. Agent modeling provides the ability to reason about the others, making predictions of their strategies. types, etc. He et al. (2016) embeds opponent model learning into deep Q-learning which stabilizes the training process faced with opponents whose policy is changing over time. LOLA (Foerster et al.] (2018) considers the evolution of other agents in the training process of multi-agent reinforcement learning. Raileanu et al. (2018) proposes model others from onc's own policy. Rabinowitz et al. (2018) uses meta learning to predict strategies of different kinds of agents.
NOTATIONS AND BACKGROUND
An extensive-form imperfect information game - ( 2, Z, Go, I) describes sequen- tial interactions among agents, where agents have private information. finite set P consists of n players and a chance node which represents the stochastic nature of the environment. The set of non-terminal decision nodes is denoted as H, and is a set of terminal nodes, or leaves. The set of possible actions is A, and X H A| is function which assigns to each decision node h E H set of legal actions. A player function p H -> P assigns to each decision node a player p E P who h'. If there exists sequence of
acts at that node. If action leads from h to h', we write h actions leading from / to hi, we write h C ht. At each node h E H, the acting player p = p(h) picks an action from legal actions E (h), and leads node h into its child h- aa The chance node always samples an action from its own distribution d.. which is common knowledge to all players. Utility functions are = (u1, Ug..... ... u, where u, Z --b R defines the utility of player at terminal node E 7. The nature of imperfect information is characterized by infosets I = (I,, I2..... In), where I, = (J,,,...., Ix,A:) ) a partition of H for player i. Two states in the same infoset must have the same acting player and the same legal action sets. We use ((h) to denote the infoset that h belongs to. A player cannot distinguish between states h4 and h2 if (h11) = 1(h2). and thus should behave identically on all states in the same infoset.
The strategy of a player p is op Ip x A - R. where (p a) is a distribution over valid actions on infoset I. For simplicity, we also use op(h, a) to denote op a). We use xT (h) to denote the prob- ability of reaching state h from the root when agents choose a strategy profile a = (a), o2.... o,,). Formally, x" (h) I (h't))(',ar a). We use =,, (h) aI ( o Pp(k)) (h', a) de- whenever possible. T0 (h, h²) is the reaching probability of h from h. x (h a, a,')) is the the probability of reaching h'' from h if action a is taken h. These probabilities can be formally defined in a similar manner.
note the probability of reaching h when player p always chooses the action that leads
The expected utility of player p given strategy profile a is uc = = T" (z)up()) The counter- factual value ug (1, a) is the expected utility that player p will obtain after taking action a at infoset I, given the joint policy profile is a. Mathematically, it is the weighted sum of expected values at all states h E
(I,a) Eber T- (1)m (h- a, (2)
(1)
ΣnEr T- (h)
3

---

Under review as a conference paper at ICLR 2022
In the rest of the paper, focus two-player sum games with perfect recall. Zero-sun means Vz E Z, u1(2) + u2(2) = O. Perfect recall means that no player will forget the information which has been obtained previously in the game. This is common assumption in related literature.
best response strategy (a-(p-)) = arg maxe, Up (0..0-p> -p) for player p is the strategy that maximize his own expected utility against fixed opponent strategy d-p- The exploitability of strategy op is exp(Tp) = up up " (0..BR_-((5)) where o² is the optimal strategy, and is an NE in two-player zero-sum games. It measures the performance of op against its best response comparing with the NE. A counterfactual best response CB is strategy where (p(1, a) > if and only if og (I.a) 2 max, oi b). Counterfactual best response is best response, but vice versa. The counterfactual best response value CBV, (I) = Up
(CBRg(o-p)oop)) is the expected utility the counterfactual best response policy. Since we focus on two-player zero-sum games, we will use CBVV>> (T) as shorthand notation for (T).
We follow the imperfect information subgame definition as in Burch et al. 2014b). An augmented infoset contains states which cannot be distinguished by the remaining players.
An imperfect information subgame S is forest of trees, closed under both the descendant relation and membership within augmented infosets for any player. Let Stop be the set of nodes which are roots of each tree in S.
Definition 1.
4 METHOD
In this section, we introduce our novel search algorithm called safe exploitation search (SES), which exploits the weaknesses of opponent while ensuring a bounded exploitability. Let a be the pre- computed blueprint strategy. Without loss of generality, assume search for player 2's refined strategy of by applying SES to all subgames S E S. Finally, the refined strategy for P2 after search is o22, which is the same d2 in (TH S, I & S} and is replaced with o3 in S S.
4.1 SAFE EXPLOITATION SEARCH
Our algorithm offers a unified approach to balance between these two demands with theoretical guarantees. The objective of our search algorithm to find new subgame strategy of for which maximizes
CBV + (1-10 a) min SB(o)) =a Σ p(t (1((1)))))-)) 1/ESuop
(1)))
1/ES
where a E [0, 1] hyper-paramette controlling the exploitation level, and p(11) is the estimated probability of player I entering infoset I Stop. Given P2's strategy (which is the blueprint σ22) and P1's actual strategy (which does not have to be the blueprint σ1), the real probability of player 1 entering infoset 1f Stop (which we denote y( (})) )) is determined. ý (i) is just an estimation of p(T)). For instance, in poker, it is the estimated distribution of private cards player holds. Both theoretically and empirically, such estimation does not have to be fully accurate. It can be done with off-the-shelf opponent modeling techniques, which lies beyond the focus of this paper.
Though seemingly complicated, intuitively, the maximization objective achieves balance between opponent exploitation and safety, controlled by exploitation level a. The first part of the objective
maximized when Expe..op P(I))CBV (4() is minimized. aims at finding a strategy oz which results in the lowest value for P1 under the assumption that the reach probabilities is p. It can be interpreted exploiting the estimated P1's strategy. The second part of the objective demands the resolved strategy to behave well against any reach probability distribution. We use the subgame
(b](I)) - C (17) (Moravcik et al. 2016) which can be regarded as the
margin minyjessop worst-case utility increase for P2.
By maximizing the objective[] 2 we provide sound theoretical results for both safety and opponent exploitation. Additionally, we provide analyses of how (1) exploitation level a, (2) accuracy of
4

---

Under review as a conference paper at ICLR 2022
opponent modeling, and (3) strength of the blueprint strategy impact the theoretical bound. By gradually increasing a from 0 to I, our algorithm tends to exploit rather than keeping safety.
Theorem 1. (safety) Let & be disjoint of subgames S. Let o* (0i. oz) be the NE where P2's strategy is constrained to be the same with 02 outside S. Define A = maxx se. ICBV (1t)- of (T)). Let p(T)) be the reach probability given by oi. Let p(Ti) be the estimation of reach probability p(Tí) given by the real opponent strategy. Define max
(
((T))
Whenever (2T + 1)xe > O, we have a bounded exploitability given by:
exp(d2)= S exp(oo) + 1 (2T + +)a A.
(3)
Recall that og is the refined strategy after search. The proof is provided in Appendix A This theorem implies that the exploitability of the new strategy is smaller than that of strategy Ø2 plus a constant value, which is the closest strategy to NE if constrained differ from 02 only in S. The corresponding theoretical result of maxmargin search (Moravcik et al. 2016). a safe search algorithm with no opponent exploitation abilities, is exp(e4) S (xp(a)) +2A. Comparing these two results, we can interpret the term 2/(1 (2r + 1)a) as the additional risk introduced by exploiting the opponent. If exploitation level a O, then our bound is as tight as that of maxmargin search (Moraveik et al.. 2016). The bound also gets tighter if the t gets smaller, or the blueprint 02 is closer to 02.
Theorem 2. (opponent exploitation) Let -1i--pli be the I.I distance of the distribution pl (Ti and p(T)) Let 1j minses max E/ESu (CBV, of) CBV 2 0. We use BRG 3.00) B (a)
to denote the strategy for player which maximizes its utility in subgame S E S against a-p under the constraint that BR rl (a) and op differs only inside S. By maximizing objective for all S E S.
the refined strategy 02 satisfies
(Bn (01))) (o1).ot) U2
(Bn (1n))1))0))))) (S) + (1 24) ex
1-a
(S) 2 u2
(4)
The proof is provided in Appendix A Observe that the reach probability p is characterized by Pl's strategy outside S and p is its estimation. Because the search algorithm always find a stronger response strategy for P1 in S (which is exactly B BR| (at)) well, opponent exploitation refers to adapting to Pl's strategy outside S. This theorem implies that the utility of the new strategy d lower bounded by the utility of σΩ when both confronted with Pl's unknown strategy outside S. It provides theoretical guarantees for the opponent exploitation ability of our algorithm. can be interpreted as estimation error. The lower bound increases if the estimation error get smaller or the blueprint 02 is closer to σz. We show empirically how exploitation level and estimation error impact both safety and exploitation abilities in section 5
4.2 GADGET GAME
In order to find oB which maximize objective a straight-forward method is to reformulate the maximization problem as a Linear Programming problem (Moraveik et al., (016). However, LP solvers (Koller et al. 1994) cannot handle large-scale problems. Alternatively, inspired by MMraveikk al. 2016), we create a gadget game and then apply iteration- based NE algorithms such as CFR (Zinkeiich et al. 2007 Tammelin et al. 2015 Lanctot et al. 2009) in the gadget game. The gadget game is carefully designed such that the NE solution found is exactly the solution to the original optimization problem.
As shown Figure the original subgame is copied into two identical parts S1, S2 in the gadget
game. Player 2's infosets stretch over both branches, while player 1 can distinguish between the two parts. The procedure of constructing such gadget game can be summarized into 4 steps: (i). Create a chance node at the top of the gadget game. (ii) For the left part of the gadget game, PI node to let P1 choose an infoset I; to enter. The following chance node samples a specific state with probability proportional to (h,()) for all h I1 (iii) For the right part, create chance node sampling an infoset 7j. The following chance node again samples specific state with probability
construct
5

---

Under review as a conference paper at ICLR 2022
S
S₂
Figure 1: The gadget game of SES. The shadow and dashed line indicate that player cannot distinguish between the two branches. C' represents chance node, P1 represents player I's action node. S₁ and S2 are two identical copies of the subgame S with utility shifted.
P1
L
M
R
P2
U
3
2
4
0
2
3
9.9
D
3
2
9.9
F
-100
-100
10
Table 1: The payoff matrix of the example zero-sum matrix game. The values are the payoffss of player 2. We will resolve for player 2.
proportional to (h) for all h Ir. (iv). Shift the utility of the gadget game by of (4f). The details are described below.
The chance node the top goes to the left part with probability 1 a, and the right part with probability a. The outcome is visible to P1 but not P2. Therefore, corresponding nodes in both branches are in the same infosets for P2, and his strategy of will be the same for both parts. Since of is the best-response to of and the two parts only differ at how to go to each infoset of player 1, player will also keep his strategy the same in both parts.
2. We subtract un (2) by of (Ti) for all h, h E I, and add u2(2) by 2y (T)) in order to keep the subgame zero-sum. By doing so, the objective of a Nash Equilibrium pa will change from maximizing -CBV (Ti) maximizing of (fi) CBV (Ti).
3. As for the left part of the gadget game, the P1 node on the second level in Figure enables P1 enter an arbitrary infoset 1f. Since this zero-sum game, in NE strategy, he will enter the one with lowest of (If) (B), o5) which is exactly the minimization in the second term of (E
4. The chance node on the second level of the right part will sample an infoset I according to reach probability p(I)). So that the NE objective of this part is exactly the summation in the first term of SF(())
4.3 MATRIX GAME
In this part, we offer matrix game as example to show the necessity of considering safety and expected payoff simultaneously, and to demonstrate the superiority of SES over a simple mixing strategy, which follows a best response to the estimated opponent model with probability and follows the blueprint with probability 1-a. a.
In the matrix game shown in Table I let's consider two specific NEs. In both NEs, P1 will play LMM with 0.5 probability each. P2 will play U/O with 0.5 probability in the first NE and O/D with 0.5 probability in the second NE. Suppose the blueprint strategy is the first NE. Consider the case when PI plays rather weak strategy that he will only play action R. We apply SES to search for P2's refined strategy.

---

Under review as a conference paper at ICLR 2022
Explubiity
100
120g
dippsh
7.8
7.
B25
Minm
0.0
04
5.4
0.5
0.5
100
0.0
0.2
0.4
0.5 0.
1.5
Figure 2: Left: Expected payoffs of SES and the mixing strategy in the proposed matrix game example. Right: Exploitability of the two algorithms.
When the estimation of opponent strategy is accurate such that p, the best response of P2 is always playing F, which is highly exploitable, while SES finds the second NE under proper a. To give more details, the exploitability and expected payoff of the strategy found by SES and the mixing strategy are shown in Figure 2] We can see that SES achieves both lower exploitability and better performance than the mixing strategy almost all values. The reason behind this success is that P1 always playing R is a Gift Strategy (Ganzfried & Sandholm, 2015a) in the designed matrix game and SES manages utilize such gift strategy. Strategy o- is Gift Strategy if it
best response NE strategy o. Therefore. we can switch to of to get better performance against O-p while also keeping exploitability low. However, the simple mixing strategy cannot find such "good" NE strategy so that it will perform much worse in both exploitability and expected payoff.
EXPERIMENT
Our experiment is done in Leduc Hold' em (Southey et al., 2005) and Flop Hold' em Poker (FHP) (Brown et al.) 2019). Leduc Hold' em is smaller-scale poker games and FHP is a larger one. The rules of these two pokers are provided in Appendix B We demonstrate the exploitability and evaluation performance of SES against opponents of various strengths. The exploitability measures search algorithm's s safety, while head-to-heal evaluation measures the ability of opponent exploitation. We also illustrate how estimation accuracy of opponent's strategy and the exploitation level impact the results. Please refer to Appendix for implementation details.
5.1 OPPONENTS
In our experiments, we test the performance of our algorithm against opponents of various strengths. For both Ledue Poker and FHP, we create 3 types of opponents with 3 random seeds each. The first type of opponent is approximation of NE in the full game, and is regarded computed in the same way as the blueprint strategy with different seed. For the second and third type of opponents, distribution randomly with probability Prahume = 0.3 or 0.7. We multiply the probability of each action by a random variable from Uniform(O, 1), and then re-normalize the probability distribution. The procedure is motivated by Brown et al.] (2018). in which such method is applied to create a number of diverse but reasonably strong agents. Even when Prstuftie 0.7, the strategy keeps close to NE with average LI distance of each infoset 0. 132 comparing to 1.036 of a random strategy to NE, So they are regarded as opponents who are not fully rational but with competitive strength.
strong opponent.
enumerate every infoset in the blueprint strategy and shift the action
5.2 SAFE OPPONENT SEARCH
In Figure we demonstrate the head-to-head evaluation performances and corresponding exploitabil- ity of the refined strategies found by SES against opponents of various strengths, under different exploitation level a and estimation errors of opponent's 's strategy. Different lines in each plot refers to corresponding estimation e, which is the I.1 distance of ý and p. We evaluate our refined
7

---

Under review as a conference paper at ICLR 2022
Eveluation!Psswve 0.0)
Evaluation(PPsuute =0.3)
Evaluetion(Paneet =0.7)
370
Anorud rerrecti a.4
-70
310
ExplottabillyIPPo... 0.0)
ExplotaailltyPPccoee
Expliitabilty(PPaasss
do 6.0
Facton Bustardo
254
Sodaa-o-- 6.
04
Evaluation(P/auee Pecuun 0.0)
Evaluation Preast -0.3)
Evalustion (Parune 0.2)
0.4
1.4
3.5
1.0
13
0.2
0.4
04
02
044
100
Exploitabilll((Ponn
0..03
ExpliitabilityPPPeeee
0.30
Exploitablltt(PPsen 0.7)
34
3.9
3.
33
54
Figure 3: Row 1&2: Experiment results on Ledue poker. Row 3&4: Experiment results on FHP. From left to right, each column represents a type of opponent with Premufte = 0.0, 0.3, 0.7. The first row of each game shows the head-to-head expected payoff's against corresponding opponents, while the second row demonstrates the exploitability calculated for different refined strategies. The X-axis is the parameter which controls exploitation level.
strategy when 0.0, 0.3, 0.6, 0.9, 1.2. The blue line is the result of blueprint strategy without conducting any search.
Generally speaking, SES balances between safety and opponent exploitation. The increase of exploitation level a helps win more chips from opponents, while resulting in the increase of the strategy's 's own exploitability. As can be seen in Figure 3 the exploitability increases when the exploitation level a grows from 0 to 1, which is consistent with Theorem 1. One exception is in FHP when e small: the exploitability surprisingly keeps decreasing even if SES puts more emphasis on opponent exploitation. Similar situations have also occurred in previous literature (Brown & Sandholm 2017). The reason is that our opponent is quite close to NE outside the subgame which will make close when is small, which means the 7 in Theorem I is small. As result, we will have a low-exploitability resolved strategy when using unsafe search and the exploitability increases as increases.
When the estimation is completely correct (c = 0.0, the yellow line), the expected payoff in FHP increases as the exploitation level a grows higher. In Ledue poker, since the game is very small, the pre-computed blueprint is very close to NE. Therefore, when confronted with relatively strong opponents (Prstuftte 0.0, 0.3) which are also close to NE, actually few things can be done other
8

---

Under review as a conference paper at ICLR 2022
than sticking with the blueprint. So the improvement introduced by SES is small. When facing relatively weak opponent (Prshuffee = 0.7), the improvement margin is slightly larger.
SES relies when the prediction of p(1f) is not accurate, we evaluate the performance of our algorithm with different values of estimation error As illustrated in Figure[3] the exploitability increases and the expected payoff drops when c grows larger. The result is expected since an accurate estimation always provides benefits. However, also demonstrates that SES can still achieve trade-off between safety and opponent exploitation even when e is considerably high. For instance, in FHP, e is between O and 2, and e 1.2 means that the predicted distribution is almost random. When S 0.6, the expected payoff still keeps increasing with respect to a. In case of a bad estimation, we can always choose smaller a to ensure safety.
estimation of opponent's strategy. In order to test the robustness of our algorithm
5.3 COMPARISON WITH RESTRICTED NASH RESPONSE
Evaluation/Psauve = 0.0)
Evaluation(PPsuuee = =0.3)
Evalustion =0.7)
14
11467)
-16
-28
-15
pldl
ExploitabilityPFa..e (..)
Exp lottaabilityPPtaaa 0.3)
ExplortabilltyPPeawe 0.7)
30
A1d
Figure 4: Comparison between SES and RNR. From left to right, each column represents a type of opponent with Pratulle = 0.0, 0.3, 0.7. The X-axis is the parameter a for SES and p for RNR.
We also compare SES with restricted Nash response (RNR) (Johanson et al. 2007) in FHP. In each round, we limit the computation time of (NR(molall) to 10 CPU second which is the same for SES. However, as stated in section 2 RNR needs to recompute a strategy for the whole game each round. It cannot converge in 10s. So we also compare with RNR(big), which has budget of 10M CFR iterations in each round (around 190 CPU second in time). In contrast, SES only uses 10M CFR iterations to calculate its blueprint once. As is shown in Figure 4 SES significantly outperforms RNR(normal) in both exploitability and evaluation. SES also achieves much lower exploitability than RNR(big) and comparable evaluation results with much less computation time.
6 CONCLUSION
We propose a novel safe exploitation search (SES) algorithm which unifies both safe search and opponent exploitation. With the aid of real-time search, SES can make online adaptations to a changing opponent model. We also prove safety and opponent exploitation guarantees of SES in Theorem and Theorem 2. The experimental results in our designed matrix game confirm the existence of the refined strategy which is both safe and actively exploiting the opponent. In games of poker, our method outperforms NE baselines while keeping exploitability low. SES is also much more efficient than previous safe exploitation algorithms without search. The exploitation level a is now regarded as a hyperparameter in our algorithm. However, ideally, a should be learnt automatically from opponents, and should be adaptive to opponent's strategy change. We leave this for future work.
We test it Intel(R) Xeon(R) Platinum 82761. CPU @ 2.20GHz
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Stefano V. Albrecht and Peter Stone. Autonomous agents modelling other agents: A comprehensive
survey and open problems. Artificial Intelligence, 258:66-95, 2018. ISSN 0004-3702. doi:
.022. URL
sci http://www.cieeeeerrrttttt..ctee com/
Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terence Schauenberg, and Duane Szafron. Approximating game- theoretic optimal strategies for full-scale poker. In IJCAI, volume pp. 661, 2003.
Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfecctinfoorationn games. Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 689-699, 2017.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456):
885-890, 2019.
Noam Brown, Tuomas Sandholm, and Brandon Amos. Depth-limited solving for cnperfect-innfomattie games. In Advances in Neural Information Processing Sys- tems 31: Annual Conference on Neural Information Processing Systems. Mon- tréal, Canada, pp. 7674-7685, 2018. URL innrectttiifooaaasee -aa-s
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International conference on machine learning, pp. 793-802. PMLR, 2019.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-informane
games. arXiv preprint arXiv:2007.13544 2020.
Neil Burch, Michael Johanson, and Michael Bowling, Solving imperfect information games using decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014a.
Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014b.
David Carmel and Shaul Markovitch. Learning models of intelligent agents. In AAAI/AAI,, Vol. 1, pp. 62-67, 1996.
Jakob Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Picter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. In Proceedings of the 17th International Conference Autonomous Agents and MulriAgent Systems, AAMAS 18, pp. 122-130, Richland, SC, 2018. International Foundation for Autonomous Agents and Multiagent Systems.
Sam Ganzfried and Tuomas Sandholm. Safe opponent exploitation. ACM Transactions on Economics and Computation (TEAC), 30)):)22,,20111111
Sam Ganzfried and Tuomas Sandholm. Endgame solving in large poperfect-inforaatie games. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, pp. 37-45. Citeseer, 2015b.
Andrew Gilpin and Tuomas Sandholm. A competitive texas hold em poker player via automated abstraction and real-time equilibrium computation. In AAAI, pp. 1007-1013, 2006.
Andrew Gilpin and Tuomas Sandholm. Better automated abstraction techniques for imperfect information games, with application to texas hold' em poker. In Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, pp. 1-8, 2007.
He He, Jordan Boyd-Graber, Kevin Kwok, and Hal Daumé, III. Opponent modeling in deep reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1804-181111 1813, New York, New York, USA, 20-22 Jun 2016. PMLR. URL http::/ppoceet
m prw.s v hhl 6. html
10

---

Under review as a conference paper at ICLR 2022
Michael Johanson, Michael Bowling, and Martin Zinkevich. Computing robust counter- strategiss. 2007.
Michael Johanson, Neil Burch, Richard Valenzano, and Michael Bowling. Evaluating state-space abstractions extensive- games. Proceedings of the 2013 international conference on Autonomous agents and mulli-agent systems, pp. 271 1-28,, 2013.
Daphne Koller, Nimrod Megiddo, and Bernhard Von Stengel. Fast algorithms for finding randomized strategies in game trees. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 750-759, 1994.
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H Bowling. Monte carlo sampling for regret minimization in extensive games. In NIPS, pp. 1078-1086, 2009.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search
in cooperative partially observable games. Proceedings of the AAAI Conference on Artificial
Intelligence, 34(05):7187-7194, Apr. 2020. doi: 10. 10.1609/aaii v34.ai..34..6.... 6208. URL https
T/ojs . aaai.ai......................... orr/ witp:/indexx.cm whtppddwppppppppppppppppppp AAAT AwA./AAatiit.. wecllleeveeee wwreew///// 6208
Xun Li and Risto Miikkulannen. Dynamic adaptation and opponent exploitation in computer poker. In Workshops at the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Peter McCracken and Michael Bowling. Safe strategies for agent modelling in games. Artificial Multiagent Learning, Papers from the 2004 AAAI Fall Symposium. Arlingion, VA, USA, October 22-24, 2004, volume FS-04-02, pp. 103-1 10. AAAI Press, 2004. URL https: http://wwwaaa//eoo aaai org/ http///bbaaryyyparsae http:paaw/yyymoiiaaaaa/////0 /
014. phpp
Matej Moraveik. Martin Schmid, Karel Ha, Milan Hladik, and Stephen Gaukrodger. Refining subgames in large imperfect information games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Matej Moravcík, Martina Schmid, Neil Burch, Viliam Lisy, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael H. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356:508 513, 2017.
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, S. M. Ali Eslami, and Matthew Botvinick. Machine theory of mind. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 02218-4227.. PMLR, 10-15 Jul 2018. URL http::/ppoocedding
mlr.
2188.18880 html
Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself in multi-agent reinforcement learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4257-4266. PMLR, 10-15 Jul 2018. URL http: http://proceedings mlr www.ppeees//v///aaaaeaiiii html
Julian Schritwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):6046609 2020.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukeuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 2016. doi: 10.1038/naturel 6961. URL wtttp:://daatt org.l.rg//1 10. 1ww.1103/nauuuu 16961
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint 17Xiv:1712.01815, 2017.
11

---

Under review as a conference paper at ICLR 2022
Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. Bayes' bluff: opponent modelling in poker. In Proceedings of the Twenty- First Conference Uncertainty in Artificial Intelligence, pp. 550-5550 2005.
Oskari Tammelin, Neil Burch, Michael Johanson, and Michael Bowling. Solving heads-up limit texas hold'em. In Twenty-fourth international joint conference on artificial intelligence, 2015.
Yuandong Tian, Qucheng Gong, and Tina Jiang. Joint policy search for multi-agent collaboration with imperfect information. arXiv preprint arXiv:2008. 06495, 2020a.
Yuandong Tian, Qucheng Gong, and Yu Jiang. Joint policy search for multi-agent collaboration with imperfect information. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.),
Advances in Neural Information Processing Systems, volume 33, pp. 19931-19942. Curran Asso- ciates, Inc., 2020b. URL httpps://ppoceee.ngggg meersiippp wtt.seerrr......ppppreeee..... wttpc//ppppppp///eeeeep 20000/0//ee///////// ce
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information, Advances neural information processing systems, 20: 1729-17366 2007.
12

---

Under review as a conference paper at ICLR 2022
A PROOFS
A. PROOF OF THEOREM 1
Theorem 1. (safety) Let be a disjoint set of subgames S. Let o² (0i, oz) be the NE where P2's
strategy is constrained to be the same with 02 outside S. Define A = max sea, |CBV1 (Ti)- of (T)))- Let p(T)) be the reach probability given by oî. Let p(Ii) be the estimation of reach probability p(Ti) given by the real opponent strategy. Define
(0 P(T)
maxges.11
((T))
Whenever 1 - (2T + 1)xx > O, we have bounded exploitability given by:
2 A. 1 - (2T + 1)a
exp(o>) S exp(o)) +
(5)
Proof:
For simplicity, we will omit the subscript of CBV by default. In order to prove Theorem 1, we will use mathematical induction on the level of the infoset. The depth has the same definition as in Brown & Sandholm (2017). i.c.
For all the infosets which are direct parents of the subgames, we define L(I) = 0.
For the infosets that are not ancestors of the subgames, we define L(I) =
For any infosets that are ancestors of the subgames, we define
L()) maXres)ee()) L(I') + 1. That is, has a higher level than any its successors.
BASE CASE OF INDUCTION
Firstly, we will prove that for any infoset with level 0, the inequality of theorem 1 holds. For convenience, we consider that theorem I in specific subgame S.
We will prove the infoset the top of the subgame first. Since SE(O?) 2 (1 a-))
()(((((-AA)) = A, we have
(1 - a) min (1) - CBV + - -BV (11)
R
=SE(o)))
2SE(a)))
--A
since of = arg max,, SE())).
Furthermore, we have
-BV
-E(EEEE + ( (T))
<A+ EEC)CEEV" ((1)
+ ΣELDCCEO - -CB (11)
-CV + Σ - -CB (T))
where the second term E( CBV (ff) is no larger than because Σ; CBV (I+) is exactly what of minimized. Otherwise, of can change the strategy in the subgame that he will get higher reward against of which conflicts the definition of NE.
13

---

Under review as a conference paper at ICLR 2022
And will further decompose Ii Stop into two parts, {
} and { They have the property
that CBV CBV (1 & 0 and CBV (11++) - CBV (1i+))
And since
E, ( -B))
CBV (T)) & 0 as discussed above, we have
E - CBV (1)7) + Σ (() CBV (1++))
(8)
which implies that
- E [BthiCBrodd)> - - (9)
Then we have
- (oth)-/thh)cBB=3)0---
- (1
47
+ -
17
p(1 -
ST
(10)
E (t 1)
2r
(CB (1t)
$ - 2r min
The last inequation holds since miny; (CBV - CBV (12) < 0 since oî is the strategy with lowest exploitability by only changing strategy 0g in the subgames.
Back to Equation 7 we have
- - C (7:) < A 2r min (CBV -C
(1I)
19
And substitute it into Equation 6
- (BB
A + (1 -2ur) min
(19(1)) CBV- (1()) + aals - 27) min (1) (12) Ki
2 a) min
so that
CBV CBV +
1 1 (2r + 1)a A
(13)
for all I in the subgame.
And for infoset I out of the subgame with level 0, since the refined strategy o and blueprint strategy T2 the same here, the CBV value is exactly the same and the inequality holds.
14

---

Under review as a conference paper at ICLR 2022
INDUCTIVE STEP
The inductive step mostly follows that Brown Sandholm (2017).
Since CBV (T1) S CBVV (T)) + 1-(2++1p 1)a A holds for every subgame S, o2 will also satisfy
this inequation since A and are defined as maximum over all subgames.
Now, suppose ( & CBVV + +1) holds for any infoset with level lower or equal to k, we will prove that it also holds for infoset with level k + 1.
By definition of (B)(L)).
CBV (BV = Σ
T (h) (h (h-a))/
Σ
क (h)
hET
hET
Thm (h)
Σ
Σ hET
(14)
heh
If (Esucc(h,a)
Σ
Σ heh
π (1)
hEfI ('Esuca(h,
We can swap the two summations above since the game is perfect recall, then
CB. = Σ
E ()) (1'))
Σ (h) heh
(15)
([Esuce MEE
By substituting the definition of CBV(T)) into the equation above,
(B,
Σ [[
CBV Σ =3701))
Σ
(1)
(16)
NER
he4,
And by the induction hypothesis,
CBV=2(1,,a) S
Σ
(C
2 1 ( A)
Σ
Σ क
(17)
([Esuc((Li.a)
MER
heh
Because T, is out of the subgame and o2 02 is exactly the same outside the subgame, we will get
(L,
Σ
(CBV*)(1)
a A)
Σ
-))(K))
Σ Th)
1 1
NE
BET
= CBV (11,
2 2 A
Σ
o Σ
T (kh))
Σ
2 (h)
(18)
1 MEsuco(11, MEE
heh
= CBV (I, + 1 a
a
Finally, by mathematical induction we get
2 exp(os) S exp(o²) + 1- (2F + 1)a
(19)
A.2 PROOF OF THEBREM 2
Theorem 2. (opponent exploitation) Let 11p-pl1 be the L. distance of the distribution p(T)) and p(1t). Let minges maxieeS.op ( CBV (4) 2 0. We use B to denote the strategy for player which maximizes its utility in subgame S E against o-p under the constraint that BR BR)B.0r((0) (a) and op differs only inside S. By maximizing objective for all Se5 the refined strategy o22 satisfies
(BR Bel Bal (o)))0))
1-a (1 22) - en
U2
(S) 2 u2
(S)
(20)
a
15

---

Under review as a conference paper at ICLR 2022
Proof: Still, we only consider specific subgame S first.
of is maximizing
(1 - a) min
(C())) ta -
(21)
2(og)
f(a8)
So, we have
(1
(22)
and
- CBV((), oB)((,,))) = 2
max
f
(23)
AS
g - s A 7 (g(0)) 2 -A)
Therefore,
af(o)) 2 +
+ (1 24)
(24)
which means
1 a (1 22) (T)
EUAIBBVO (11)
1 1-a a (n - -22) - E (B)
0 ENGDBVA (A))
1- (n 22) EM(ACBVA)))
(25)
(p(()) - (C (1)) CBV (
EuthBBAA (7))
1 1- a (n - 222 - [M(D)CBV')()) -
Σ (RIDSS
a (n (n-24 22) - -on+ + Σ P(T)) BR(O)),
(8
2,02 18-0
S (1))) (S) 1 (n 22 en
e22
(S)
u2
Since is defined minimum over all subgames, we have
( (R 1BR (o5).o%)
(BR) (00))))) (8) + a
1
U2
(S) 2 ug
(n 22) - erj
(26)
B POKER RULES
RULES OF LEDUC POKER
Ledue Poker is a two players game. Ledue Poker, there are 6 cards in total, three ranks( Q, K ) with suits((a, b)) each. And the beginning, every player should put chip into the pot and then will be dealt with one private card. Then, two players alternatively bet. They can call, raise and fold. If any of them fold, the game ends and all chips in the pot belongs to the other player. And
16

---

Under review as a conference paper at ICLR 2022
when player call, he has to put chips in the pot ensure that he contributes equal chips as the other player in the pot. When a player raise, he has to ensure that he contributes more chips than the other player in the pot. A betting round ends when player calls.
Ledue Poker is divided into two betting rounds. In the first round, a private card dealt to each player and then card is dealt on board and the second betting round starts. When the second round ends, both of the player show their private hands and the stronger hands win. If player's private card has the same rank as the public card, then he wins. Otherwise, we have < Q < K and the higher one wins. And in each betting round, there will be at most two raises in our experiment and each raise should contribute 1 more chip in the first round and 2 more chips in the second round.
player start to bet. After the first betting round ends and nobody folds, public
RULES OF FLOP HOLD'ER EM POKER
The rules of Flop Hold' em Poker is similar to that of Ledue Poker. In FHP, we use the standard 52-card deck. At the beginning, the first player will contribute chip the pot and the second player will contribute chips. And then they will dealt with 2 private cards each and the first player start to bet. There are still two betting rounds and the raise sizes are both 2 chips. At the end of the first betting round, there will be 3 public cards dealt on board. And the players will show their private card at the end of the second betting round and the larger one wins the game, In FHP, we have the same rule of card order as a standard Texas hold 'em.
C IMPLEMENTATION DETAILS
Ledue Poker. In Ledue Poker, we solve for a blueprint strategy using variant of CFR algorithm (Lanctot al.] 2009 Tammelin al. 2015) with 1M iterations in the full game. Then we apply search in subgames when the board card is dealt.
Flop Hold' Poker (FHP). As for FHP, there are 1,286,792 different infosets for each betting sequence. We cluster them into 200 infosets by an abstraction algorithm (Johanson et al. 2013) in order to make equilibrium finding feasible. Then, we compute a blueprint strategy in this abstraction with 10,000,000 iterations. We apply search immediately once the flop cards are dealt.
17


Reviews:
[{"review_id": "hflQY-eXj5t", "reviewer": "Reviewer_f5FT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The paper is clean and easy to read.\n\n2. Both the theoretical results and the experiments clearly support the main claims of the paper.\n\nWeaknesses: \n\n1. The main contribution of the paper is only a minimal step on top of known ideas (a convex combination of unsafe and maxmargin subgame solving). The theoretical and experimental results are not at all surprising either.\n\n2. Related to above: I'm not completely satisfied with the comparison to the past safe exploitation works [Johanson et al '07, Ganzfried & Sandholm '15]. As far as I can tell, the present paper simply uses a different parameterization of the Pareto frontier of exploitation vs exploitability--it uses the mixing amount $\\alpha$; the others use the exploitability, formulating the objective as \"maximize exploitation such that exploitability is at most $\\varepsilon$\". These are not very different. Further, LP solving in games is not that slow, especially with recent advances [Zhang & Sandholm '20]; in particular, the subgames in experiments seem tractable with LP.\n\n[Zhang & Sandholm '20] Sparsified Linear Programming for Zero-Sum Equilibrium Finding", "summary_of_the_paper": "The paper introduces Safe Exploitation Search (SES), which achieves a balance between maxmargin solving (guaranteed to be safe, but non-exploitative) and unsafe subgame solving (unsafe, as the name suggests, but exploitative of the opponent's initial distribution at S_top) by mixing their objective functions. The paper provides both theoretical and experimental evidence that the method does a good job of balancing the two objectives. ", "summary_of_the_review": "Well-written, but in my view not very novel/just incremental work over past work on subgame solving. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fV53FrEUl5", "reviewer": "Reviewer_hmTT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To my understanding, the technique presented by the authors to interpolate between a Nash equilibrium strategy and a best response (say, for Player 1) simply boils down to the following:\n- introduce a parameter $\\alpha$ and optimize the objective $f(x) = (1-\\alpha) \\cdot \\min_{y\\in Y} \\\\{x^\\top U y\\\\} + \\alpha\\cdot x^\\top U \\bar{y}$, where $x$ is a strategy of Player 1, $Y$ is the set of strategies of Player 2, and $\\bar{y}$ is a \"predicted\" strategy for Player 2;\n- solve the above optimization point (that is, solve $\\max_{x \\in X} f(x)$ where $X$ is the set of strategies of Player 1.\nThe presence of search seems just an implementation detail that obscures the above, straightforward idea.\n\nIf my understanding were to be confirmed correct, I find the paper very light theory-wise, and I definitely think that the idea should be stated for what it is instead of interspersing it with the search formalism, which ends up obscuring the idea and making it looks significantly more complex than it is.\n\nAgain assuming I didn't miss anything about the fundamental underlying idea of the paper, the technical results (Theorems 1 & 2) are not surprising at all, and just amount to bounding the two terms in the definition of $f(x)$ independently.\n\nGiven the limited technical contribution I would be significantly more satisfied with the paper if it had shown more compelling/insightful experimental evidence of the benefit of the approach. However, the paper only experiments on one domain (poker), and the experiments do not seem to show any particular interesting insight. For example, the experiments find that if the prediction $\\bar{y}$ is accurate, then for large $\\alpha$ the maximum of $f$ will be a best response to the strategy of the opponent, and if the prediction is not accurate, then one would be better off by picking a lower $\\alpha$. I find that completely expected, but perhaps I missed some more subtle point?", "summary_of_the_paper": "The paper proposes a technique to smoothly interpolate between computing a Nash equilibrium strategy and computing a best response. The technique is presented in the form of search for an extensive-form imperfect information game. Experiments on two poker variants are presented showing that the technique can indeed interpolate between the Nash equilibrium strategy (\"safety\") and the best response (\"exploitation\").", "summary_of_the_review": "My biggest concern with the paper is about the significance. I believe that the idea behind the paper is simply optimizing a convex combination of functions, and that the search formalism that was imposed on top is mostly an implementation detail from a theory point of view. I also find the experiments unsurprising and not particularly insightful. Other than that, I do not believe the paper to be technically flawed or problematic in its claims. However, I find the significance concern is serious enough to prevent me from recommending acceptance. I look forward to a robust discussion with the authors on that point.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "e8S9pvak_Nx", "reviewer": "Reviewer_Wp7Z", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper’s motivation is easy to follow and does a good job of introducing subgame search and opponent exploitation. I have not found any glaring errors in derivations or proofs. In terms of significance, this paper answers the natural question of how opponent weaknesses can be exploited without overly sacrificing safety. Experiments are sufficient.\n\nOne area this paper could do a lot better in terms of clarity. For example, the definition of CBR at the end of section 3.1 could be much more precise---the argument of CBR need only depend on player -p, and \\sigma_p in the definition should really be CBR_p(\\sigma_{-p}). In other areas, the authors could be more precise, e.g., in section 4.1, “under the assumption that the reach probabilities *remain the same*”, could be changed to “is \\hat{p}(...)”. This is to disambiguate between \\tilde{p} and \\hat{p}. The gadget game presented seems correct to me, and Figure 1 was very useful in illustrating it. However, for readers unfamiliar with gadgets, the textual representation could be insufficient. For example, P2’s infosets should stretch over both the left and the right branches (which is briefly alluded to in point 1).\n\nTheorem 1 provides a natural extension of the bounds of Moravcik et. al. One concern I have is how useful these bounds are in practice, in particular for selecting an appropriate value of alpha. In larger games (e.g., FHP), it is very likely that some information sets are never reached in practice even over many rounds of play. Hence, tau is not known, or may not even be estimated using data (this admittedly is a problem for any type of opponent modeling). The authors’ claim at the end of section 5: “In case of a bad estimation, we can always choose smaller \\alpha to ensure safety”. In practice, how do we know we have a bad estimation if there are no samples to compare with?\n\nThe authors present experimental results with varying epsilon (estimation error of opponent strategy). What was the procedure in which this error was introduced?\n\n", "summary_of_the_paper": "This paper proposes a method of subgame resolving in zero-sum extensive form games, blending in elements of theoretical safety, as well as more classical approaches based on opponent modeling. The method is fairly straightforward, utilizing a modified objective balancing between the safety objective (used in Moravcik et al) and a best-response like objective use in opponent modeling. To facilitate compatibility with modern solvers such as CFR, the authors propose gadgets transforming the refinement step into another zero-sum extensive form game.", "summary_of_the_review": "I vote for this paper to be accepted. Apart from a lack of polish, there are no glaring errors in the paper, and the key ideas in the paper are easy to follow and appreciate. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L9Z9EJMBuGX", "reviewer": "Reviewer_SWZo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main idea of the submission is somewhat obvious. However, I think it nevertheless offers value to the community, as opponent exploration is both an important and an under-explored research area (at least in my opinion). There are some small problems with the submission (see below) that I would like to see addressed. More generally, I like to see the authors put into the quality of the writing. As it currently stands, much of it is sloppy as does not read like a publication-ready conference paper.\n\n### Exploitability Theory\nI think the exploitability results are a bit confusing as currently written. The term \"exploitability\" is not generally used in a way that depends on the opponent's \"true distribution\". Exploitability defines a worst case loss. Unless I am misunderstanding something, the submission is talking about a worst case loss, subject to a constraint on the private information. I am not sure it is appropriate to refer to this quantity as exploitability --- SES is not, in fact, safe against arbitrary opponents.\n\nThe submission provides a nice example illustrating why its approach is superior to simply mixing between a safe strategy and an exploitation strategy. That being said, it seems to me to be perfectly possible to provide theorems analogous to Theorem 1 and Theorem 2 for the \"mixing between a safe strategy and an exploitation strategy\" approach. I think it would add value to the submission to work through these results, as it may be interesting to compare them to Theorem 1 and Theorem 2.\n\n\n### Baselines\nThe submission dismisses Johanson 2007 and Ganzfried 2015 as baselines. However, I am not sure that this dismissal is well justified. The method in the submission already uses an estimate of the opponent strategy. It would be relatively to substitute this estimate for the \"known\" component of the strategy required by restricted Nash response (RNR) and test the exploitability. It may be that RNR performs perfectly well in this case. Also, while I do not dispute it is difficult to scale LP solvers to large games, the games considered in the submission are not that large. Therefore, it seems like both Johanson and Ganzfried offer reasonable baselines for the algorithm proposed in the submission.\n\n### Small Problems\n\nPaper cites benchmark Hanabi paper for superhuman Hanabi performance?\n\nPaper cites Tian for superhuman bridge performance?\n\n“Monte Carlo tree search (MCTS) can be viewed as a powerful policy improvement operator.” \nThis sentence appears to be (hopefully accidentally) plagiarized from the AlphaGo Zero paper: “MCTS may therefore be viewed as a powerful policy improvement operator”.\n\nPoorly constructed “They both have sounded monotonic improvement guarantees in theory, and show tremendous performance promotion empirically.”\n\n“In fully-cooperative imperfect information games, search algorithms proposed in Tian et al. (2020b) and Lerer et al. (2020) are also proved to never be detrimental to the current policy”\nThis is only half true. Lerer et al.’s “never detrimental” is only asymptotic. After any finite amount of time (ie in all practical cases) there is no such guarantee.\n\n“However, it may be overly conservative confronted with opponents with limited rationality and fail to take advantages of their weaknesses to obtain higher rewards.”\nIt has nothing to reference (should be they) \nAdvantages is wrong grammatical number\n\n“We construct a new gadget game to optimize this objective, which enable”\n\n“Search techniques are proven to be essential in developing strong AI strategies”\nThis claim appears overly strong.\n\n“Libratus (Brown et al., 2018) is the first superhuman poker AI which is considered the milestone in the research of imperfect information games”\nThis sentence is both grammatically incorrect and unnecessarily contentious. Does it add value to the paper to make a claim about which poker AI algorithm (between Libratus and DeepStack) was the first and which is considered the “milestone”? Also, is it appropriate to not even cite DeepStack here?\n\n“search algorithms for subgame refinement have also shown promise in improving joint strategies in cooperative imperfect information games such as Hanabi (Bard et al., 2020)”\nThe paper being cited here does not involve sublime refinement.\n\n“In that paper, Johanson et al. (2007) assumes that the”\nassume\n\n“But Ganzfried & Sandholm (2015a) relies on LP solver”\nrely\n\n“It is worthwhile mentioning that there also have been extensive research”\nhas\n\n“However, this paper only only focuses”\nfix\n\nNotation Section:\nIt’s bad form to start sentences with symbols.\n\nIt’s pretty unusual for EFGs to use \\sqsubseteq the way the submission defines it.\nHaving read further it appears that the submission uses \\sqsubseteq the way it is normally used for EFGs. So the definition is incorrect.\n\nIn the matrix game shown in Table 1, there are two NEs.\nAny interpolation of the two NE the submission gives is also a NE.\n\nThroughout the paper Safe Subgame Exploitation is improperly capitalized.", "summary_of_the_paper": "The submission proposes performing safe opponent exploitation via decision-time planning using a novel gadget game. At the top of the gadget game, there is a chance node that goes to the maxmargin gadget game with probability (1 - alpha) and goes to the estimate posterior over private information with probability alpha. The submission proves that, for small enough alpha and posterior error, this gadget game produces a safe (non-exploitable) strategy. The submission presents experiments on Leduc Hold'em and Flop Hold'em Poker.", "summary_of_the_review": "I would like the authors to address the comments above. Should they do so, I am willing to reconsider my score.\n\n---\n\nAfter discussions with the authors, I raised my score from a 5 to an 8.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents tackles the problem of finding strategies that are -- unlike Nash which is safe -- both safe (non-exploitable, to some extent) and able to exploit the opponent. The proposed solution is a convex combination of exploitation and safety that is efficient to compute. Overall, the paper is borderline. Given that the objective and its analysis are not especially surprising, a lot rides on the thoroughness of the empirical results, which could be improved.
Decision: Reject