# Continual Depth-limited Responses for Computing
Counter-strategies in Sequential Games

David Milec, Ondřej Kubíček, Viliam Lisý

###### Abstract

Limited look-ahead game solving for imperfect-information games is the
breakthrough that allowed defeating expert humans in large poker. The existing
algorithms of this type assume that all players are perfectly rational and do
not allow explicit modeling and exploitation of the opponent’s flaws. As a
result, even very weak opponents can tie or lose only very slowly against
these powerful methods. We present the first algorithm that allows
incorporating opponent models into limited look-ahead game solving. Using only
an approximation of a single (optimal) value function, the algorithm
efficiently exploits an arbitrary estimate of the opponent’s strategy. It
guarantees a bounded worst-case loss for the player. We also show that using
existing resolving gadgets is problematic and why we need to keep the
previously solved parts of the game. Experiments on three different games show
that over half of the maximum possible exploitation is achieved by our
algorithm without risking almost any loss.

##  1 Introduction

Researchers aim to solve bigger and bigger games. A breakthrough that allowed
defeating human experts in several large imperfect-information games is
limited look-ahead solving, which adapts a well-known approach from perfect-
information games to games with imperfect-information (Moravčík et al. 2017;
Brown and Sandholm 2019b; Schmid et al. 2021). Limited look-ahead solving
takes advantage of decomposition. It builds the game to some depth and solves
it using a value function that can be learned, for example, by neural
networks. When the depth-limit is reached, we build another part until the
depth-limit and continue until the end of the game.

All the existing algorithms of this type assume perfect rationality of the
opponent and do not allow explicit modeling of an opponent and exploitation of
his mistakes. As a result, even very weak opponents exploitable by the
heuristic local best response (LBR) (Lisy and Bowling 2017) can tie or lose
very slowly against these methods (Zarick et al. 2020). As more and more
computer-generated strategies are deployed in the real world (An et al. 2013)
we can not avoid the interaction of AI systems with humans. Therefore, there
has been a significant amount of work towards computing strategies to use
against imperfect opponents such as humans (Bard et al. 2013; Wu et al. 2021;
Southey et al. 2012; Mealing and Shapiro 2015; Korb, Nicholson, and Jitnah
2013; Milec et al. 2021; Johanson and Bowling 2009). We continue this area of
research and propose the first algorithms that allow opponent modeling in
limited look-ahead solving in imperfect-information games.

First, we propose a continual depth-limited best response (CDBR), which fixes
the opponent and does continual resolving. Assuming we had precise value
function111the Value function takes player’s reaches at the depth limit and
returns the evaluation of the information sets for both players. trained to
return values as if we played against a particular opponent, and the algorithm
would produce the best response (BR). Next, we propose continual depth-limited
restricted Nash response (CDRNR), which is based on restricted Nash response
(RNR) (Johanson, Zinkevich, and Bowling 2008) with modifications to allow
depth-limited solving. Specifically, we need to measure the increase in
exploitability caused by the change in our strategy, which is done by
computing BR in RNR. To do that precisely, we keep all the previously
considered parts of the game and show the problems caused by replacing them
with known gadgets (Burch, Johanson, and Bowling 2014; Moravcik et al. 2016;
Brown and Sandholm 2017).

To avoid training a vast amount of value functions, we use the single
(optimal) value function, which assumes both players act rationally after the
depth limit. As a result, we create algorithms that do not directly compute BR
and RNR but still have favorable theoretical guarantees and practical results.
We propose first algorithms that allow opponent modeling in large extensive-
form games (EFGs). Specifically, CDBR is a generalization of LBR. Compared to
previous approaches using reinforcement-learning (Heinrich and Silver 2016;
Mnih et al. 2013; Timbers et al. 2020), we can quickly compute the response to
an unseen opponent model. Therefore, it is the first algorithm approximating
BR in large games applicable in real-time opponent modeling. CDRNR has no
comparison since no other algorithm is trying to compute robust responses in
large EFGs, making it the first robust response that can be quickly recomputed
for unseen opponent models.

Our contributions are: 1) We formulate the algorithms to find the responses
given opponent strategy and an evaluation function, resulting in the first
robust response applicable to massive games. 2) We prove the soundness of the
proposed algorithms. 3) We empirically evaluate the algorithms on three
different games. We show that our responses exploit the opponents, and CDBR
outperforms domain-specific local best response (Lisy and Bowling 2017) on
poker.

##  2 Background

A two-player extensive-form game (EFG) consist of a set of players
$N=\\{\vartriangle,\triangledown,c\\}$, where $c$ denotes the chance,
$\vartriangle$ is the maximizer and $\triangledown$ is the minimizer. $A$ is a
finite set of all actions available in the game. $H\subset\\{a_{1}a_{2}\cdots
a_{n}\mid a_{j}\in A,n\in\mathbb{N}\\}$ is the set of histories in the game.
We assume that $H$ forms a non-empty finite prefix tree. We use $g\sqsubset h$
to denote that $h$ extends $g$. The root of $H$ is the empty sequence
$\emptyset$. The set of leaves of $H$ is denoted $Z$, and its elements $z$ are
called terminal histories. The histories not in Z are non-terminal histories.
By $A(h)=\\{a\in A\mid ha\in H\\}$ we denote the set of actions available at
$h$. $P:H\setminus Z\to N$ is the player function which returns who acts in a
given history. Denoting $H_{i}=\\{h\in H\setminus Z\mid P(h)=i\\}$, we
partition the histories as $H=H_{\vartriangle}\cup H_{\triangledown}\cup
H_{c}\cup Z$. $\sigma_{c}$ is the chance strategy defined on $H_{c}$. For each
$h\in H_{c},\sigma_{c}(h)$ is a fixed probability distribution over $A(h)$.
Utility functions assign each player utility for each leaf node,
$u_{i}:Z\to\mathbb{R}$. The game is of imperfect information if some actions
or chance events are not fully observed by all players. The information
structure is described by information sets for each player $i$, which form a
partition $\mathcal{I}_{i}$ of $H_{i}$. For any information set
$I_{i}\in\mathcal{I}_{i}$, any two histories $h,h^{\prime}\in I_{i}$ are
indistinguishable to player $i$. Therefore $A(h)=A(h^{\prime})$ whenever
$h,h^{\prime}\in I_{i}$. For $I_{i}\in\mathcal{I}_{i}$ we denote by $A(I_{i})$
the set $A(h)$ and by $P(I_{i})$ the player $P(h)$ for any $h\in I_{i}$.

A strategy $\sigma_{i}\in\Sigma_{i}$ of player $i$ is a function that assigns
a distribution over $A(I_{i})$ to each $I_{i}\in\mathcal{I}_{i}$. A strategy
profile $\sigma=(\sigma_{\vartriangle},\sigma_{\triangledown})$ consists of
strategies for both players. $\pi^{\sigma}(h)$ is the probability of reaching
$h$ if all players play according to $\sigma$. We can decompose
$\pi^{\sigma}(h)=\prod_{i\in N}\pi^{\sigma}_{i}(h)$ into each player’s
contribution. Let $\pi^{\sigma}_{-i}$ be the product of all players’
contributions except that of player $i$ (including chance). For
$I_{i}\in\mathcal{I}_{i}$ define $\pi^{\sigma}(I_{i})=\sum_{h\in
I_{i}}\pi^{\sigma}(h)$, as the probability of reaching information set $I_{i}$
given all players play according to $\sigma$. $\pi_{i}^{\sigma}(I_{i})$ and
$\pi_{-i}^{\sigma}(I_{i})$ are defined similarly. Finally, let
$\pi^{\sigma}(h,z)=\frac{\pi^{\sigma}(z)}{\pi^{\sigma}(h)}$ if $h\sqsubset z$,
and zero otherwise. $\pi^{\sigma}_{i}(h,z)$ and $\pi^{\sigma}_{-i}(h,z)$ are
defined similarly. Using this notation, expected payoff for player $i$ is
$u_{i}(\sigma)=\sum_{z\in Z}u_{i}(z)\pi^{\sigma}(z)$. A best response (BR) of
player $i$ to the opponent’s strategy $\sigma_{-i}$ is a strategy
$\sigma_{i}^{BR}\in BR_{i}(\sigma_{-i})$, where
$u_{i}(\sigma_{i}^{BR},\sigma_{-i})\geq
u_{i}(\sigma^{\prime}_{i},\sigma_{-i})$ for all
$\sigma^{\prime}_{i}\in\Sigma_{i}$. A tuple of strategies
$(\sigma_{i}^{NE},\sigma_{-i}^{NE})$,
$\sigma_{i}^{NE}\in\Sigma_{i},\sigma_{-i}^{NE}\in\Sigma_{-i}$ is a _Nash
Equilibrium_ (NE) if $\sigma_{i}^{NE}$ is an optimal strategy of player $i$
against strategy $\sigma_{-i}^{NE}$. Formally: $\sigma_{i}^{NE}\in
BR(\sigma_{-i}^{NE})\quad\forall i\in\\{\vartriangle,\triangledown\\}$.

In a two-player zero-sum game, the exploitability of a strategy is defined as
the expected utility a fully rational opponent can achieve above the value of
the game. Formally, exploitability $\mathcal{E}(\sigma_{i})$ of strategy
$\sigma_{i}\in\Sigma_{i}$ is
$\mathcal{E}(\sigma_{i})=u_{-i}(\sigma_{i},\sigma_{-i})-u_{-i}(\sigma^{NE}),\quad\sigma_{-i}\in
BR_{-i}(\sigma_{i}).$

