Year: 2021

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 algorithm enables computationally efficient online adaptations to 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 at the same time. It is also much more efficient than previous safe exploitation baselines.

heading: 1 INTRODUCTION
text: Behind the recent breakthroughs of superhuman AIs in Go (Silver et al., 2016; 2017; Schrittwieser et al., 2020), heads-up no-limit Texas hold’em (HUNL) (Brown et al., 2018; Moravcík et 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 to 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 & Sandholm, 2017; Burch et al., 2014a). They are both theoretically sounded and empirically powerful. In fully-cooperative imperfect information games, the search algorithm proposed in Tian et al. (2020b) is proved to never be detrimental to the current policy. Lerer et al. (2020) also ensures original performance asymptotically.
In zero-sum games, NE-based search algorithms (Burch et al., 2014a; Moravcik 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 to obtain higher rewards (McCracken & Bowling, 2004; Johanson et al., 2007; Li & Miikkulainen, 2018). From the other perspective, there have been extensive studies on opponent exploitation to address the problem. Some typical works (Carmel & Markovitch, 1996; Billings et al., 2003; Gilpin & Sandholm, 2006; Li & Miikkulainen, 2018) model the opponent’s strategy based on previous observations and then search for a 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 are computationally inefficient in an online setting where the opponent model is being updated continuously with streamed data.
In this paper, we study the dilemma of safety and opponent exploitation and present a 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
computationally efficient online adaptations to a continuously changing opponent model, which is hard to address by previous safe exploitation algorithms. The safety criterion requires the refined strategy to stay close to 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 a novel maximization objective which combines the safety objective and exploitation, controlled by the exploitation level α. We construct a new gadget game to optimize this objective, which enables our method’s scalability to large games such as Texas Hold’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.

heading: 2 RELATED WORK
text: This paper investigates the problem of safe opponent exploitation in two-player zero-sum imperfect information games. We propose a 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 in developing strong AI 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 a 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 as the blueprint strategy. Unsafe search (Billings et al., 2003; Ganzfried & Sandholm, 2015b; Gilpin & Sandholm, 2006; 2007) estimates the subgame reach probability assuming the opponent follows blueprint, and searches for a refined subgame strategy. Subgame resolving (Burch et al., 2014a) 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 a gadget game and achieve safety by providing the opponent with the option not entering the current subgame. DeepStack (Moravcík et al., 2017) and Libratus (Brown et al., 2018) build strong poker AIs 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, 2018) typically model the opponent’s strategy based on previous observations and then search for a 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) to 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 a p-RNR to σfix is 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, p-RNR 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).
Ganzfried & Sandholm (2015a) study safe exploitation strategies in repeated games, which is a 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 ε-safe best response for the whole game at each iteration with LP. This procedure is one of the main limitations on the algorithm’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.
It is 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 to model others from one’s own policy. Rabinowitz et al. (2018) uses meta learning to predict strategies of different kinds of agents.