We define gain of a strategy against a sub-rational opponent as an expected
utility we receive above the value of the game. Formally, gain
$\mathcal{G}(\sigma_{i},\sigma_{-i})$ of strategy $\sigma_{i}$ against
strategy $\sigma_{-i}$ is defined as
$\mathcal{G}(\sigma_{i},\sigma_{-i})=u_{i}(\sigma_{i},\sigma_{-i})-u_{i}(\sigma^{NE}).$

##### Depth-limited Solving

We denote $H_{i}(h)$ the sequence of player $i$’s information states and
actions on the path to a history $h$. Two histories $h,h^{\prime}$ where
player $i$ does not act are in the same augmented information set $I_{i}$ if
$H_{i}(h)=H_{i}(h^{\prime})$. We partition the game histories into public
states $PS_{i}\subset H$, which are closed under the membership within the
augmented information sets of all players. Trunk is a set of histories
$T\subset H$, closed under prefixes and public states. Subgame $S\subset H$ is
a forest of trees closed under extensions and public states. Range of a player
$i$ is a probability distribution over his information sets in some public
state $PS_{i}$, given we reached the $PS_{i}$. Value function is a function
that takes the public state and both players’ ranges as input and outputs
values for each information set in the public state for both players. We
assume using an approximation of an optimal value function, which is a value
function returning the values of using some NE after the depth-limit. Subgame
partitioning $\mathcal{P}$ is a partitioning that splits the game into trunk
and subgames into multiple different levels based on some depth-limit or other
factors (domain knowledge). Subgame partitioning can be naturally created
using the formalism of factored-observation stochastic games. (Kovařík et al.
2019). We denote by $u_{i}(\sigma)^{T}_{V}$ the utility for player $i$ if we
use strategy profile $\sigma$ in trunk $T$ and compute values at the depth-
limit using value function $V$.

##  3 Continual Depth-limited Responses

This section formally defines the strategies we are computing and the
practical algorithms we use. The pseudo-code of the algorithms is in Algorithm
1.

### Using Only the Optimal Value Function

When we add the opponent model to the depth-limited solving, the exact
solution would require capturing the opponent’s mistakes after the depth-limit
given by the opponent model in the value function. Training the value function
is costly. Hence, it is infeasible for many opponent models and outright
impossible for applications where we do not know the model in advance and
gradually update it after each interaction. We instead explore the effects of
using only the optimal value function. We start from the top of the game and
construct a trunk with a depth-limit. Next, we solve the trunk, using the
value function to evaluate public states at the depth-limit. Then we move
forward to the next public state reached in the game, and we construct a
subgame starting from the public state with some depth-limit. We solve the
depth-limited subgame and continue with the same steps until we reach the end
of the game.

The main problem of depth-limited solving is that when we find the equilibrium
in the subgame, the joined strategy from trunk and subgame together is not
guaranteed to be Nash equilibrium and can be substantially exploitable. To
solve the issue, we can use gadget (Burch, Johanson, and Bowling 2014;
Moravcik et al. 2016; Brown and Sandholm 2017), which adds a structure above
the root of the subgame and using the summary values from previous iterations
guarantees the exploitability will not rise.

Figure 1: Illustration of the depth-limited solving.

### Continual Depth-limited Best Response

Given any extensive-form game $G$ with perfect recall, opponent’s fixed
strategy $\sigma_{\triangledown}^{F}$ and some subgame partitioning
$\mathcal{P}$, we define continual depth-limited best response (CDBR)
recursively from the top, see Figure 1. First we have trunk $T_{1}=T$ and
value function $V$. CDBR in the trunk $T_{1}$ for player $\vartriangle$ with
value function $V$ is defined as
$\sigma_{\vartriangle}^{\mathcal{B}}(\sigma_{\triangledown}^{F})_{V}^{T_{1}}=\operatorname*{arg\,max}_{\sigma_{\vartriangle}}u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown}^{F})_{V}^{T_{1}}$.
In other words, we maximize the utility over the strategy in the trunk, where
we return values from the value function after the depth-limit. In each step
afterwards we create a new subgame $S_{i}$ and create new trunk by joining the
old one with the subgame, creating $T_{i}=T_{i-1}\cup S_{i}$. We fix the
strategy of player $\vartriangle$ in the $T_{i-1}$ and maximize over strategy
in the subgame.
$\sigma_{\vartriangle}^{\mathcal{B}}(\sigma_{\triangledown}^{F})_{V}^{T_{i}}=\operatorname*{arg\,max}_{\sigma_{\vartriangle}^{S_{i}}}u_{\vartriangle}(\sigma_{\vartriangle}^{S_{i}}\cup\sigma_{\vartriangle}^{T_{i-1}},\sigma_{\triangledown}^{F})_{V}^{T_{i}}$.
We continue like that for each step, and we always create a new trunk $T_{i}$
using the strategy from step $T_{i-1}$ until we reach the end of the game. We
denote the full CDBR strategy created by joining strategies from all possible
branches
$\sigma_{\vartriangle}^{\mathcal{B}}(\sigma_{\triangledown}^{F})_{V}^{\mathcal{P}}$.

#### Computing CDBR

The algorithm’s input is the game’s definition and the opponent’s strategy. We
have a fixed solving depth, such that the created subgames can fit in the
memory, and we can solve them in a reasonable time. First, we get the trunk
from the subgame partitioning. We need to compute the best response in the
trunk given the value function, and since the output of the value function
changes when strategy in the trunk changes, we can no longer compute the best
response in one pass as in a full game. We need to use some version of CFR
(Tammelin et al. 2015; Brown and Sandholm 2019a; Farina, Kroer, and Sandholm
2020) and construct the strategy iteratively. Lemma 1 in Section 5 shows that
it converges to the best response in the trunk even if we only keep strategy
from the best iteration without the need to compute the average strategy as in
regular use of CFR.

After we solve the trunk, we move into the subgame, and we use value resolving
without any gadgets because the opponent can not change his strategy in the
trunk. We set the initial reaches in the subgame using player strategies and
chance. We then solve the resulting subgame using depth-limited CFR.

### Continual Depth-limited RNR

Given any extensive-form game $G$ with perfect recall, restricted Nash
response can be computed by solving a modified game (Johanson, Zinkevich, and
Bowling 2008): We add an initial chance node with two outcomes that player
$\vartriangle$ does not observe. We copy the whole game $G$ after both
outcomes of the chance node. In one tree, the opponent plays the fixed
strategy, and we denote it $G^{F}$. The other tree is the same as the original
game; we mark it $G^{\prime}$. Player $\vartriangle$ does not observe the
initial chance node his infosets span over both $G^{\prime}$ and $G^{F}$. We
denote the full modified game $G^{M}$. Parameter $p$ is the initial chance
node probability of picking $G^{F}$. Given the opponent’s fixed strategy
$\sigma_{\triangledown}^{F}$ and some subgame partitioning $\mathcal{P}$ of
$G^{M}$ we define continual depth-limited restricted Nash response (CDRNR)
recursively from the top. First we have trunk $T_{1}^{M}$ using $\mathcal{P}$
and value function $V$. Note that the number and semantic of infosets at the
value function for player $\vartriangle$ remain unchanged, and for
$\triangledown$, inputs and outputs are doubled in size, so the value function
is a bit more complex. CDRNR for player $\vartriangle$ in the trunk
$T_{1}^{M}$ using value function $V$ is
$\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{T_{1}^{M}}=\operatorname*{arg\,max}_{\sigma_{\vartriangle}}u_{\vartriangle}(\sigma_{\vartriangle},BR(\sigma_{\vartriangle}))_{V}^{T_{1}^{M}}$.
And then in every following step we create the new subgame $S_{i}^{M}$ and
enlarge the trunk to incorporate this subgame, creating trunk $T_{i}^{M}$ =
$T_{i-1}^{M}\cup S_{i}^{M}$. Next, we fix strategy
$\sigma_{\vartriangle}^{T_{i-1}^{M}}$ of player $\vartriangle$ in the previous
trunk $T_{i-1}^{M}$ so it can not be changed anymore and the CDRNR is
$\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{T_{i}}=\operatorname*{arg\,max}_{\sigma_{\vartriangle}^{S_{i}^{M}}}u_{\vartriangle}(\sigma_{\vartriangle}^{\prime},BR(\sigma_{\vartriangle}^{\prime}))_{V}^{T_{i}^{M}}$
where $\sigma_{\vartriangle}^{\prime}$ is a combination of the strategy we
optimize over and the fixed strategy from previous step, formally
$\sigma_{\vartriangle}^{\prime}=\sigma_{\vartriangle}^{S_{i}^{M}}\cup\sigma_{\vartriangle}^{T_{i-1}^{M}}$.

To summarize, we optimize only over the strategy in the subgame used in the
current step while the strategy in the previous parts of the game is fixed for
player $\vartriangle$, and we give the opponent a chance to best respond in
the whole $T^{\prime}_{i}$. We denote the full CDRNR strategy
$\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{\mathcal{P}}$.

#### Computing CDRNR

The input for computing CDRNR is also a definition of the game, opponent
strategy, value function with the same inputs and outputs as CDBR, and the
parameter $p$. We can create a modified game $G^{M}$ explicitly, or we can use
the original game tree and store everything in it because the trees are
identical. The trunk is solved using depth-limited CFR with the value
function, where both players act, but the opponent changes his strategy only
in $G^{\prime}$. We play following the strategy in the trunk, and when we need
to play outside of the trunk, we need to create a new depth-limited game.