heading: 3 NOTATIONS AND BACKGROUND
text: An extensive-form imperfect information game G = (P,H,Z,A, χ, ρ, ·, σc, u, I) describes sequential interactions among agents, where agents have private information. A finite set P consists of n players and a chance node c which represents the stochastic nature of the environment. The set of non-terminal decision nodes is denoted as H , and Z is a set of terminal nodes, or leaves. The set of possible actions is A, and χ : H → 2|A| is a function which assigns to each decision node h ∈ H a set of legal actions. A player function ρ : H → P assigns to each decision node a player p ∈ P who acts at that node. If action a leads from h to h′, we write h · a = h′. If there exists a sequence of actions leading from h to h′, we write h v h′. At each node h ∈ H , the acting player p = ρ(h) picks an action from legal actions a ∈ χ(h), and leads node h into its child h · a. The chance node always samples an action from its own distribution σc, which is common knowledge to all players. Utility functions are u = (u1, u2, . . . , un), where ui : Z → R defines the utility of player i at terminal node z ∈ Z. The nature of imperfect information is characterized by infosets I = (I1, I2, . . . , In), where Ii = (Ii,1, . . . , Ii,ki) is 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 I(h) to denote the infoset that h belongs to. A player p cannot distinguish between states h1 and h2 if I(h1) = I(h2), and thus should behave identically on all states in the same infoset.
The strategy of a player p is σp : Ip ×A→ R, where σp(I, a) is a distribution over valid actions on infoset I . For simplicity, we also use σp(h, a) to denote σp(I(h), a). We use πσ(h) to denote the probability of reaching state h from the root when agents choose a strategy profile σ = 〈σ1, σ2, . . . , σn〉. Formally, πσ(h) = ∏ h′·avh σρ(h′)(h ′, a). We use πσ−p(h) = ∏ h′·avh∧ρ(h′) 6=p σρ(h′)(h
′, a) to denote the probability of reaching h when player p always chooses the action that leads to h whenever possible. πσ(h, h′) is the reaching probability of h′ from h. πσ(h · a, h′) is the the probability of reaching h′ from h if action a is taken at h. These probabilities can be formally defined in a similar manner.
The expected utility of player p given strategy profile σ is uσp = ∑ z∈Z π
σ(z)up(z). The counterfactual value vσp (I, a) is the expected utility that player p will obtain after taking action a at infoset I , given the joint policy profile is σ. Mathematically, it is the weighted sum of expected values at all states h ∈ I .
vσp (I, a) =
∑ h∈I,z∈Z π σ −p(h)π
σ(h · a, z)up(z)∑ h∈I π σ −p(h)
(1)
In the rest of the paper, we focus on two-player zero-sum games with perfect recall. Zero-sum means ∀z ∈ Z, u1(z) + u2(z) = 0. Perfect recall means that no player will forget the information which has been obtained previously in the game. This is a common assumption in related literature.
A best response strategyBRp(σ−p) = arg maxσp u 〈σp,σ−p〉 p for player p is the strategy that maximize his own expected utility against fixed opponent strategy σ−p. The exploitability of strategy σp is exp(σp) = u σ∗ p − u 〈σp,BR−p(σp)〉 p where σ∗ is the optimal strategy, and is an NE in two-player zero-sum games. It measures the performance of σp against its best response comparing with the NE. A counterfactual best response CBRp(σ−p) is a strategy where σp(I, a) > 0 if and only if vσp (I, a) ≥ maxb vσp (I, b). Counterfactual best response is a best response, but not vice versa. The counterfactual best response value CBV σ−pp (I) = v 〈CBRp(σ−p),σ−p〉 p is the expected utility of the counterfactual best response policy. Since we focus on two-player zero-sum games, we will use CBV σp(I) as a shorthand notation for CBV σp−p (I).
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.
Definition 1. An imperfect information subgame S is a 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.

heading: 4 METHOD
text: 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 σ be the precomputed blueprint strategy. Without loss of generality, assume we search for player 2’s refined strategy σS2 by applying SES to all subgames S ∈ S. Finally, the refined strategy for P2 after search is σ′2, which is the same as σ2 in {Ii2|∀S ∈ S, Ii2 /∈ S} and is replaced with σS2 in S ∈ S.

heading: 4.1 SAFE EXPLOITATION SEARCH
text: Our algorithm offers a unified approach to balance between these two demands with theoretical guarantees. The objective of our search algorithm is to find a new subgame strategy σS2 for S ∈ S which maximizes
SE(σS2 ) = α ∑
Ij1∈Stop
p̂(Ij1) ( vσ1 (I j 1)− CBV σS2 1 (I j 1) )
+ (1− α) min Ij1∈Stop
( vσ1 (I j 1)− CBV σS2 1 (I j 1) ) ,
(2) where α ∈ [0, 1] is a hyper-parameter controlling the exploitation level, and p̂(Ii1) is the estimated probability of player 1 entering infoset Ij1 ∈ Stop. Given P2’s strategy (which is the blueprint σ2) and P1’s actual strategy (which does not have to be the blueprint σ1), the real probability of player 1 entering infoset Ij1 ∈ Stop (which we denote as p(I j 1)) is determined. p̂(I i 1) is just an estimation of p(Ij1). For instance, in poker, it is the estimated distribution of private cards player 1 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 a balance between opponent exploitation and safety, controlled by exploitation level α. The first part of the objective is maximized when ∑ Ij1∈Stop p̂(Ij1)CBV σS2 1 (I j 1) is minimized. It aims at finding a strategy σ S 2 which results in the lowest value for P1 under the assumption that the reach probabilities is p̂. It can be interpreted as 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 margin minIj1∈Stop ( vσ1 (I j 1)− CBV σS2 1 (I j 1) )
(Moravcik et al., 2016) which can be regarded as the 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 α, (2) accuracy of
opponent modeling, and (3) strength of the blueprint strategy impact the theoretical bound. By gradually increasing α from 0 to 1, our algorithm tends to exploit rather than keeping safety.
Theorem 1. (safety) Let S be a disjoint set of subgames S. Let σ∗ = 〈σ∗1 , σ∗2〉 be the NE where P2’s strategy is constrained to be the same with σ2 outside S. Define ∆ = maxS∈S,Ii1∈Stop |CBV σ∗2 1 (I i 1)− vσ1 (I i 1)|. Let p̃(Ii1) be the reach probability given by σ∗1 . Let p̂(Ii1) be the estimation of reach probability p(Ii1) given by the real opponent strategy. Define τ = maxS∈S,Ii1∈Stop | p̂(Ii1)−p̃(I i 1) p̃(Ii1) |. Whenever 1− (2τ + 1)α > 0, we have a bounded exploitability given by:
exp(σ′2) ≤ exp(σ∗2) + 2
1− (2τ + 1)α ∆. (3)
Recall that σ′2 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 to differ from σ2 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(σ′2) ≤ exp(σ∗2)+2∆. Comparing these two results, we can interpret the term 2/(1− (2τ + 1)α) as the additional risk introduced by exploiting the opponent. If exploitation level α = 0, then our bound is as tight as that of maxmargin search (Moravcik et al., 2016). The bound also gets tighter if the τ gets smaller, or the blueprint σ2 is closer to σ∗2 .
Theorem 2. (opponent exploitation) Let = ‖p̂−p‖1 be the L1 distance of the distribution p(Ii1) and p̂(Ii1). Let η = minS∈S maxIj1∈Stop ( CBV1(I j 1 , σ S 2 )− CBV1(I j 1 , σ ∗ 2) ) ≥ 0. We use BR[S,σp]p (σ) to denote the strategy for player p which maximizes its utility in subgame S ∈ S against σ−p under the constraint that BR[S,σp]p (σ) and σp differs only inside S. By maximizing objective 2, for all S ∈ S, the refined strategy σ′2 satisfies
u
〈 BR
[S,σ1] 1 (σ ′ 2),σ ′ 2 〉 2 (S) ≥ u 〈 BR [S,σ1] 1 (σ ∗ 2 ),σ ∗ 2 〉 2 (S) +
1− α α (η − 2∆)− η (4)
The proof is provided in Appendix A. Observe that the reach probability p is characterized by P1’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 BR[S,σ1]1 (σ′2)) as well, opponent exploitation refers to adapting to P1’s strategy σ1 outside S. This theorem implies that the utility of the new strategy σ′2 is lower bounded by the utility of σ ∗ 2 when both confronted with P1’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 σ2 is closer to σ∗2 . We show empirically how exploitation level α and estimation error impact both safety and exploitation abilities in section 5.