We create a new depth-limited game in the same way as we specify in the
concept. Unlike CDBR, we can not exchange the trunk for the chance node
because player $\triangledown$ can deviate in the $G^{\prime}$ part. We then
need to use the value function when leaving the trunk. This means that we can
not exchange the trunk part of $G^{F}$ because the value function still needs
the reach probabilities from the fixed part of the tree. However, we can
compute the reaches once and reuse them because we know they will not change
and do not need the returned values. To summarize, we construct the new depth-
limited game by appending the new subgame to the trunk.

Then we resolve the subgame by CFR with value function, and we play according
to the resolved strategy in the subgame. When we leave the subgame, we
construct a new subgame and continue until the game ends.

The approach is computationally more demanding than CDBR, but it only grows
polynomially with each resolving round making it tractable. We attempted to
exchange the trunk using existing gadgets (Burch, Johanson, and Bowling 2014;
Moravcik et al. 2016; Brown and Sandholm 2017), and we found out all the
existing gadgets work nicely for standard resolving but break when we insert
the model.

Algorithm 1 Computing CDBR (CDRNR)

game $G$, opponent strategy $\sigma_{\triangledown}^{F}$, value function $V$

create (virtually) modified game $G^{M}$ (only CDRNR)

create subgame partitioning $\mathcal{P}$ from $G$ ($G^{M}$)

$\sigma_{\vartriangle}^{\mathcal{B}}$ = empty strategy ready to be filled

$I$ = initial information set in which we act

$S$ = current constructed subgame

while $I$ not null do

if $I$ not in $S$ then

S = construct new $S$ from $\mathcal{P}$ using previous $S$ (CDRNR does not
delete trunk)

$\sigma_{\vartriangle}^{\mathcal{B}}$ += solution of $S$ using CFR+ with $V$

else

pick action $A$ according to $\sigma_{\vartriangle}^{\mathcal{B}}$ in $I$

get new $I$ using $A$ (or null if the game ends)

end if

end while

##  4 Why Gadgets Fail

To demonstrate the problem with using gadgets, it is sufficient to assume that
the subgame is constructed until the end of the game without using value
functions. The problem shows when we solve the game from a non-root public
state. In RNR, the chance node at the beginning is not observed by player
$\vartriangle$. Therefore, in each information set, player $\vartriangle$
chooses his actions based on the values of his actions combined from the
values in $G^{\prime}$ and $G^{F}$. The values in $G^{F}$ can be computed
without problem even if we do not start from the beginning since the
opponent’s strategy is fixed. However, in $G^{\prime}$ player $\triangledown$
can respond, and we need to make sure the values of the part of the
information set in $G^{\prime}$ are also _correct_. Formally:

######  Definition 1.

For each information set $I\in\mathcal{I}_{\vartriangle}$ we need the value of
it’s part in $G^{\prime}$, formally $\sum_{h\in I,h\in G^{\prime},z\in
Z,h\sqsubset z}\pi^{\sigma}(z)u_{\vartriangle}(z)$, to be the same as the
value we would get if we let player $\triangledown$ play BR in full
$G^{\prime}$.

We can then apply the value function, and the problem will still be the same
because it is related to the history we are forgetting while the value
function is applied looking forward in the game. In the following examples, we
show the requirement is not satisfied for common resolving gadgets. We tried
to construct a gadget which would satisfy the condition, but in the end, we
kept the previously resolved parts of the game $G^{\prime}$ which satisfies
the condition, and still only increased the size of the solved part of the
game linearly. The construction of a constant-size gadget fulfilling the
previous condition is an open problem.

### Restricted Nash Response with Gadget

We show that commonly used resolving gadgets are either overestimating or
underestimating the values from Definiton 1 on an example game in Figure 2. In
the game, we first randomly pick a red or green coin. Player $\triangledown$
observes this and decides to place the coin heads up (RH, GH) or tails up (RT,
GT). Player $\vartriangle$ can not observe anything and, in the end, chooses
whether he wants to play the game (P) or quit (Q).

In equilibrium, player $\vartriangle$ plays action $Q$, and player
$\triangledown$ can mix action up to the point where utility for $P$ is at
most 0. This gives the value of the game 0, and counterfactual values in all
inner nodes are also 0. If we assume the modified RNR game $G^{M}$ with an
opponent model that makes it worth for player $\vartriangle$ to play (P) in
the game, $\triangledown$ will play $(RH,GH)$ in $G^{\prime}$ with utility -3
for player $\vartriangle$ in $G^{\prime}$. We will use gadgets to resolve the
game beginning in the player $\vartriangle$ information set.

.5cm .5cm [rectangle node] (0)c+4.5mm..2.4cm+ 0.5[left, xshift=4mm,
yshift=2.2mm] 0.5[right, xshift=-4mm, yshift=2.2mm]
(1)(0-1)$\triangledown$+8.5mm..1.2cm+ RH[left, xshift=1.5mm, yshift=2mm]
RT[right, xshift=-1.5mm, yshift=2mm] (2)(0-2)$\triangledown$+8.5mm..1.2cm+
GH[left, xshift=1.5mm, yshift=2mm] GT[right, xshift=-1.5mm, yshift=2mm]
(3)(1-1)$\vartriangle$+8.5mm…6cm+ P[l]-4[center] Q[r]0[center]
(4)(1-2)$\vartriangle$+8.5mm…6cm+ P[l]-1[center] Q[r]0[center]
(5)(2-1)$\vartriangle$+8.5mm…6cm+ P[l]-2[center] Q[r]0[center]
(6)(2-2)$\vartriangle$+8.5mm…6cm+ P[l]10[center] Q[r]0[center] (1-1)(1-2)
(1-2)(2-1) (2-1)(2-2)

.5cm .5cm [rectangle node] (0)c+10.5mm..1.8cm+ 0.5[left, xshift=0mm,
yshift=0.5mm] 0.5[left, xshift=1mm, yshift=0.5mm] 0.5[right, xshift=-1mm,
yshift=0.5mm] 0.5[right, xshift=0mm, yshift=0.5mm]
(1)(0-1)$\triangledown$+8.5mm..0.9cm+ F[left, xshift=1.5mm, yshift=2mm] <level
distance=1.2*>T[right, xshift=-0.8mm, yshift=2.8mm]0[center]
(2)(0-2)$\triangledown$+8.5mm..0.9cm+ F[left, xshift=1.5mm, yshift=2mm] <level
distance=1.2*>T[right, xshift=-0.8mm, yshift=2.8mm]0[center]
(3)(0-3)$\triangledown$+8.5mm..0.9cm+ F[left, xshift=1.5mm, yshift=2mm] <level
distance=1.2*>T[right, xshift=-0.8mm, yshift=2.8mm]0[center]
(4)(0-4)$\triangledown$+8.5mm..0.9cm+ F[left, xshift=1.5mm, yshift=2mm] <level
distance=1.2*>T[right, xshift=-0.8mm, yshift=2.8mm]0[center]
(5)(1-1)$\vartriangle$+9.5mm…6cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]-4[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(6)(2-1)$\vartriangle$+9.5mm…6cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]-1[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(7)(3-1)$\vartriangle$+9.5mm…6cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]-2[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(8)(4-1)$\vartriangle$+9.5mm…6cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]10[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(1-1)(2-1) (2-1)(3-1) (3-1)(4-1)

.5cm .5cm [rectangle node] (0)$\triangledown$+10.5mm..1.6cm+ E[left,
xshift=0mm, yshift=0.8mm] F[left, xshift=1mm, yshift=0.5mm] G[right,
xshift=-1mm, yshift=0.5mm] H[right, xshift=0mm, yshift=0.8mm]
(1)(0-1)c+8.5mm..0.8cm+ 0.5[left, xshift=0mm, yshift=1mm]
(2)(0-2)c+8.5mm..0.8cm+ 0.5[left, xshift=0mm, yshift=1mm]
(3)(0-3)c+8.5mm..0.8cm+ 0.5[left, xshift=0mm, yshift=1mm]
(4)(0-4)c+8.5mm..0.8cm+ 0.5[left, xshift=0mm, yshift=1mm]
(5)(1-1)$\vartriangle$+9.5mm…8cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]-4[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(6)(2-1)$\vartriangle$+9.5mm…8cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]-1[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(7)(3-1)$\vartriangle$+9.5mm…8cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]-2[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center]
(8)(4-1)$\vartriangle$+9.5mm…8cm+ P[left, yshift=-0.5mm,
xshift=0.5mm]10[center] Q[right, yshift=-0.5mm, xshift=-0.5mm]0[center] (8)(7)
(7)(6) (6)(5)

Figure 2: (left) Game to show problems with gadgets. (middle) Resolving gadget
for the left game. (right) Max-margin and Reach max-margin gadget.

##### Resolving Gadget

(Burch, Johanson, and Bowling 2014) Resolving gadget on the game in Figure 2
has all utilities after terminate actions 0. When we resolve the gadget, the
utility is 0. However, when player $\vartriangle$ deviates to action $P$,
player $\triangledown$ plays follow action in all but the rightmost node, and
the utility of player $\vartriangle$ will be -3.5. Therefore, the common
resolving gadget may overestimate the real exploitability of the strategy in
the subgame. Overestimating may lead to not exploiting as much as we can and
makes it impossible to prove Theorem 2 about the minimal gain of our
algorithm. It might seem that normalization of the chance node could solve the
problem, but it would only halve the value to -1.75, which is still incorrect.

##### (Reach) Max-margin Gadget

(Moravcik et al. 2016; Brown and Sandholm 2017) All the counterfactual best
response values are 0, and we do not need to offset any node in the max-margin
gadget. Similarly, the reach max-margin gadget offsets the values using
counterfactual values. It adds a lower bound on previous mistakes, but since
we assume both players played perfectly before the depth limit, the offset is
also 0. Then both gadget constructions are identical. We add the initial
decision node and the chance nodes (since there is only one state in each
infoset, the nodes have only one action). When we solve the gadget, player
$\vartriangle$ will pick action $Q$, and the gadget value will be 0. However,
when player $\vartriangle$ deviates to action $P$, player $\triangledown$ now
has a choice between terminal utilities and picks action $E$ to receive the
highest one. This will result in utility -2, and we see that (reach) max-
margin gadgets can underestimate the real exploitability. Underestimating the
exploitability can lead to our algorithm being more exploitable than we want
using some $p$, and it makes Theorem 3 impossible to prove. Similar to the
previous gadget, normalizing the chance nodes would lead to double the
utility, which is still incorrect.

##  5 Theory

This section provides the theoretical performance guarantees for CDBR and
CDRNR and explains why the guarantee can not be even better. Furthermore, we
provide an upper bound on the exploitability of CDRNR, linking it to the gain
by the parameter $p$. Formal proofs of all the theorems are in the appendix.

### Response Performance Against Model

The first theorem shows that CDBR and CDRNR will achieve at least the value of
the game against the opponent model. Theorem specifically for CDBR is only in
the appendix because it is only a special case of Theorem 2. However, as shown
in the appendix, CDBR can perform worse than a Nash equilibrium against the
fixed opponent because of the perfect opponent assumption at the depth-limit.

######  Lemma 1.

Let $G$ be a zero-sum imperfect-information extensive-form game with perfect
recall. Let $\sigma_{\triangledown}^{\text{F}}$ be fixed opponent’s strategy,
and let $T$ be some trunk of the game. If we perform CFR iterations in the
trunk for player $\vartriangle$ then for the strategy
$\hat{\sigma}_{\vartriangle}$ from the iteration with highest expected utility
it holds
$\max_{\sigma_{\vartriangle}^{*}\in\Sigma_{\vartriangle}}u_{\vartriangle}(\sigma_{\vartriangle}^{*},\sigma_{\triangledown}^{F})_{V}^{T}-u_{\vartriangle}(\hat{\sigma}_{\vartriangle},\sigma_{\triangledown}^{F})_{V}^{T}\leq\Delta\sqrt{\frac{A}{T}}|\mathcal{I}_{TR}|+TN_{S}\epsilon_{S}$
where $\Delta$ is variance in leaf utility, $A$ is an upper bound on the
number of actions, $|\mathcal{I}_{TR}|$ is number of information sets in the
trunk, $N_{S}$ is the number of information sets at the root of any subgame
and value function error is at most $\epsilon_{S}$.

The previous lemma states that the algorithm in CDBR converges to the best
response in the trunk not only using an average strategy which is guaranteed
by CFR but also if we track the strategy with the highest utility, it will
converge to the best response.

For the following theorems, we denote $\mathcal{S}$ as the set consisting of
the trunk and all the subgames explored when computing the response, and
$\mathcal{S^{\prime}}$ is the same but without the last subgame. $S^{B}$
denotes a border of the subgame (a set of all the states where the value
function is used in the subgame). We also denote $S^{O}$ the set of all the
states where we leave the trunk not going in the currently resolving subgame
(set of the states where value function is used in RNR which are not in
$S^{B}$).

######  Theorem 2.

Let $G$ be any zero-sum extensive-form game with perfect recall and let
$\sigma_{\triangledown}^{\text{F}}$ be any fixed opponent’s strategy in $G$.
Then we set $G^{M}$ as restricted Nash response modification of $G$ using
$\sigma_{\triangledown}^{\text{F}}$. Let $\mathcal{P}$ be any subgame
partitioning of the game $G^{M}$ and using some $p\in\langle 0,1\rangle$, let
$\sigma_{\vartriangle}^{\mathcal{R}}$ be a CDRNR given approximation $\bar{V}$
of the optimal value function $V$ with error at most $\epsilon_{V}$ and
opponent strategy $\sigma_{\triangledown}^{\text{F}}$ approximated in each
step with regret at most $\epsilon_{R}$, formally
$\sigma_{\vartriangle}^{\mathcal{R}}=\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{\mathcal{P}}$.
Let $\sigma^{NE}$ be any Nash equilibrium in $G$. Then
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma_{\triangledown}^{F})+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{O}}|(1-p)\epsilon_{V}+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}\geq
u_{\vartriangle}(\sigma^{NE})$.

The previous theorem states that our approaches have the first property we
wanted, and when we respond to the model, we will receive at least the value
of the game.

### Exploitability Guarantee of CDRNR

######  Theorem 3.

Let $G$ be any zero-sum extensive-form game with perfect recall and let
$\sigma_{\triangledown}^{\text{F}}$ be any fixed opponent’s strategy in $G$.
Then we set $G^{M}$ as restricted Nash response modification of $G$ using
$\sigma_{\triangledown}^{\text{F}}$. Let $\mathcal{P}$ be any subgame
partitioning of the game $G^{M}$ and using some $p\in\langle 0,1\rangle$, let
$\sigma_{\vartriangle}^{\mathcal{R}}$ be a CDRNR given approximation $\bar{V}$
of the optimal value function $V$ with error at most $\epsilon_{V}$,
partitioning $\mathcal{P}$ and opponent strategy
$\sigma_{\triangledown}^{\text{F}}$, which is approximated in each step with
regret at most $\epsilon_{R}$, formally
$\sigma_{\vartriangle}^{\mathcal{R}}=\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{\mathcal{P}}$.
Then exploitability has a bound
$\mathcal{E}(\sigma_{\vartriangle}^{\mathcal{R}})\leq\mathcal{G}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma_{\triangledown}^{F})\frac{p}{1-p}\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{O}}|(1-p)\epsilon_{V}+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}$,
$\mathcal{E}$ and $\mathcal{G}$ are defined in Section 2.

The last theorem is more complex, and it bounds the exploitability by the gain
of the strategy against the model. With $p=0$ it is reduced to the continual
resolving and with $p=1$ to CDBR with unbounded exploitability. The theorem
shows we can manipulate allowed exploitability by changing the $p$.

##  6 Experiments

We show a comparison between continual depth-limited best response (CDBR) and
local best response (LBR) (Lisy and Bowling 2017). We also show empirically
that the continual depth-limited restricted Nash response (CDRNR)
exploitability is bounded, and we explore the tradeoff between exploitability
and gain in CDRNR. The appendix contains hardware setup, domain description,
algorithm details, and experiments on more game domains. We use two types of
opponent strategies, strategies generated by a low amount of CFR iterations
and random strategies with different seeds.

Figure 3: Gain and exploitability comparison of BR, RNR, CDRNR, and best Nash
equilibrium (BNE) in Leduc Hold’em (top) against strategies from CFR using a
small number of iterations with different $p$ values. The a stands for the
average of the other values. VF is CDRNR using an imperfect value function. SX
is CDRNR with perfect value function using lookahead with X steps.

### Exploitability of Robust Responses

We report both gain and exploitability for CDRNR on Leduc Hold’em. Results in
Figure 3 show that the proven bound on exploitability works in practice, and
we see that the bound is very loose in practice. For example, with $p=0.5$,
the bound on the exploitability is the gain itself, but the algorithm rarely
reaches even a tenth of the gain in exploitability. This shows that the CDRNR
is similar to the restricted Nash response because, with a well-set $p$, it
can significantly exploit the opponent without significantly raising its
exploitability. The only exception is the CDRNR with value function, which
shows the added constants from the value function’s imprecision. When the
opponent is close to optimal, we see that the exploitability can rise above
the gain.

In most cases, the gain and exploitability of CDRNR are lower than that of
RNR. Gain must be lower because of the different value function, but the
exploitability can be higher, as seen with $p=0.1$ against low iteration
strategies. The depth-limited scheme causes that, and because the algorithm,
unlike RNR, has not complete information when making individual decisions, it
can choose different paths to exploit the opponent, raising its exploitability
more than it has to. However, the bound will always hold. We provide results
on other domains and for more parameter values $p$ in the appendix.

We also compare the algorithm against the best possible Nash equilibrium. It
is computed by a linear program and serves as the theoretical limit of maximal
gain, which does not allow exploitability. It would be impossible to compute
for larger games. We can see we can gain twice as much with exploitability
still being almost zero.

We report the result with the value function produced by 500 CFR iterations as
VF. We split the Leduc by rounds, so it does not correspond to any step scheme
and is somewhere between S1 and S5. As expected, the imperfect value function
slightly decreases the performance, but overall is comparable to the
algorithms using the optimal value function.

### Local Best Response vs. CDRNR

We compare LBR and CDBR in Leduc Holde’m. We also compare CDBR with just the
BR in imperfect information Goofspiel, but without LBR, which is poker
specific. We show that CDBR and LBR are very similar with smaller steps, and
as we increase the depth-limit of CDBR, it starts outperforming LBR. The
behavior differs in every strategy because LBR assumes the player continues
the game by only calling till the end, while CDBR uses the perfectly rational
extension. Furthermore, it is possible to exchange the value function of CDBR,
and both concepts would be very similar. However, we would lose the guarantee
that CDBR will never perform worse than the value of the game.