heading: 4.2 GADGET GAME
text: In order to find σS2 which maximize objective 2, a straight-forward method is to reformulate the maximization problem as a Linear Programming problem (Moravcik et al., 2016). However, LP solvers (Koller et al., 1994) cannot handle large-scale problems. Alternatively, inspired by Moravcik et al. (2016), we create a gadget game and then apply iteration-based NE algorithms such as CFR (Zinkevich 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 in it is exactly the solution to the original optimization problem.
As shown in Figure 1, 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, we construct a P1 node to let P1 choose an infoset Ii1 to enter. The following chance node samples a specific state with probability proportional to πσ−1(h) for all h ∈ I1. (iii) For the right part, create a chance node sampling an infoset Ii1. The following chance node again samples a specific state with probability
proportional to πσ−1(h) for all h ∈ I1. (iv). Shift the utility of the gadget game by vσ1 (Ii1). The details are described below.
1. The chance node at the top goes to the left part with probability 1 − α, and the right part with probability α. 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 σS2 will be the same for both parts. Since σS1 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.
2. We subtract u1(z) by vσ1 (I i 1) for all z v h, h ∈ Ii1, and add u2(z) by vσ1 (Ii1) in order to keep the subgame zero-sum. By doing so, the objective of a Nash Equilibrium of p2 will change from maximizing −CBV σ S 2
1 (I i 1) to maximizing v σ 1 (I i 1)− CBV σS2 1 (I i 1).
3. As for the left part of the gadget game, the P1 node on the second level in Figure 1 enables P1 to enter an arbitrary infoset Ii1. Since this is a zero-sum game, in an NE strategy, he will enter the one with lowest vσ1 (I i 1) − CBV1(Ii1, σ∗2) which is exactly the minimization in the second term of SE(σS2 ).
4. The chance node on the second level of the right part will sample an infoset Ii1 according to reach probability p̂(Ii1). So that the NE objective of this part is exactly the summation in the first term of SE(σS2 ).

heading: 4.3 MATRIX GAME
text: In this part, we offer a matrix game as an 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− α. In the matrix game shown in Table 1, let’s consider two specific NEs. In both NEs, P1 will play L/M 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 P1 plays a rather weak strategy that he will only play action R. We apply SES to search for P2’s refined strategy.
When the estimation of opponent strategy is accurate such that p̂ = p, the best response of P2 is always playing F, which is highly exploitable, while SES finds the second NE under proper α. 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 at 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 to utilize such gift strategy. Strategy σ−p is a Gift Strategy if it is not a best response to a NE strategy σ∗p . Therefore, we can switch to σ ∗ p to get better performance against σ−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.

heading: 5 EXPERIMENT
text: 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 a 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 a search algorithm’s safety, while head-to-head 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 C for implementation details.

heading: 5.1 OPPONENTS
text: In our experiments, we test the performance of our algorithm against opponents of various strengths. For both Leduc Poker and FHP, we create 3 types of opponents with 3 random seeds each. The first type of opponent is an approximation of NE in the full game, and is regarded as a strong opponent. It is computed in the same way as the blueprint strategy with different seed. For the second and third type of opponents, we enumerate every infoset in the blueprint strategy and shift the action distribution randomly with probability Prshuffle = 0.3 or 0.7. We multiply the probability of each action by a random variable from Uniform(0, 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 Prshuffle = 0.7, the strategy keeps close to NE with average L1 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.

heading: 5.2 SAFE OPPONENT SEARCH
text: In Figure 3, we demonstrate the head-to-head evaluation performances and corresponding exploitability of the refined strategies found by SES against opponents of various strengths, under different exploitation level α and estimation errors of opponent’s strategy. Different lines in each plot refers to corresponding estimation error , which is the L1 distance of p̂ and p. We evaluate our refined
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 α helps win more chips from opponents, while resulting in the increase of the strategy’s own exploitability. As can be seen in Figure 3, the exploitability increases when the exploitation level α grows from 0 to 1, which is consistent with Theorem 1. One exception is in FHP when is 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 p̂ close to p̃ when is small, which means the τ in Theorem 1 is small. As a 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 ( = 0.0, the yellow line), the expected payoff in FHP increases as the exploitation level α grows higher. In Leduc poker, since the game is very small, the pre-computed blueprint is very close to NE. Therefore, when confronted with relatively strong opponents (Prshuffle = 0.0, 0.3) which are also close to NE, actually few things can be done other
than sticking with the blueprint. So the improvement introduced by SES is small. When facing relatively weak opponent (Prshuffle = 0.7), the improvement margin is slightly larger.
SES relies on an estimation of opponent’s strategy. In order to test the robustness of our algorithm when the prediction of p(Ii1) 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 grows larger. The result is expected since an accurate estimation always provides benefits. However, it also demonstrates that SES can still achieve a trade-off between safety and opponent exploitation even when is considerably high. For instance, in FHP, is between 0 and 2, and = 1.2 means that the predicted distribution is almost random. When ≤ 0.6, the expected payoff still keeps increasing with respect to α. In case of a bad estimation, we can always choose smaller α to ensure safety.

heading: 5.3 COMPARISON WITH RESTRICTED NASH RESPONSE
text: We also compare SES with restricted Nash response (RNR) (Johanson et al., 2007) in FHP. In each round, we limit the computation time of RNR(normal) to 10 CPU second1, which is the same for SES. However, as stated in section 2, RNR needs to recompute a strategy for the whole game in each round. It cannot converge in 10s. So we also compare with RNR(big), which has a 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.

heading: 6 CONCLUSION
text: 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 1 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 α is now regarded as a hyperparameter in our algorithm. However, ideally, α should be learnt automatically from opponents, and should be adaptive to opponent’s strategy change. We leave this for future work.
1We test it on Intel(R) Xeon(R) Platinum 8276L CPU @ 2.20GHz

heading: A PROOFS

heading: A.1 PROOF OF THEOREM 1
text: Theorem 1. (safety) Let S be a disjoint set of subgames S. Let σ∗ = 〈σ∗1 , σ∗2〉 be the NE where P2’s strategy is constrained to be the same with σ2 outside S. Define ∆ = maxS∈S,Ii1∈Stop |CBV σ∗2 1 (I i 1)− vσ1 (I i 1)|. Let p̃(Ii1) be the reach probability given by σ∗1 . Let p̂(Ii1) be the estimation of reach probability p(Ii1) given by the real opponent strategy. Define τ = maxS∈S,Ii1∈Stop | p̂(Ii1)−p̃(I i 1) p̃(Ii1) |. Whenever 1− (2τ + 1)α > 0, we have a bounded exploitability given by:
exp(σ′2) ≤ exp(σ∗2) + 2
1− (2τ + 1)α ∆. (5)

heading: Proof:
text: For simplicity, we will omit the subscript of CBV σ ∗ 2
1 by default. In order to prove Theorem 1, we will use mathematical induction on the level of the infoset. The depth L has the same definition as in Brown & Sandholm (2017), i.e.
• 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) = 0. • For any infosets that are ancestors of the subgames, we define L(I) = maxI′∈succ(I) L(I ′) + 1. That is, it has a higher level than any of its successors.

heading: BASE CASE OF INDUCTION
text: Firstly, we will prove that for any infoset with level 0, the inequality of theorem 1 holds. For convenience, we consider that theorem 1 in a specific subgame S. We will prove the infoset at the top of the subgame first. Since SE(σ∗2) ≥ (1 − α)(−∆) + α ∑ i p̂(I i 1)(−∆) = −∆, we have
(1− α) min Ij1
( vσ1 (I j 1)− CBV σ S 2 (Ij1) ) + α ∑ i p̂(Ii1)(v σ 1 (I i 1)− CBV σ S 2 (Ii1))
=SE(σS2 ) ≥SE(σ∗2) ≥−∆
(6)
since σS2 = arg maxσ̃2 SE(σ̃2).
Furthermore, we have∑ i p̂(Ii1)(v σ 1 (I i 1)− CBV σ S 2 (Ii1))
= ∑ i p̂(Ii1)(v σ 1 (I i 1)− CBV σ ∗ 2 (Ii1)) + ∑ i p̂(Ii1)(CBV σ∗2 (Ii1)− CBV σ S 2 (Ii1))
≤∆ + ∑ i p̂(Ii1)(CBV σ∗2 (Ii1)− CBV σ S 2 (Ii1))
=∆ + ∑ i p̃(Ii1)(CBV σ∗2 (Ii1)− CBV σ S 2 (Ii1))
+ ∑ i (p̂(Ii1)− p̃(Ii1))(CBV σ ∗ 2 (Ii1)− CBV σ S 2 (Ii1))
(7)
where the second term ∑ i p̃(I i 1)(CBV σ∗2 (Ii1) − CBV σ S 2 (Ii1)) is no larger than 0 because∑
i p̃(I1)CBV σ∗2 (Ii1) is exactly what σ ∗ 2 minimized. Otherwise, σ ∗ 2 can change the strategy in
the subgame so that he will get higher reward against σ∗1 which conflicts the definition of NE.
And we will further decompose Ii1 ∈ Stop into two parts, {I i,− 1 } and {I i,+ 1 }. They have the property that CBV σ ∗ 2 (Ii,−1 ) − CBV σ S 2 (Ii,−1 ) ≤ 0 and CBV σ ∗ 2 (Ii,+1 ) − CBV σ S 2 (Ii,+1 ) > 0. And since∑
i p̃(I i 1)(CBV σ∗2 (Ii1)− CBV σ S 2 (Ii1)) ≤ 0 as discussed above, we have∑
Ii,−1
p̃(Ii1)(CBV σ∗2 (Ii,−1 )− CBV σ S 2 (Ii,−1 )) + ∑ Ii,+1 p̃(Ii1)(CBV σ∗2 (Ii,+1 )− CBV σ S 2 (Ii,+1 ))
= ∑ i p̃(Ii1)(CBV σ∗2 (Ii1)− CBV σ S 2 (Ii1))
≤0
(8)
which implies that∑ Ii,+1 p̃(Ii1)(CBV σ∗2 (Ii,+1 )−CBV σ S 2 (Ii,+1 )) ≤ − ∑ Ii,−1 p̃(Ii1)(CBV σ∗2 (Ii,−1 )−CBV σ S 2 (Ii,−1 )) (9)
Then we have ∑ i (p̂(Ii1)− p̃(Ii1))(CBV σ ∗ 2 (Ii1)− CBV σ S 2 (Ii1))
= ∑ Ii,−1 (p̂(Ii,−1 )− p̃(I i,− 1 ))(CBV σ∗2 (Ii,−1 )− CBV σ S 2 (Ii,−1 ))
+ ∑ Ii,+1 (p̂(Ii,+1 )− p̃(I i,+ 1 ))(CBV σ∗2 (Ii,+1 )− CBV σ S 2 (I Ii,+1 1 ))
≤τ ( − ∑ Ii,−1 p̃(Ii,−1 )(CBV σ∗2 (Ii,−1 )− CBV σ S 2 (I Ii,−1 1 ))
+ ∑ Ii,+1 p̃(Ii,+1 )(CBV σ∗2 (Ii,+1 )− CBV σ S 2 (I Ii,+1 1 )) ) ≤− 2τ
∑ Ii,−1 p̃(Ii,−1 )(CBV σ∗2 (Ii,−1 )− CBV σ S 2 (I Ii,−1 1 ))
≤− 2τ min Ij1
( CBV σ
∗ 2 (Ij1)− CBV σ S 2 (Ij1)
)
(10)
The last inequation holds since minIj1
( CBV σ
∗ 2 (Ij1) − CBV σ S 2 (Ij1) ) ≤ 0 since σ∗2 is the strategy
with lowest exploitability by only changing strategy of σ2 in the subgames.
Back to Equation 7, we have∑ i p̂(Ii1)(v σ 1 (I i 1)− CBV σ S 2 (Ii1)) ≤ ∆− 2τ min Ij1 ( CBV σ ∗ 2 (Ij1)− CBV σ S 2 (Ij1) ) (11)
And substitute it into Equation 6,
∆ + (1− α− 2ατ) min Ij1
( CBV σ
∗ 2 (Ij1)− CBV σ S 2 (Ij1) ) ≥(1− α) min
Ij1
( vσ1 (I j 1)− CBV σ S 2 (Ij1) ) + α(∆− 2τ) min
Ij1
( CBV σ
∗ 2 (Ij1)− CBV σ S 2 (Ij1) ) ≥−∆ (12)
so that CBV σ
S 2 (Ij1) ≤ CBV σ ∗ 2 (Ij1) +
2
1− (2τ + 1)α ∆ (13)
for all Ij1 in the subgame.
And for infoset I out of the subgame with level 0, since the refined strategy σS2 and blueprint strategy σ2 are the same here, the CBV value is exactly the same and the inequality holds.

heading: INDUCTIVE STEP
text: The inductive step mostly follows that of Brown & Sandholm (2017).
Since CBV σ S 2 (I1) ≤ CBV σ ∗ 2 (I1) + 2 1−(2τ+1)α∆ holds for every subgame S, σ ′ 2 will also satisfy this inequation since ∆ and τ are defined as maximum over all subgames.
Now, suppose CBV σ ′ 2(I1) ≤ CBV σ ∗ 2 (I1) + 2 1−(2τ+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 CBV (I1), CBV σ2(I1, a) = ( ∑ h∈I1 πσ2−1(h)v 〈CBR(σ2),σ2〉(h · a) ) / ∑ h∈I1 πσ2−1(h)
= ( ∑ h∈I1 πσ2−1(h) ∑ h′∈succ(h,a) πσ2−1(h, h ′)v〈CBR(σ2),σ2〉(h′) ) / ∑ h∈I1 πσ2−1(h)
= ( ∑ h∈I1 ∑ h′∈succ(h,a) πσ2−1(h ′)v〈CBR(σ2),σ2〉(h′) ) / ∑ h∈I1 πσ2−1(h)
(14)
We can swap the two summations above since the game is perfect recall, then CBV σ2(I1, a) = ( ∑ I′1∈succ(I1,a) ∑ h′∈I′1 πσ2−1(h ′)v〈CBR(σ2),σ2〉(h′) ) / ∑ h∈I1 πσ2−1(h) (15)
By substituting the definition of CBV (I ′1) into the equation above, CBV σ2(I1, a) = ( ∑ I′1∈succ(I1,a) CBV σ2(I ′1) ∑ h′∈I′1 πσ2−1(h ′) ) / ∑ h∈I1 πσ2−1(h) (16)
And by the induction hypothesis, CBV σ2(I1, a) ≤ ( ∑ I′1∈succ(I1,a) (CBV σ ∗ 2 (I ′1) + 2− α 1− α ∆) ∑ h′∈I′1 πσ2−1(h ′) ) / ∑ h∈I1 πσ2−1(h) (17)
Because I1 is out of the subgame and σ∗2 , σ2 is exactly the same outside the subgame, we will get CBV σ2(I1, a) ≤ ( ∑ I′1∈succ(I1,a) (CBV σ ∗ 2 (I ′1) + 2− α 1− α ∆) ∑ h′∈I′1 π σ∗2 −1(h ′) ) / ∑ h∈I1 π σ∗2 −1(h)
= CBV σ ∗ 2 (I1, a) + 2− α 1− α ∆ ( ∑ I′1∈succ(I1,a) ∑ h′∈I′1 π σ∗2 −1(h ′) ) / ∑ h∈I1 π σ∗2 −1(h)
= CBV σ ∗ 2 (I1, a) + 2− α 1− α ∆
(18)
Finally, by mathematical induction we get
exp(σ′2) ≤ exp(σ∗2) + 2
1− (2τ + 1)α ∆ (19)

heading: A.2 PROOF OF THEOREM 2
text: Theorem 2. (opponent exploitation) Let = ‖p̂−p‖1 be the L1 distance of the distribution p(Ii1) and p̂(Ii1). Let η = minS∈S maxIj1∈Stop ( CBV1(I j 1 , σ S 2 )− CBV1(I j 1 , σ ∗ 2) ) ≥ 0. We use BR[S,σp]p (σ) to denote the strategy for player p which maximizes its utility in subgame S ∈ S against σ−p under the constraint that BR[S,σp]p (σ) and σp differs only inside S. By maximizing objective 2, for all S ∈ S, the refined strategy σ′2 satisfies
u
〈 BR
[S,σ1] 1 (σ ′ 2),σ ′ 2 〉 2 (S) ≥ u 〈 BR [S,σ1] 1 (σ ∗ 2 ),σ ∗ 2 〉 2 (S) +
1− α α (η − 2∆)− η (20)
Proof: Still, we only consider a specific subgame S first.
σS2 is maximizing
(1− α) min Ij1
( vσ1 (I j 1)− CBV σ S 2 (Ij1) ) ︸ ︷︷ ︸
g(σS2 )
+α ∑ i p̂(Ii1)(v σ 1 (I i 1)− CBV σ S 2 (Ii1))︸ ︷︷ ︸
f(σS2 )
(21)
So, we have
(1− α)g(σS2 ) + αf(σS2 ) ≥ (1− α)g(σ∗2) + αf(σ∗2) (22)
and
max Ij1
CBV (Ij1 , σ S 2 )− CBV (I j 1 , σ ∗ 2) = η ≥ η
⇔g(σS2 )−∆ ≤ −η ⇔g(σS2 )−∆ ≤ ∆ + g(σ∗2)− η (g(σ∗2) ≥ −∆)
(23)
Therefore,
αf(σS2 ) ≥ αf(σ∗2) + (1− α)(η − 2∆) (24)
which means∑ i p̂(Ii1)(CBV σ∗2 (I1)− CBV σ S 2 (Ii1))
≥ 1− α α (η − 2∆) + ∑ i p̂(Ii1)(CBV σ∗2 (I1)− CBV σ ∗ 2 (Ii1))
⇔− ∑ i p̂(Ii1)CBV σS2 (Ii1) ≥ 1− α α (η − 2∆)− ∑ i p̂(Ii1)CBV σ∗2 (Ii1)
⇔− ∑ i p(Ii1)CBV σS2 (Ii1) ≥ 1− α α (η − 2∆)− ∑ i p(Ii1)CBV σ∗2 (Ii1)
− ∑ i (p(Ii1)− p̂(Ii1))(CBV σ S 2 (Ii1)− CBV σ ∗ 2 (Ii1))
⇒− ∑ i p(Ii1)CBV σS2 (Ii1) ≥ 1− α α (η − 2∆)− ∑ i p(Ii1)CBV σ∗2 (Ii1)− η
⇔ ∑ i p(Ii1)V2(I i 1, BR(σ S 2 ), σ S 2 ) ≥ 1− α α (η − 2∆)− η + ∑ i p(Ii1)V2(I i 1, BR(σ ∗ 2), σ ∗ 2)
⇔u〈BR [S,σ1] 1 (σ
[S←σS2 ] 2 ),σ [S←σS2 ] 2 〉
2 (S) ≥ u 〈BR[S,σ1]1 (σ ∗ 2 ),σ ∗ 2 〉 2 (S) + 1− α α (η − 2∆)− η
(25)
Since η is defined as minimum over all subgames, we have
u
〈 BR
[S,σ1] 1 (σ ′ 2),σ ′ 2 〉 2 (S) ≥ u 〈 BR [S,σ1] 1 (σ ∗ 2 ),σ ∗ 2 〉 2 (S) +
1− α α (η − 2∆)− η (26)

heading: B POKER RULES

heading: RULES OF LEDUC POKER
text: Leduc Poker is a two players game. In Leduc Poker, there are 6 cards in total, three ranks({J,Q,K}) with two suits({a, b}) each. And at the beginning, every player should put 1 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
when a player call, he has to put chips in the pot to 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 a player calls.
Leduc Poker is divided into two betting rounds. In the first round, a private card is dealt to each player and then two player start to bet. After the first betting round ends and nobody folds, a public 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 a player’s private card has the same rank as the public card, then he wins. Otherwise, we have J < 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.

heading: RULES OF FLOP HOLD’EM POKER
text: The rules of Flop Hold’em Poker is similar to that of Leduc Poker. In FHP, we use the standard 52-card deck. At the beginning, the first player will contribute 1 chip to the pot and the second player will contribute 2 chips. And then they will be 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
Leduc Poker. In Leduc Poker, we solve for a blueprint strategy using a variant of CFR algorithm (Lanctot et al., 2009; Tammelin et al., 2015) with 1M iterations in the full game. Then we apply search in subgames when the board card is dealt.
Flop Hold’em 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.

Review summaries:
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.

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.

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").