Figure 4: Gain comparison of best response (BR), local best response (LBR -
only poker), and continual depth-limited best response (CDBR) in Leduc Hold’em
(top) and Imperfect information Goofspiel (bottom) against strategies from CFR
using a small number of iterations (left) and random strategies (right). The a
stands for the average of the other values in the plot. The number after CDBR
stands for the number of actions CDBR was allowed to look in the future, and
CDBRNN is one step CDBR with a neural network as a value function.

Looking at the results in Figure 4, we can see that both concepts are good at
approximating the best response, with CDBR being better against both
strategies. LBR looks at one following action, so in terms of comparability,
it is best compared to the CDBR1. Next, we observe a lack of monotonicity in
step increase, which is linked to the counterexample in the appendix. When we
increase the depth-limit, the algorithm can exploit some early mistake that
causes it to miss a sub-tree where the opponent makes a much bigger mistake in
the future. Finally, we can see the difference between the algorithm with
guarantees and LBR without them nicely. Against strategy from 34 CFR
iterations, LBR can no longer achieve positive gain and only worsens with more
iterations. In contrast, CDBR can always achieve at least zero gain (assuming
we have an optimal value function).

##  7 Related Work

This section describes the related work focusing more on distinguishing our
novel contributions.

We have been inspired by the depth-limited solving used by DeepStack, and
other algorithms (Moravčík et al. 2017; Brown and Sandholm 2018). Depth-
limited solving is an approach that made solving huge imperfect-information
games possible.

Restricted Nash response (RNR) (Johanson, Zinkevich, and Bowling 2008) is an
opponent exploiting scheme. It solves the entire game and allows changing the
trade-off between exploitability and gain. Essentially it always produces
$\epsilon$ safe best response (McCracken and Bowling 2004).

However, it is impossible to compute RNR in huge games, and we fused the RNR
approach with depth-limited solving creating a novel algorithm we call CDRNR.
CDRNR is the first robust response calculation that can be done in huge games,
enabling opponent modeling approaches in such games.

Local best response (Lisy and Bowling 2017) is an evaluation tool for poker.
It uses given abstraction in its action space. It picks the best action in
each decision set, looking at fold probability for the opponent in the next
decision node and then assuming the game is called until the end. Our second
algorithm CDBR is a generalization of the LBR because we can use it on any
game solvable by depth-limited solving. We have explicitly defined value
function, which we can exchange for different heuristics.

Approximate best response (ABR) (Timbers et al. 2020) is also a generalization
of the LBR and showed promising results in evaluating strategies. However, our
approach focuses on opponent modeling, which requires crucial differences,
such as quick re-computation against unseen models. ABR needs to independently
learn the response for every combination of opponent and game, making it
unusable in the opponent modeling scenario. Our algorithms learn a single
domain-specific value function and can subsequently compute strategies against
any opponent in the run-time. Furthermore, ABR and even our CDBR are extremely
brittle, making it a bad choice if we are unsure about the opponent, which we
often are at the start of a game against an unknown opponent. On the other
hand, our second algorithm CDRNR tackles exactly this issue and provides
powerful exploitation with very limited exploitability.

##  8 Conclusion

Opponent exploitation is an essential topic in computational game theory, and
no previous approaches use continual resolving for opponent exploitation. We
propose algorithms to quickly compute depth-limited best response and depth-
limited restricted Nash response once we have the value function, creating the
first robust response applicable to massive games. We prove the soundness of
the methods in terms of gain against the opponents and safety against the
worst-case adversary. Next, we show that common resolving gadgets can skew the
subgame value. Finally, we empirically evaluate the algorithms on three
different games. We show that we can achieve high exploitation with the
optimal value function and outperform the domain-specific local best response
on poker.

## Acknowledgements

This research is supported by Czech Science Foundation (grant no. 18-27483Y).
Computational resources were supplied by the project "e-Infrastruktura CZ"
(e-INFRA CZ LM2018140) supported by the Ministry of Education, Youth and
Sports of the Czech Republic and also the OP VVV funded project
CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics” which are
both gratefully acknowledged.

## References

  * An et al. (2013) An, B.; Ordóñez, F.; Tambe, M.; Shieh, E.; Yang, R.; Baldwin, C.; DiRenzo III, J.; Moretti, K.; Maule, B.; and Meyer, G. 2013.  A deployed quantal response-based patrol planning system for the US Coast Guard.  _Interfaces_ , 43(5): 400–420.
  * Bard et al. (2013) Bard, N.; Johanson, M.; Burch, N.; and Bowling, M. 2013.  Online implicit agent modelling.  In _Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems_ , 255–262.
  * Brown and Sandholm (2017) Brown, N.; and Sandholm, T. 2017.  Safe and nested endgame solving for imperfect-information games.  In _Workshops at the thirty-first AAAI conference on artificial intelligence_.
  * Brown and Sandholm (2018) Brown, N.; and Sandholm, T. 2018.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , 359(6374): 418–424.
  * Brown and Sandholm (2019a) Brown, N.; and Sandholm, T. 2019a.  Solving imperfect-information games via discounted regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 1829–1836.
  * Brown and Sandholm (2019b) Brown, N.; and Sandholm, T. 2019b.  Superhuman AI for multiplayer poker.  _Science_ , 365(6456): 885–890.
  * Burch, Johanson, and Bowling (2014) Burch, N.; Johanson, M.; and Bowling, M. 2014.  Solving imperfect information games using decomposition.  In _Twenty-eighth AAAI conference on artificial intelligence_.
  * Farina, Kroer, and Sandholm (2020) Farina, G.; Kroer, C.; and Sandholm, T. 2020.  Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent.  _arXiv preprint arXiv:2007.14358_.
  * Heinrich and Silver (2016) Heinrich, J.; and Silver, D. 2016.  Deep reinforcement learning from self-play in imperfect-information games.  _arXiv preprint arXiv:1603.01121_.
  * Johanson and Bowling (2009) Johanson, M.; and Bowling, M. 2009.  Data biased robust counter strategies.  In _Artificial Intelligence and Statistics_ , 264–271.
  * Johanson, Zinkevich, and Bowling (2008) Johanson, M.; Zinkevich, M.; and Bowling, M. 2008.  Computing robust counter-strategies.  In _Advances in neural information processing systems_ , 721–728.
  * Korb, Nicholson, and Jitnah (2013) Korb, K. B.; Nicholson, A.; and Jitnah, N. 2013.  Bayesian poker.  _arXiv preprint arXiv:1301.6711_.
  * Kovařík et al. (2019) Kovařík, V.; Seitz, D.; Lisý, V.; Rudolf, J.; Sun, S.; and Ha, K. 2019\.  Value Functions for Depth-Limited Solving in Imperfect-Information Games.  _arXiv preprint arXiv:1906.06412_.
  * Lisy and Bowling (2017) Lisy, V.; and Bowling, M. 2017.  Eqilibrium approximation quality of current no-limit poker bots.  In _Workshops at the Thirty-First AAAI Conference on Artificial Intelligence_.
  * Lockhart et al. (2019) Lockhart, E.; Lanctot, M.; Pérolat, J.; Lespiau, J.-B.; Morrill, D.; TImbers, F.; and Tuyls, K. 2019.  Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , 464–470.
  * McCracken and Bowling (2004) McCracken, P.; and Bowling, M. 2004.  Safe strategies for agent modelling in games.  In _AAAI Fall Symposium on Artificial Multi-agent Learning_ , 103–110.
  * Mealing and Shapiro (2015) Mealing, R.; and Shapiro, J. L. 2015.  Opponent modeling by expectation–maximization and sequence prediction in simplified poker.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 9(1): 11–24.
  * Milec et al. (2021) Milec, D.; Černý, J.; Lisý, V.; and An, B. 2021.  Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, 5575–5583.
  * Mnih et al. (2013) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Graves, A.; Antonoglou, I.; Wierstra, D.; and Riedmiller, M. 2013.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_.
  * Moravcik et al. (2016) Moravcik, M.; Schmid, M.; Ha, K.; Hladik, M.; and Gaukrodger, S. 2016.  Refining subgames in large imperfect information games.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30.
  * Moravčík et al. (2017) Moravčík, M.; Schmid, M.; Burch, N.; Lisý, V.; Morrill, D.; Bard, N.; Davis, T.; Waugh, K.; Johanson, M.; and Bowling, M. 2017.  Deepstack: Expert-level artificial intelligence in Heads-Up No-Limit Poker.  _Science_ , 356(6337): 508–513.
  * Schmid et al. (2021) Schmid, M.; Moravcik, M.; Burch, N.; Kadlec, R.; Davidson, J.; Waugh, K.; Bard, N.; Timbers, F.; Lanctot, M.; Holland, Z.; et al. 2021.  Player of Games.  _arXiv preprint arXiv:2112.03178_.
  * Southey et al. (2012) Southey, F.; Bowling, M. P.; Larson, B.; Piccione, C.; Burch, N.; Billings, D.; and Rayner, C. 2012.  Bayes’ bluff: Opponent modelling in poker.  _arXiv preprint arXiv:1207.1411_.
  * Tammelin et al. (2015) Tammelin, O.; Burch, N.; Johanson, M.; and Bowling, M. 2015.  Solving heads-up limit texas hold’em.  In _Twenty-fourth international joint conference on artificial intelligence_.
  * Timbers et al. (2020) Timbers, F.; Lockhart, E.; Lanctot, M.; Schmid, M.; Schrittwieser, J.; Hubert, T.; and Bowling, M. 2020.  Approximate exploitability: Learning a best response in large games.  _arXiv preprint arXiv:2004.09677_.
  * Wu et al. (2021) Wu, Z.; Li, K.; Zhao, E.; Xu, H.; Zhang, M.; Fu, H.; An, B.; and Xing, J. 2021.  L2E: Learning to Exploit Your Opponent.  _arXiv preprint arXiv:2102.09381_.
  * Zarick et al. (2020) Zarick, R.; Pellegrino, B.; Brown, N.; and Banister, C. 2020.  Unlocking the potential of deep counterfactual value networks.  _arXiv preprint arXiv:2007.10442_.

##  Appendix A Counterexample Gadget Game

In this section, we describe the more profound problem with the gadget. Both
resolving and max-margin gadgets might be unable to find the correct strategy
in the RNR depth limited scenario. We constructed an example game in Figure 5
such that action $b$ is always 0 for player $\vartriangle$ and other actions
are dominated by $b$ unless the opponent makes a mistake. We construct the RNR
modified game with the opponent’s strategy playing purely actions
$(W,Z,M,O,Q,S)$ action $b$ still dominates for $p$ slightly smaller than 0.5.
When we have $p=0.5$ the best action is $c$ and when we slightly increase $p$
action $a$ dominates all the way up to $p=1$.

With the gadgets, we take such depth-limit that the game is first solved
without player $\vartriangle$ playing, and then the next subgame starts in his
information set. The previous game is solved using the perfect value function,
so counterfactual values everywhere are 0, and the resolving and sequence form
gadget will have 0 at the terminate actions, and the max-margin gadget will
not offset anything. Then when we solve the subgame using the sequence form
gadget, it is the same as the original RNR. for $p=0.5$ we resolve $c$, and
for smaller $p$ we have $b$, and for higher $p$ we have $a$. First, we thought
that even though other gadgets overestimate/underestimate the values, we can
re-scale $p$ and resolve the same strategies. However, as we show in Figures 7
and 8, there is no $p$ such that resolving or max-margin gadget resolve the
subgame to create strategy with pure $c$.

.5cm .5cm [rectangle node] (0)c+10.5mm..3.8cm+ 0.5[left, xshift=0mm,
yshift=1mm] 0.5[right, yshift=1mm] (1)(0-1)$\triangledown$+8.5mm..2.cm+
W[left, xshift=1.5mm, yshift=2mm] X[right, xshift=-1.5mm, yshift=2mm]
(2)(0-2)$\triangledown$+8.5mm..2.cm+ Y[left, xshift=1.5mm, yshift=2mm]
Z[right, xshift=-1.5mm, yshift=2mm] (3)(1-1)$\vartriangle$+9.5mm..0.6cm+
c[left, yshift=1.5mm, xshift=1mm] b[right, yshift=0mm, xshift=-1mm]0[center]
a[right, yshift=1.5mm, xshift=-1mm](4)(1-2)$\vartriangle$+9.5mm…6cm+ c[left,
yshift=0mm, xshift=0.5mm]-3[center] b[right, yshift=0mm, xshift=-1mm]0[center]
a[right, yshift=0mm, xshift=-0.5mm]-3[center](5)(2-1)$\vartriangle$+9.5mm…6cm+
c[left, yshift=0mm, xshift=0.5mm]-4[center] b[right, yshift=0mm,
xshift=-1mm]0[center] a[right, yshift=0mm,
xshift=-0.5mm]-5[center](6)(2-2)$\vartriangle$+9.5mm..0.6cm+ c[left,
yshift=1.5mm, xshift=1mm] b[right, yshift=0mm, xshift=-1mm]0[center] a[right,
yshift=1.5mm, xshift=-1mm](7)(3-1)$\triangledown$+9.5mm..0.6cm+ M[left,
yshift=-0.5mm, xshift=0.55mm]$E$[center] N[right, yshift=-0.5mm,
xshift=-0.5mm]-3[center](8)(3-3)$\triangledown$+9.5mm..0.6cm+ O[left,
yshift=-0.5mm, xshift=0.55mm]4.5[center] P[right, yshift=-0.5mm,
xshift=-0.5mm]-4[center](9)(6-1)$\triangledown$+9.5mm..0.6cm+ Q[left,
yshift=-0.5mm, xshift=0.55mm]$E$[center] R[right, yshift=-0.5mm,
xshift=-0.5mm]0[center](10)(6-3)$\triangledown$+9.5mm..0.6cm+ S[left,
yshift=-0.5mm, xshift=0.55mm]4.5[center] T[right, yshift=-0.5mm,
xshift=-0.5mm]0[center](1-1)(1-2) (2-1)(1-2) (2-1)(2-2)

Figure 5: Example game where gadgets can not resolve the strategy in CDRNR.
$E=3.500001$ Figure 6: Expected utility of different actions from Figure 5
using sequence form gadget, where $x=0.000001$ and utility on the right is
times $10^{-5}$. Figure 7: Expected utility of different actions from Figure 5
using max-margin gadget. Figure 8: Expected utility of different actions from
Figure 5 using resolving gadget.

##  Appendix B Experiment Details

### Experimental Setup

For all experiments, we use Python 3.8 and C++. We solved linear programs
using gurobi 9.0.3, and experiments were done on Intel i7 1.8GHz CPU with 8GB
RAM. We used Leduc Hold’em for CDBR experiments with the torch library for the
neural network experiment. For CDRNR experiments, we used an imperfect
information version of Goofspiel 5. For most of the experiments, we wanted to
solve the concepts perfectly with perfect value function, so we used LP and
fixed the parts of the game that needed to be fixed. For the neural network
experiment with CDBR, we used CFR+ to solve the subgame and the neural network
as a value function.

### Domain Definition

Leduc Hold’em is a medium-sized poker game. Both players give one chip at the
beginning of the match and receive one card from a deck with six cards of 2
suits and three ranks. Then players switch and can call or bet. After a bet,
the opponent can also fold, which finishes the game, and he forfeits all the
staked money. After both players call or after at most two bets public card is
revealed, and another betting round begins. In the first round, the bet size
is two, and in the second, it is 4. If the game ends without anyone, folding
cards are compared, and the player with pair always wins, and if there is no
pair, the player with the higher card wins. If both have the same card, the
money is split. Goofspiel is a bidding card game where players are trying to
obtain the most points. Cards are shuffled and set face-down. Each turn, the
top point card is revealed, and players simultaneously play a bid card; the
point card is given to the highest bidder or discarded if the bids are equal.
In this implementation, we use a fixed deck with K = 5.

Liar’s Dice is a game where players have some number of dice and secretly
roll. Then first player bids amount of numbers rolled and the other player can
bid more or disbelieve the first player. When bidding ends by disbelief action
both players show dice and if the bid is right the caller loses one die and
when the bidder is wrong the bidder loses one die. Then the game continues but
for out computation we use game which ends by the loss of a die and we use one
die with four sides for each player.

##  Appendix C Proofs

######  Lemma 1.

Let $G$ be zero-sum imperfect-information extensive-form game with perfect
recall. Let $\sigma_{\triangledown}^{\text{F}}$ be fixed opponent’s strategy,
let $T$ be some trunk of the game. If we perform CFR iterations in the trunk
for player $\vartriangle$ then for the best iterate
$\hat{\sigma}_{\vartriangle}$
$\max_{\sigma_{\vartriangle}^{*}\in\Sigma_{\vartriangle}}u_{\vartriangle}(\sigma_{\vartriangle}^{*},\sigma_{\triangledown}^{F})_{V}^{T}-u_{\vartriangle}(\hat{\sigma}_{\vartriangle},\sigma_{\triangledown}^{F})_{V}^{T}\leq\Delta\sqrt{\frac{A}{T}}|\mathcal{I}_{TR}|+N_{S}\epsilon_{S}$
where $\Delta$ is variance in leaf utility, $A$ is an upper bound on the
number of actions, $|\mathcal{I}_{TR}|$ is number of information sets in the
trunk, $N_{S}$ is the number of information sets at the root of any subgame
and value function error is at most $\epsilon_{S}$.

###### Proof.

Using Theorem 2 from (Burch, Johanson, and Bowling 2014) we know that regret
for player $\vartriangle$ is bounded
$R_{\vartriangle}^{T}=\frac{1}{T}\max_{\sigma_{\vartriangle}^{*}\in\Sigma_{\vartriangle}}\sum_{t=1}^{T}(u_{\vartriangle}(\sigma_{\vartriangle}^{*},\sigma_{\triangledown}^{F})_{V}^{T}-u_{\vartriangle}(\sigma_{\vartriangle}^{t},\sigma_{\triangledown}^{F}))_{V}^{T}\leq\Delta\sqrt{AT}|\mathcal{I}_{TR}|+TN_{S}\epsilon_{S}$.
Then we can directly map the regret to regret using time-independent loss
function
$l(\sigma_{\vartriangle})=-u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown}^{F})_{V}^{T}$.
We can then use Lemma 2 from (Lockhart et al. 2019) and we get
$l(\hat{\sigma}_{\vartriangle})-\min_{\sigma_{\vartriangle}^{*}\in\Sigma_{\vartriangle}}l(\sigma_{\vartriangle}^{*})\leq\frac{R_{\vartriangle}^{T}}{T}$.
Substituting $l$ and $R_{\vartriangle}^{T}$ back we get

$\max_{\sigma_{\vartriangle}^{*}\in\Sigma_{\vartriangle}}u_{\vartriangle}(\sigma_{\vartriangle}^{*},\sigma_{\triangledown}^{F})_{V}^{T}-u_{\vartriangle}(\hat{\sigma}_{\vartriangle},\sigma_{\triangledown}^{F})_{V}^{T}\leq\Delta\sqrt{\frac{A}{T}}|\mathcal{I}_{TR}|+N_{S}\epsilon_{S}$

∎

######  Theorem 2.

Let $G$ be zero-sum extensive-form game with perfect recall. Let
$\sigma_{\triangledown}^{\text{F}}$ be fixed opponent’s strategy, let
$\mathcal{P}$ be any subgame partitioning of the game $G$ and let
$\sigma_{\vartriangle}^{\mathcal{B}}$ be a CDBR given approximation $\bar{V}$
of the optimal value function $V$ with error at most $\epsilon_{V}$,
partitioning $\mathcal{P}$ and opponent strategy
$\sigma_{\triangledown}^{\text{F}}$ approximated in each step with regret at
most $\epsilon_{R}$, formally
$\sigma_{\vartriangle}^{\mathcal{B}}=\sigma_{\vartriangle}^{\mathcal{B}}(\sigma_{\triangledown}^{F})_{V}^{\mathcal{P}}$.
Let $\sigma^{NE}$ be any Nash equilibrium. Then
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{F})+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}\geq
u_{\vartriangle}(\sigma^{NE})$.

###### Proof.

Using subgame partitioning $P$, let $T_{1}$ be the trunk of the game. From the
properties of a NE $u_{\vartriangle}(\sigma^{NE})\leq
u_{\vartriangle}(\sigma_{\vartriangle}^{NE},\sigma_{\triangledown}^{\text{F}})\leq
u_{\vartriangle}(\sigma_{\vartriangle}^{NE},\sigma_{\triangledown}^{\text{F}})^{T_{1}}_{V}$.
To compute CDBR we are maximizing in the trunk and using error in the value
function and non-zero regret of the computed strategy
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{\text{F}})^{T_{1}}_{V}+|I_{T^{B}_{1}}|\epsilon_{V}+\epsilon_{R}\geq
u_{\vartriangle}(\sigma_{\vartriangle}^{NE},\sigma_{\triangledown}^{\text{F}})^{T_{1}}_{V}$.
We continue using induction over steps with induction assumption that in step
$i$,
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{\text{F}})^{T_{i}}_{V}+\epsilon_{i}\geq
u_{\vartriangle}(\sigma^{NE})$. We already know it holds for $T_{1}$. Now we
assume we have trunk $T_{i-1}$ for which the induction step holds and trunk
$T_{i}$ which is $T_{i-1}$ joined with new subgame $S_{i-1}$. Our algorithm
recovers approximate equilibrium in $S_{i-1}$ using $\bar{V}$ at the boundary
$S^{B}_{i-1}$, which means
$u_{\vartriangle}(\sigma^{\mathcal{B}}_{\vartriangle},\sigma_{\triangledown}^{F})_{V}^{T_{i}}+|I_{S^{B}_{i-1}}|\epsilon_{V}+\epsilon_{R}\geq
u_{\vartriangle}(\sigma^{NE_{S_{i-1}}}_{\vartriangle}\cup\sigma_{\vartriangle}^{\mathcal{B}_{T_{i-1}}},\sigma_{\triangledown}^{F})_{V}^{T_{i}}$.
If we use equilibrium for the opponent in the subgame $S_{i-1}$ we can replace
equilibrium in the subgame by the value function $V$ and we have
$u_{\vartriangle}(\sigma^{NE_{S_{i-1}}}_{\vartriangle}\cup\sigma_{\vartriangle}^{\mathcal{B}_{T_{i-1}}},\sigma_{\triangledown}^{F})_{V}^{T_{i}}\geq
u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{\text{F}})^{T_{i-1}}_{V}$
and joining it all together we have
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{\text{F}})^{T_{i-1}}_{V}\leq\textbf{{}}u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{\text{F}})^{T_{i}}_{V}+|I_{S^{B}_{i-1}}|\epsilon_{V}+\epsilon_{R}$
and
$u_{\vartriangle}(\sigma^{NE})\leq\textbf{{}}u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{\text{F}})^{T_{i}}_{V}+|I_{S^{B}_{i-1}}|\epsilon_{V}+\epsilon_{R}+\epsilon_{i-1}$.
Accumulating the errors through the subgames will give the desired result
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{B}},\sigma_{\triangledown}^{F})+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}\geq
u_{\vartriangle}(\sigma^{NE})$ We omit last subgame from the accumulated value
function error because the last step does not use value function. ∎

######  Theorem 3.

Let $G$ be any zero-sum extensive-form game with perfect recall and let
$\sigma_{\triangledown}^{\text{F}}$ be any fixed opponent’s strategy in $G$.
Then we set $G^{M}$ as restricted Nash response modification of $G$ using
$\sigma_{\triangledown}^{\text{F}}$. Let $\mathcal{P}$ be any subgame
partitioning of the game $G^{M}$ and using some $p\in\langle 0,1\rangle$, let
$\sigma_{\vartriangle}^{\mathcal{R}}$ be a CDRNR given approximation $\bar{V}$
of the optimal value function $V$ with error at most $\epsilon_{V}$ and
opponent strategy $\sigma_{\triangledown}^{\text{F}}$ approximated in each
step with regret at most $\epsilon_{R}$, formally
$\sigma_{\vartriangle}^{\mathcal{R}}=\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{\mathcal{P}}$.
Let $\sigma^{NE}$ be any Nash equilibrium in $G$. Then
$u_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma_{\triangledown}^{F})+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{O}}|(1-p)\epsilon_{V}+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}\geq
u_{\vartriangle}(\sigma^{NE})$.

###### Proof.

Let $T^{M}_{1}$ be a trunk of a modified game $G^{M}$ using partitioning
$\mathcal{P}$. We will use $u^{G}(\sigma)$ as utility in $G$. Utility of
player $\vartriangle$ for playing Nash equilibrium of the $G$ in trunk $T_{1}$
will be higher or the same as game value of $G$, formally
$u^{G}_{\vartriangle}(\sigma^{NE})\leq
u^{G^{M}}_{\vartriangle}(\sigma^{NE})^{T^{M}_{1}}_{V}$. To compute CDRNR we
use the approximate value function. In the fixed part of the game $G^{F}$ the
value will be worse at most by sum of errors as in the CDBR case. However, in
the $G^{\prime}$ the situation is more complicated and we use Theorem 2 from
(Burch, Johanson, and Bowling 2014) to bound the utility increase, resulting
in
$u^{G^{M}}_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{R}},BR(\sigma_{\vartriangle}^{\mathcal{R}}))^{T_{i}}_{V}+|I_{T^{M,B}_{1}}|\epsilon_{V}+|I_{T^{M}_{1}}|\epsilon_{R}\geq
u^{G}_{\vartriangle}(\sigma^{NE})$. We continue using induction over steps
with induction assumption that in step $i$,
$u^{G^{M}}_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{R}},BR(\sigma_{\vartriangle}^{\mathcal{R}}))^{T^{M}_{i}}_{V}+\epsilon_{i}\geq
u^{G}_{\vartriangle}(\sigma^{NE})$ and we already showed it holds for $T_{1}$.
Now we assume we have trunk $T_{i-1}$ for which the induction step holds and
trunk $T_{i}$ which is $T_{i-1}$ joined with new subgame $S_{i-1}$. Our
algorithm recovers approximate equilibrium in $S^{M}_{i-1}$ and we want
similar equation as for the CDBR. Part of the game tree $G^{F}$ has the errors
bounded as in CDBR but because we use gadget in the $G^{\prime}$ we need to
also consider error in actions ending with value function player
$\triangledown$ can play in the top with error bounded by $\epsilon_{V}$. We
have $|I_{S^{O}}|$ of actions leading out of the tree so the error increase in
the $G^{\prime}$ going to the next subgame is at most
$|I_{S^{O}}|\epsilon_{V}+|I_{S^{M,B}_{i-1}}|\epsilon_{V}+|I_{S^{M}_{i-1}}|\epsilon_{R}$
which together gives us
$u^{G^{M}}_{\vartriangle}(\sigma^{\prime}_{\vartriangle},BR(\sigma^{\prime}_{\vartriangle}))_{V}^{T_{i}}+(1-p)|I_{S^{O}}|\epsilon_{V}+|I_{S^{M,B}_{i-1}}|\epsilon_{V}+|I_{S^{M}_{i-1}}|\epsilon_{R}\geq
u^{G^{M}}_{\vartriangle}(\sigma^{\mathcal{R}}_{\vartriangle},BR(\sigma^{\mathcal{R}}_{\vartriangle}))_{V}^{T_{i-1}}$,
where $\sigma_{\vartriangle}^{\prime}$ is a combination of the strategy we
approximated in the subgame and the fixed strategy from previous step,
formally
$\sigma_{\vartriangle}^{\prime}=\sigma_{\vartriangle}^{S_{i-1}}\cup\sigma_{\vartriangle}^{\mathcal{R},T_{i-1}}$.
Joining it with the induction assumption we have
$u^{G^{M}}_{\vartriangle}(\sigma^{\mathcal{R}}_{\vartriangle},BR(\sigma^{\mathcal{R}}_{\vartriangle}))_{V}^{T_{i}}+(1-p)|I_{S^{O}}|\epsilon_{V}+|I_{S^{M,B}_{i-1}}|\epsilon_{V}+|I_{S^{M}_{i-1}}|\epsilon_{R}+\epsilon_{i-1}\geq
u^{G}_{\vartriangle}(\sigma^{NE})$. Accumulating the errors in the last
subgame we have
$u^{G^{M}}_{\vartriangle}(\sigma^{\mathcal{R}}_{\vartriangle},BR(\sigma^{\mathcal{R}}_{\vartriangle}))+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{O}}|(1-p)\epsilon_{V}+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}$.
However, we still need to show it works for
$u^{G}_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma_{\triangledown}^{F})$.
We can do it by replacing strategy of player $\triangledown$ in the
$G^{\prime}$ by $\sigma_{\triangledown}^{F}$ which will effectively transform
$G^{M}$ game back to $G$ with player $\triangledown$ playing
$\sigma_{\triangledown}^{F}$. Since we did this transformation by changing the
strategy that was a best response the utility can only increase and
$u^{G}_{\vartriangle}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma_{\triangledown}^{F})\geq
u^{G^{M}}_{\vartriangle}(\sigma^{\mathcal{R}}_{\vartriangle},BR(\sigma_{\vartriangle}^{\mathcal{R}}))$
which concludes the proof. ∎

######  Theorem 4.

Let $G$ be any zero-sum extensive-form game with perfect recall and let
$\sigma_{\triangledown}^{\text{F}}$ be any fixed opponent’s strategy in $G$.
Then we set $G^{M}$ as restricted Nash response modification of $G$ using
$\sigma_{\triangledown}^{\text{F}}$. Let $\mathcal{P}$ be any subgame
partitioning of the game $G^{M}$ and using some $p\in\langle 0,1\rangle$, let
$\sigma_{\vartriangle}^{\mathcal{R}}$ be a CDRNR given approximation $\bar{V}$
of the optimal value function $V$ with error at most $\epsilon_{V}$,
partitioning $\mathcal{P}$ and opponent strategy
$\sigma_{\triangledown}^{\text{F}}$, which is approximated in each step with
regret at most $\epsilon_{R}$, formally
$\sigma_{\vartriangle}^{\mathcal{R}}=\sigma_{\vartriangle}^{\mathcal{R}}(\sigma_{\triangledown}^{F},p)_{V}^{\mathcal{P}}$.
Then exploitability has a bound
$\mathcal{E}(\sigma_{\vartriangle}^{\mathcal{R}})\leq\mathcal{G}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma_{\triangledown}^{F})\frac{p}{1-p}\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{O}}|(1-p)\epsilon_{V}+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}$,
$\mathcal{E}$ and $\mathcal{G}$ are defined in Section 2.

###### Proof.

We will examine the exploitability increase in each step. First, we define
gain in a single step as
$\mathcal{G}(\sigma_{\vartriangle},\sigma_{\triangledown})_{V}^{T_{i}}=u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})_{V}^{T_{i}}-u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})_{V}^{T_{i-1}}$
for $i>0$ and
$\mathcal{G}(\sigma_{\vartriangle},\sigma_{\triangledown})_{V}^{T_{0}}=u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})_{V}^{T_{0}}-u_{\vartriangle}(\sigma^{NE})$.
This is consistent with full definition of gain because sum of gains over all
steps will results in
$u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})^{G}-u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})^{T_{n}}_{V}+u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})^{T_{n}}_{V}-...-u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})^{T_{0}}_{V}+u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})^{T_{0}}_{V}-u_{\vartriangle}(\sigma^{NE})=u_{\vartriangle}(\sigma_{\vartriangle},\sigma_{\triangledown})^{G}-u_{\vartriangle}(\sigma^{NE})=\mathcal{G}(\sigma_{\vartriangle},\sigma_{\triangledown})$.
We define exploitability in a single step similarly as
$\mathcal{E}(\sigma_{\vartriangle})_{V}^{T_{i}}=u_{\triangledown}(\sigma_{\vartriangle},BR(\sigma_{\vartriangle}))_{V}^{T_{i}}-u_{\triangledown}(\sigma_{\vartriangle},BR(\sigma_{\vartriangle}))_{V}^{T_{i-1}}$
for $i>0$ and
$\mathcal{E}(\sigma_{\vartriangle})_{V}^{T_{0}}=u_{\triangledown}(\sigma_{\vartriangle},BR(\sigma_{\vartriangle}))_{V}^{T_{0}}-u_{\triangledown}(\sigma^{NE})$
and it also sums to full exploitability. In each step we approximate the
strategy in the modified game, having full utility in step written as
$\mathcal{G}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma^{F}_{\triangledown})_{V}^{T^{M}_{i}}p-\mathcal{E}(\sigma_{\vartriangle}^{\mathcal{R}})_{V}^{T^{M}_{i}}(1-p)$.
If we had exact equilibrium in the subgame this would always be at least 0.
However, we have $\bar{V}$ instead of $V$, values at the top of the gadget are
not exact and the computed strategy has regret $\epsilon_{R}$. As in the
previous proof the error is bounded by
$|I_{S^{O}}|(1-p)\epsilon_{V}+|I_{S^{M,B}_{i-1}}|\epsilon_{V}+|I_{S^{M}_{i-1}}|\epsilon_{R}$
and we can write
$\mathcal{G}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma^{F}_{\triangledown})_{V}^{T^{M}_{i}}p-\mathcal{E}(\sigma_{\vartriangle}^{\mathcal{R}})_{V}^{T^{M}_{i}}(1-p)+|I_{S^{O}}|(1-p)\epsilon_{V}+|I_{S^{M,B}_{i-1}}|\epsilon_{V}+|I_{S^{M}_{i-1}}|\epsilon_{R}\geq
0$. We reorganize the equation to get
$\mathcal{G}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma^{F}_{\triangledown})_{V}^{T^{M}_{i}}\frac{p}{1-p}+|I_{S^{O}}|(1-p)\epsilon_{V}+|I_{S^{M,B}_{i-1}}|\epsilon_{V}+|I_{S^{M}_{i-1}}|\epsilon_{R}\geq\mathcal{E}(\sigma_{\vartriangle}^{\mathcal{R}})_{V}^{T^{M}_{i}}$
and summing over all the steps gives us
$\mathcal{G}(\sigma_{\vartriangle}^{\mathcal{R}},\sigma^{F}_{\triangledown})\frac{p}{1-p}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{O}}|(1-p)\epsilon_{V}+|\mathcal{S}|\epsilon_{R}+\sum_{S\in\mathcal{S^{\prime}}}|I_{S^{B}}|\epsilon_{V}\geq\mathcal{E}(\sigma_{\vartriangle}^{\mathcal{R}})$
∎

##  Appendix D CDBR Against Nash Strategy

.5cm .5cm [rectangle node] (0)$\vartriangle$+4.5mm..3.6cm+ H[left, xshift=4mm,
yshift=2.5mm] T[right, xshift=-4mm, yshift=2.5mm]
(1)(0-1)$\triangledown$+6.5mm..2cm+ h[left, xshift=1mm,
yshift=1.2mm]2/3[right, yshift=-2.5mm, xshift=-2.5mm]1[center] t[right,
xshift=-1mm, yshift=1.2mm]1/3[left, yshift=-2.5mm, xshift=2.5mm]0[center]
(2)(0-2)$\triangledown$+6.5mm..2.8cm+ h[left, xshift=1mm,
yshift=1.2mm]2/3[right, yshift=-1.5mm, xshift=-1.5]0[center] t[right,
xshift=-1mm, yshift=1.2mm]1/3[left, yshift=-0.8mm]
(6)(2-2)$\triangledown$+6.5mm..2.2cm+ x[left, yshift=1.5mm,
xshift=1mm]1[right, yshift=-1.5mm]10[center] y[right, yshift=1.5mm,
xshift=-1mm]0[left, yshift=-1.5mm]1[center] (0-1)(0-2)

Figure 9: Example of game where step best response is worse than NE against
fixed strategy $\sigma(h)=\frac{2}{3},\sigma(x)=1$.

######  Observation 5.

An example in Figure 9 shows that CDBR can perform worse than a Nash
equilibrium against the fixed opponent because of the perfect opponent
assumption after the depth-limit. An example is a game of matching pennies
with a twist. Player $\triangledown$ can choose in the case of the tails
whether he wants to give the opponent 10 instead of only 1. A rational player
will never do it, and the equilibrium is a uniform strategy as in normal
matching pennies.

Now we have an opponent model that plays $h$ with probability $\frac{2}{3}$
and always plays $x$. The best response to the model will always play $T$ and
get payoff $\frac{10}{3}$. Nash equilibrium strategy will get payoff 2, and
CDBR with depth-limit 2 will cut the game before the $x/y$ choice. Assuming
the opponent plays perfectly after the depth-limit and chooses $y$,
$\vartriangle$ will always play $H$. Playing $H$ will result in receiving
payoff $\frac{2}{3}$, which is higher than the value of the game
($\frac{1}{2}$) but lower than what Nash equilibrium can get against the
model.

##  Appendix E Additional Empirical Results

##### CDBR

We show CDBR results on more domains that we were not able to fit in the
paper. Interestingly on small liar’s dice the CDBR is almost perfect even with
only depth one. On Goofspiel the results are similar to the results on Leduc.

Figure 10: More CDBR results on Liar’s dice.

Figure 11: Aditional results for CDRNR with different values of $p$. Generated
on Goofspiel.

##### CDRNR

We show more results for Goofspiel, Leduc Hold’em and Liar’s dice with
different values of $p$.

Figure 12: Aditional results for CDRNR with different values of $p$. Generated
on Leduc Hold’em. Figure 13: Aditional result on Liar’s dice. For every $p$ it
exactly mimics the RNR so we only show one value.