GPU-Accelerated Counterfactual Regret Minimization

## Abstract

Abstract Counterfactual regret minimization is a family of algorithms of no-regret learning dynamics capable of solving large-scale imperfect information games. We propose implementing this algorithm as a series of dense and sparse matrix and vector operations, thereby making it highly parallelizable for a graphical processing unit, at a cost of higher memory usages. Our experiments show that our implementation performs up to about 352.5 times faster than OpenSpiel’s Python implementation and up to about 22.2 times faster than OpenSpiel’s C++ implementation and the speedup becomes more pronounced as the size of the game being solved grows.

## 1 Introduction

Counterfactual regret minimization (CFR) (Zinkevich et al., ) is a family of algorithms of no-regret learning dynamics capable of solving large-scale imperfect information games. Its variants dominated the development of AI agents for large imperfect information games like Poker (Tammelin et al., ; Moravčík et al., ; Brown & Sandholm, ; ) and The Resistance: Avalon (Serrino et al., ) and were components of ReBeL (Brown et al., ) and student of games (Schmid et al., ). Notable variants of CFR are as follows: CFR+ by Tammelin () (optionally) eliminates the averaging step while improving the convergence rate; Sampling variants (Lanctot et al., ) makes a complete recursive tree traversal unnecessary; Burch et al. () proposes CFR-D in which games are decomposed into subgames; Brown & Sandholm () explores modifying CFR such as to explore alternate weighted averaging (and discounting) schemes; Xu et al. () learns a discounting technique from smaller games to be used in larger games.

We propose implementing this algorithm as a series of dense and sparse matrix and vector operations, thereby making it parallelizable for a graphical processing unit (GPU) at a cost of higher memory usages. We analyze the runtimes of our implementation with both computer processing unit (CPU) and graphical processing unit (GPU) backends and compare them to Google DeepMind’s OpenSpiel (Lanctot et al., ) implementations in Python and C++ on 8 games of differing sizes.

Our experiments show that, compared to Google DeepMind OpenSpiel’s (Lanctot et al., ) Python implementation, our GPU implementation performs about 2.7 times slower for small games but is up to about 352.5 times faster for large games. Against their C++ implementation, our performance with a GPU is up to about 75.7 times slower for small games, but is up to about 22.2 times faster for large games. Even without a GPU (i.e. with a CPU backend), our implementation shows speedups compared to the OpenSpiel baselines (from about 1.7 to 56.4 times faster than their Python implementation and from 17.0 times slower to 5.6 times faster than theirs in C++). In general, We see that the speedup becomes more pronounced as the size of the game being solved grows.

## 2 Background

The background of our work and the notations we use throughout this paper is introduced below.

### 2.1 Finite Extensive-Form Games

An extensive-form game is a powerful representation of games that allow the specification of the rules of the game, information sets, actions, actors (players and the nature), chances, and payoffs.

###### Definition 1

Formally, a finite extensive-form game (Osborne & Rubinstein, ) is a structure $\displaystyle{\mathcal{G}}=\langle{\mathcal{T}},{\mathbb{H}},f_{h},{\mathbb{A}
},f_{a},{\mathbb{I}},f_{i},\sigma_{0},u\rangle$ where:

- •
$\displaystyle{\mathcal{T}}=\langle{\mathbb{V}},v_{0},{\mathbb{T}},f_{Pa}\rangle$ is a finite game tree with a finite set of nodes (i.e. vertices) $\displaystyle{\mathbb{V}}$, a unique initial node (i.e. a root) $\displaystyle v_{0}\in{\mathbb{V}}$, a finite set of terminal nodes (i.e. leaves) $\displaystyle{\mathbb{T}}\subseteq{\mathbb{V}}$, and a parent function $\displaystyle f_{Pa}:{\mathbb{V}}_{+}\rightarrow{\mathbb{D}}$ that maps a non-initial node (i.e. a non-root) $\displaystyle v_{+}\in{\mathbb{V}}_{+}$ to an immediate predecessor (i.e. a parent) $\displaystyle d\in{\mathbb{D}}$, with $\displaystyle{\mathbb{V}}_{+}={\mathbb{V}}\backslash\{v_{0}\}$ the finite set of non-initial nodes (i.e. non-roots) and $\displaystyle{\mathbb{D}}={\mathbb{V}}\backslash{\mathbb{T}}$ the finite set of decision nodes (i.e. internal vertices),
- •
$\displaystyle{\mathbb{H}}$ is a finite set of information sets, $\displaystyle f_{h}:{\mathbb{D}}\rightarrow{\mathbb{H}}$ is an information partition of $\displaystyle{\mathbb{D}}$ associating each decision node $\displaystyle d\in{\mathbb{D}}$ to an information set $\displaystyle h\in{\mathbb{H}}$,
- •
$\displaystyle{\mathbb{A}}$ is a finite set of actions, $\displaystyle f_{a}:{\mathbb{V}}_{+}\rightarrow{\mathbb{A}}$ is an action partition of $\displaystyle{\mathbb{V}}_{+}$ associating each non-initial node $\displaystyle v_{+}\in{\mathbb{V}}_{+}$ to an action $\displaystyle a\in{\mathbb{A}}$ such that $\displaystyle\forall d\in{\mathbb{D}}$ the restriction $\displaystyle f_{a,d}:S(d)\rightarrow A(f_{h}(d))$ is a bijection, with $\displaystyle S(d\in{\mathbb{D}})=\{v_{+}\in{\mathbb{V}}_{+}:f_{Pa}(v_{+})=d\}$ the finite set of immediate successors (i.e. children) of a node $\displaystyle d\in{\mathbb{D}}$ and $\displaystyle A(h\in{\mathbb{H}})=\{a\in{\mathbb{A}}:[\exists v_{+}\in{\mathbb
{V}}_{+}](f_{h}(f_{Pa}(v_{+}))=h\land f_{a}(v_{+})=a)\}$ the finite set of available actions at an information set $\displaystyle h\in{\mathbb{H}}$,
- •
$\displaystyle{\mathbb{I}}$ is a finite set of (rational) players and, optionally, the nature (i.e. chance) $\displaystyle i_{0}\in{\mathbb{I}}$, $\displaystyle f_{i}:{\mathbb{H}}\rightarrow{\mathbb{I}}$ is a player partition of $\displaystyle{\mathbb{H}}$ associating each information set $\displaystyle h\in{\mathbb{H}}$ to a player $\displaystyle i\in{\mathbb{I}}$,
- •
$\displaystyle\sigma_{0}:{\mathbb{Q}}_{0}\rightarrow[0,1]$ is a chance probabilities function that associates each pair of a nature information set and an available action $\displaystyle(h_{0},a)\in{\mathbb{Q}}_{0}$ to an independent probability value, with $\displaystyle{\mathbb{Q}}_{j}=\{(h,a)\in{\mathbb{Q}}:h\in{\mathbb{H}}_{j}\}$ the finite set of pairs of a player information set $\displaystyle h_{j}\in{\mathbb{H}}_{j}$ and an available action $\displaystyle a\in A(h_{j})$, $\displaystyle{\mathbb{Q}}=\{(h,a)\in{\mathbb{H}}\times{\mathbb{A}}:a\in A(h)\}$ the finite set of pairs of an information set $\displaystyle h\in{\mathbb{H}}$ and an available action $\displaystyle a\in A(h)$, and $\displaystyle{\mathbb{H}}_{j}=\{h\in{\mathbb{H}}:f_{i}(h)=i_{j}\}$ the finite set of information sets associated with a player $\displaystyle i_{j}\in{\mathbb{I}}$, and
- •
$\displaystyle u:{\mathbb{T}}\times{\mathbb{I}}_{+}\rightarrow\mathbb{R}$ is a utility function that associates each pair of a terminal node $\displaystyle t\in{\mathbb{T}}$ and a (rational) player $\displaystyle i_{+}\in{\mathbb{I}}_{+}$ to a real payoff value, with ${\mathbb{I}}_{+}={\mathbb{I}}\backslash\{i_{0}\}$ the finite set of (rational) players.

###### Definition 1

### 2.2 Nash Equilibrium

Each player $\displaystyle i_{j}\in{\mathbb{I}}$ selects a player strategy $\displaystyle\sigma_{j}:{\mathbb{Q}}_{j}\rightarrow[0,1]$ from a set of player strategies $\displaystyle{\Sigma}_{j}$. A player strategy $\displaystyle\sigma_{j}\in{\Sigma}_{j}$ associates, for each player information set $\displaystyle h_{j}\in{\mathbb{H}}_{j}$, a probability distribution over a finite set of available actions $\displaystyle A(h_{j})$. A strategy profile $\displaystyle\sigma:{\mathbb{Q}}\rightarrow[0,1]$ is a direct sum of the strategies of each player $\displaystyle\sigma={\bigoplus}_{i_{j}\in{\mathbb{I}}}\sigma_{j}$ which, for each information set $\displaystyle h\in{\mathbb{H}}$, gives a probability distribution over a finite set of available actions $\displaystyle A(h)$. $\displaystyle{\Sigma}$ is a set of strategy profiles. $\displaystyle\sigma_{-j}={\bigoplus}_{i_{k}\in{\mathbb{I}}\backslash\{i_{j}\}}
\sigma_{k}$ is a direct sum of all player strategies in $\displaystyle\sigma$ except $\displaystyle\sigma_{j}$ (i.e. that of player $\displaystyle i_{j}\in{\mathbb{I}}$).

Let $\displaystyle\pi:{\Sigma}\times{\mathbb{V}}\rightarrow\mathbb{R}$ be a probability of reaching a vertex $\displaystyle v\in{\mathbb{V}}$ following a strategy profile $\displaystyle\sigma\in{\Sigma}$.

$$ $\pi(\sigma\in{\Sigma},v\in{\mathbb{V}})=\begin{cases}\sigma(f_{h}(f_{Pa}(v)),f _{a}(v))\pi(\sigma,f_{Pa}(v))&v\in{\mathbb{V}}_{+}\\ 1&v=v_{0}\\ \end{cases}$ $$

Then, define $\displaystyle\hat{u}:{\Sigma}\times{\mathbb{I}}\rightarrow\mathbb{R}$ to be an expected payoff of a (rational) player $\displaystyle i_{+}\in{\mathbb{I}}_{+}$, following a strategy profile $\displaystyle\sigma\in{\Sigma}$.

$$ $\hat{u}(\sigma\in{\Sigma},i_{+}\in{\mathbb{I}}_{+})=\sum_{t\in{\mathbb{T}}}{ \pi(\sigma,t)u(t,i_{+})}$ $$

A strategy profile $\displaystyle\sigma^{*}\in{\Sigma}$ is a Nash equilibrium, a traditional solution concept for non-cooperative games, if no player stands to gain by deviating from the strategy profile.

$$ $\forall i_{+,j}\in{\mathbb{I}}_{+}\quad\hat{u}(\sigma^{*},i_{+,j})\geq\max_{ \sigma_{j}^{\prime}\in{\Sigma}_{j}}{\hat{u}(\sigma_{j}^{\prime}\oplus\sigma^{* }_{-j},i_{+,j})}$ $$

A strategy profile that approximates a Nash equilibrium $\displaystyle\sigma^{*}$ is an $\displaystyle\bm{{\epsilon}}$-Nash equilibrium $\displaystyle\sigma^{*,{\epsilon}}\in{\Sigma}$ if

$$ $\forall i_{+,j}\in{\mathbb{I}}_{+}\quad\hat{u}(\sigma^{*,{\epsilon}},i_{+,j})+ {\epsilon}\geq\max_{\sigma_{j}^{\prime}\in{\Sigma}_{j}}{\hat{u}(\sigma_{j}^{ \prime}\oplus\sigma^{*,{\epsilon}}_{-j},i_{+,j})}$ $$

### 2.3 Counterfactual Regret Minimization

Define $\displaystyle\check{u}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}_{+}
\rightarrow\mathbb{R}$ as an expected payoff of a (rational) player $\displaystyle i_{+}\in{\mathbb{I}}_{+}$ at a node $\displaystyle v\in{\mathbb{V}}$, following a strategy profile $\displaystyle\sigma\in{\Sigma}$.

$$ $\check{u}(\sigma\in{\Sigma},v\in{\mathbb{V}},i_{+}\in{\mathbb{I}}_{+})=\begin{ cases}\sum_{s\in S(v)}\sigma(f_{h}(v),f_{a}(s))\check{u}(\sigma,s,i_{+})&v\in{ \mathbb{D}}\\ u(v,i_{+})&v\in{\mathbb{T}}\\ \end{cases}$ (1) $$

Let $\displaystyle\check{\pi}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}
\rightarrow\mathbb{R}$ be a probability of reaching a vertex $\displaystyle v\in{\mathbb{V}}$ following a strategy profile $\displaystyle\sigma\in{\Sigma}$ while ignoring a strategy of a player $\displaystyle i\in{\mathbb{I}}$.

$$ $\check{\pi}(\sigma\in{\Sigma},v\in{\mathbb{V}},i\in{\mathbb{I}})=\begin{cases} \check{\pi}(\sigma,f_{Pa}(v),i)\begin{cases}\sigma(f_{h}(f_{Pa}(v)),f_{a}(v))& f_{i}(f_{h}(f_{Pa}(v)))\neq i\\ 1&f_{i}(f_{h}(f_{Pa}(v)))=i\end{cases}&v\in{\mathbb{V}}_{+}\\ 1&v=v_{0}\\ \end{cases}$ (2) $$

Below definition shows a “counterfactual” reach probability $\displaystyle\tilde{\pi}:{\Sigma}\times{\mathbb{H}}\rightarrow\mathbb{R}$.

$$ $\tilde{\pi}(\sigma\in{\Sigma},h\in{\mathbb{H}})=\sum_{d\in{\mathbb{D}}:f_{h}(d )=h}\check{\pi}(\sigma,d,f_{i}(h))$ (3) $$

Now, let $\displaystyle\tilde{u}:{\Sigma}\times{\mathbb{H}}_{+}\rightarrow\mathbb{R}$ be a counterfactual utility, with $\displaystyle{\mathbb{H}}_{+}={\mathbb{H}}\backslash{\mathbb{H}}_{0}$ the finite set of information sets associated with (rational) players.

$$ $\tilde{u}(\sigma\in{\Sigma},h_{+}\in{\mathbb{H}}_{+})=\frac{\sum_{d\in{\mathbb {D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma,d,f_{i}(h_{+}))\check{u}(\sigma,d,f_{i} (h_{+}))}{\tilde{\pi}(\sigma,h_{+})}$ (4) $$

$\displaystyle\sigma|_{h\rightarrow a}\in{\Sigma}$ is an overrided strategy profile of $\displaystyle\sigma$ where an action $\displaystyle a\in A(h)$ is always taken at an information set $\displaystyle h\in{\mathbb{H}}$.

$$ $\sigma|_{h\rightarrow a}((h^{\prime},a^{\prime})\in{\mathbb{Q}})=\begin{cases} \bm{1}_{a=a^{\prime}}&h=h^{\prime}\\ \sigma(h^{\prime},a^{\prime})&h\neq h^{\prime}\\ \end{cases}$ $$

$\displaystyle\tilde{r}:{\Sigma}\times{\mathbb{Q}}_{+}\rightarrow\mathbb{R}$ is the instantaneous counterfactual regret, with $\displaystyle{\mathbb{Q}}_{+}={\mathbb{Q}}\backslash{\mathbb{Q}}_{0}$ the finite set of pairs of a (rational) player information set $\displaystyle h_{+}\in{\mathbb{H}}_{+}$ and an available action $\displaystyle a\in A(h_{+})$.

$$ $\tilde{r}(\sigma\in{\Sigma},(h_{+},a)\in{\mathbb{Q}}_{+})=\tilde{\pi}(\sigma,h _{+})(\tilde{u}(\sigma|_{h_{+}\rightarrow a},h_{+})-\tilde{u}(\sigma,h_{+}))$ (5) $$

$\displaystyle\bar{r}^{(T)}:{\mathbb{Q}}_{+}\rightarrow\mathbb{R}$ is the average counterfactual regret at an iteration $\displaystyle T$. $\displaystyle\sigma^{(\tau)}\in{\Sigma}$ is the strategy played at an iteration $\displaystyle\tau$.

$$ $\bar{r}^{(T)}(q_{+}\in{\mathbb{Q}}_{+})=\frac{1}{T}\sum_{\tau=1}^{T}\tilde{r}( \sigma^{(\tau)},q_{+})$ (6) $$

The strategy profile for the next iteration $\displaystyle T+1$ is $\displaystyle\sigma^{(T+1)}\in{\Sigma}$.

$$ $\sigma^{(T+1)}((h,a)\in{\mathbb{Q}})=\begin{cases}\begin{cases}\frac{(\bar{r}^ {(T)}(h,a))^{+}}{\sum_{a^{\prime}\in A(h)}(\bar{r}^{(T)}(h,a^{\prime}))^{+}}& \sum_{a^{\prime}\in A(h)}(\bar{r}^{(T)}(h,a^{\prime}))^{+}>0\\ \frac{1}{|A(h)|}&\sum_{a^{\prime}\in A(h)}(\bar{r}^{(T)}(h,a^{\prime}))^{+}=0 \end{cases}&(h,a)\in{\mathbb{Q}}_{+}\\ \sigma_{0}(h,a)&(h,a)\in{\mathbb{Q}}_{0}\\ \end{cases}$ (7) $$

Counterfactual regret minimization (Zinkevich et al., ) is an algorithm that iteratively approximates a coarse correlated equilibrium $\displaystyle\bar{\sigma}^{(T)}:{\mathbb{Q}}\rightarrow\mathbb{R}$ (Hart & Mas-Colell, ).

$$ $\bar{\sigma}^{(T)}((h,a)\in{\mathbb{Q}})=\frac{\sum_{\tau=1}^{T}\tilde{\pi}( \sigma^{(\tau)},h)\sigma^{(\tau)}(h,a)}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{( \tau)},h)}$ (8) $$

Define $\displaystyle r^{(T)}:{\mathbb{I}}_{+}\rightarrow\mathbb{R}$ as the average overall regret of a (rational) player $\displaystyle i_{+,j}\in{\mathbb{I}}_{+}$ at an iteration $\displaystyle T$.

$$ $r^{(T)}(i_{+,j}\in{\mathbb{I}}_{+})=\frac{1}{T}\max_{\sigma_{j}^{\prime}\in{ \Sigma}_{j}}\sum_{\tau=1}^{T}(\hat{u}(\sigma_{j}^{\prime}\oplus\sigma_{-j}^{( \tau)},i_{+,j})-\hat{u}(\sigma^{(\tau)},i_{+,j}))$ $$

In 2-player ($\displaystyle|{\mathbb{I}}_{+}|=2$) zero-sum games, if $\displaystyle\forall i_{+}\in{\mathbb{I}}_{+}\ r^{(T)}(i_{+})\leq{\epsilon}$, the average strategy $\displaystyle\bar{\sigma}^{(T)}$ (at an iteration $\displaystyle T$) is also a $\displaystyle 2{\epsilon}$-Nash equilibrium $\displaystyle\sigma^{*,2{\epsilon}}\in{\Sigma}$ (Zinkevich et al., ).

## 3 Implementation

In order to highly parallelize the execution of CFR, we implement the algorithm as a series of dense and sparse matrix operations and avoid costly recursive game tree traversals. Due to space constraints, expanded forms of equations throughout this section had to be relegated to Appendix D.

### 3.1 Setup

Calculating expected payoffs of (rational) players $\displaystyle\check{u}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}_{+}
\rightarrow\mathbb{R}$ in Equation 1 and “excepted” reach probability $\displaystyle\check{\pi}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}
\rightarrow\mathbb{R}$ in Equation 2 are classical problems of dynamic programming on trees. To calculate these values with matrix operations, we represent the game tree $\displaystyle{\mathcal{T}}$ as an adjacency matrix $\displaystyle{\bm{G}}\in\mathbb{R}^{{\mathbb{V}}^{2}}$ and the level graphs of the game tree $\displaystyle{\mathcal{T}}$ as adjacency matrices $\displaystyle{\bm{L}}^{(1)},{\bm{L}}^{(2)},\ldots,{\bm{L}}^{(D)}\in\mathbb{R}^
{{\mathbb{V}}^{2}}$, with $\displaystyle D=\max_{t\in{\mathbb{T}}}{d_{\mathcal{T}}(t)}$ the maximum depth of any (terminal) node in the game tree $\displaystyle{\mathcal{T}}$ and $\displaystyle d_{\mathcal{T}}:{\mathbb{V}}\rightarrow{\mathbb{Z}}$ the depth of a vertex $\displaystyle v\in{\mathbb{V}}$ in the game tree $\displaystyle{\mathcal{T}}$ from the root $\displaystyle v_{0}$.

$$ $d_{\mathcal{T}}(v\in{\mathbb{V}})=\begin{cases}1+d_{\mathcal{T}}(f_{Pa}(v))&v \in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}$ $$

$$ ${\bm{G}}=\left(\begin{cases}\bm{1}_{v=f_{Pa}(v^{\prime})}&v\in{\mathbb{D}} \land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\end{cases}\right)_{(v,v^{\prime})\in{ \mathbb{V}}^{2}}$ (9) $$

$$ $\forall l\in[1,D]\cap{\mathbb{Z}}\quad{\bm{L}}^{(l)}=\left(\begin{cases}\bm{1} _{v=f_{Pa}(v^{\prime})\land d_{\mathcal{T}}(v^{\prime})=l}&v\in{\mathbb{D}} \land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\end{cases}\right)_{(v,v^{\prime})\in{ \mathbb{V}}^{2}}$ (10) $$

We also define matrices $\displaystyle{\bm{M}}^{(Q_{+},V)}\in\mathbb{R}^{{\mathbb{Q}}_{+}\times{\mathbb
{V}}},{\bm{M}}^{(H_{+},Q_{+})}\in\mathbb{R}^{{\mathbb{H}}_{+}\times{\mathbb{Q}
}_{+}},{\bm{M}}^{(V,I_{+})}\in\mathbb{R}^{{\mathbb{V}}\times{\mathbb{I}}_{+}}$ to represent the game $\displaystyle{\mathcal{G}}$. Matrix $\displaystyle{\bm{M}}^{(Q_{+},V)}$ describes whether a node $\displaystyle v\in{\mathbb{V}}$ is a result of an action from a (rational) player information set $\displaystyle(h_{+},a)\in{\mathbb{Q}}_{+}$. Matrix $\displaystyle{\bm{M}}^{(H_{+},Q_{+})}$ describes whether a (rational) player information set $\displaystyle h_{+}\in{\mathbb{H}}_{+}$ is the first element of the corresponding (rational) player information set-action pair $\displaystyle(h_{+},a)\in{\mathbb{Q}}_{+}$. Finally, matrix $\displaystyle{\bm{M}}^{(V,I_{+})}$ describes whether a node $\displaystyle v\in{\mathbb{V}}$ has a parent whose associated information set’s associated player is $\displaystyle i_{+}\in{\mathbb{I}}_{+}$ (i.e. which player $\displaystyle i_{+}\in{\mathbb{I}}_{+}$ acted to reach a node $\displaystyle v\in{\mathbb{V}}$). Note that we omit the nature player $\displaystyle i_{0}$ and related information sets $\displaystyle{\mathbb{H}}_{0}$ and information set-action pairs $\displaystyle{\mathbb{Q}}_{0}$ as only the strategies of (rational) players are updated by the algorithm. These mask-like matrices are later used to “select” the values associated with a player, action, node, or information set during the iteration.

$$ ${\bm{M}}^{(Q_{+},V)}=\left(\begin{cases}\bm{1}_{q_{+}=(f_{h}(f_{Pa}(v)),f_{a}( v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)_{(q_{+},v)\in{\mathbb{Q}}_{+}\times{\mathbb{V}}}$ (11) $$

$$ ${\bm{M}}^{(H_{+},Q_{+})}=\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{(h_{+},(h _{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q}}_{+}}$ (12) $$

$$ ${\bm{M}}^{(V,I_{+})}=\left(\begin{cases}\bm{1}_{f_{i}(f_{h}(f_{Pa}(v)))=i_{+}} &v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ (13) $$

$\displaystyle{\bm{G}},{\bm{L}}^{(1)},{\bm{L}}^{(2)},\ldots,{\bm{L}}^{(D)},{\bm
{M}}^{(Q_{+},V)},{\bm{M}}^{(H_{+},Q_{+})},{\bm{M}}^{(V,I_{+})}$ are constant matrices. In the games we experiment on, all aforesaid matrices except $\displaystyle{\bm{M}}^{(V,I_{+})}$ are highly sparse (as demonstrated in Table 1).(^1^11The sparsity of $\displaystyle{\bm{M}}^{(V,I_{+})}$ depends on the number of (rational) players. For games with many players, it may be more efficient to implement this as sparse as well.) As such, they are implemented as sparse matrices in a compressed sparse row (CSR) format. Matrix $\displaystyle{\bm{M}}^{(V,I_{+})}$ and all other defined matrices and vectors are implemented as dense.

**Table 1: The sparsities of sparse matrix constants in our implementation. The entries in the leftmost column correspond exactly to the game name in Deepmind’s OpenSpiel (Lanctot et al., ) library. CUDA’s (Nickolls et al., ) cuSPARSE “library targets matrices with sparsity ratios in the range between 70%-99.9%” (). Our values fall under this recommended range. We project that the matrices for games not tested in our work will typically have similar sparsity values as those we test.**
| Game (in OpenSpiel) | Sparsities (%) |  |  |  |
| --- | --- | --- | --- | --- |
| $\displaystyle{\bm{M}}^{(Q_{+},V)}$ | $\displaystyle{\bm{M}}^{(H_{+},Q_{+})}$ | $\displaystyle{\bm{L}}^{(l)}$ (Average) | $\displaystyle{\bm{G}}$ |  |
| tiny_hanabi | 96.36364 | 87.50000 | 99.64298 | 98.21488 |
| kuhn_poker | 96.55172 | 91.66667 | 99.71760 | 98.30559 |
| kuhn_poker(players=3) | 99.02755 | 97.91667 | 99.98202 | 99.83819 |
| first_sealed_auction | 99.54200 | 95.00000 | 99.99765 | 99.98591 |
| leduc_poker | 99.95730 | 99.89316 | 99.99912 | 99.98943 |
| tiny_bridge_2p | 99.98600 | 99.97210 | 99.99992 | 99.99907 |
| liars_dice | 99.99797 | 99.99593 | 99.99998 | 99.99966 |
| tic_tac_toe | 99.99982 | 99.99966 | 99.99998 | 99.99982 |

Define a dense vector $\displaystyle{\bm{s}}^{(\sigma_{0})}$ representing the probabilities of nature information set-action pairs $\displaystyle{\mathbb{Q}}_{0}$.

$$ ${\bm{s}}^{(\sigma_{0})}=\left(\begin{cases}\begin{cases}\sigma_{0}(f_{h}(f_{Pa }(v)),f_{a}(v))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}$ (14) $$

$\displaystyle{\bm{\sigma}}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$ is the strategy over (rational) player information set-action pairs $\displaystyle{\mathbb{Q}}_{+}$ at an iteration $\displaystyle T$.

$$ ${\bm{\sigma}}=\left(\sigma^{(T)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ (15) $$

A dense vector $\displaystyle{\bm{\sigma}}^{(T=1)}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$ representing the initial strategy profile (i.e. at $\displaystyle T=1$) is shown below.

$$ ${\bm{\sigma}}^{(T=1)}=\left(\sigma^{(1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{ +}}=\left(\frac{1}{|A(h_{+})|}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}=\bm{1}_{| {\mathbb{Q}}_{+}|}\oslash\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)^{\top} \left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\bm{1}_{|{\mathbb{Q}}_{+}|}\right)\right)$ (16) $$

On each iteration, the strategy at the next iteration $\displaystyle{\bm{\sigma}}^{\prime}=\left(\sigma^{(T+1)}(q_{+})\right)_{q_{+}
\in{\mathbb{Q}}_{+}}$ is calculated using $\displaystyle{\bm{\sigma}}$.

### 3.2 Iteration

#### 3.2.1 Tree Traversal

Let a dense vector $\displaystyle{\bm{s}}\in\mathbb{R}^{{\mathbb{V}}}$ represent the probabilities of taking an action that reaches a node $\displaystyle v\in{\mathbb{V}}$ at an iteration $\displaystyle T$. This value is irrelevant for the unique initial node $\displaystyle v_{0}$.

$$ ${\bm{s}}=\left(\begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v)),f_{a}(v))&v\in{ \mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}=\left({\bm{M}}^{(Q_{+},V)}\right)^{\top} {\bm{\sigma}}+{\bm{s}}^{(\sigma_{0})}$ (17) $$

For later use, we also broadcast the vector $\displaystyle{\bm{s}}$ to be a matrix $\displaystyle{\bm{S}}\in\mathbb{R}^{{\mathbb{V}}^{2}}$. This is defined only for notational convenience and, in our implementation, this matrix is not actually stored in memory.

$$ ${\bm{S}}=\left({\bm{s}}_{v^{\prime}}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}$ (18) $$

The recurrence relations of the expected payoffs of (rational) players $\displaystyle\check{u}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}_{+}
\rightarrow\mathbb{R}$ (see Equation 1) is expresssed with matrices. Define the dense matrices $\displaystyle\widecheck{{\bm{U}}}^{(1)},\widecheck{{\bm{U}}}^{(2)},\ldots,
\widecheck{{\bm{U}}}^{(D+1)}\in\mathbb{R}^{{\mathbb{V}}\times{\mathbb{I}}_{+}}$.

$$ $\forall l\in[1,D+1]\cap{\mathbb{Z}}\quad\widecheck{{\bm{U}}}^{(l)}=\left( \begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T}}(v)\geq l-1\lor v \in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v)<l-1\land v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ (19) $$

$$ $\widecheck{{\bm{U}}}^{(D+1)}=\left(\begin{cases}u(v,i_{+})&v\in{\mathbb{T}}\\ 0&v\in{\mathbb{D}}\end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I }}_{+}}$ (20) $$

$$ $\forall l\in[1,D]\cap{\mathbb{Z}}\quad\widecheck{{\bm{U}}}^{(l)}=\left({\bm{L} }^{(l)}\odot{\bm{S}}\right)\widecheck{{\bm{U}}}^{(l+1)}+\widecheck{{\bm{U}}}^{ (l+1)}$ (21) $$

Let a dense matrix $\displaystyle\widecheck{{\bm{U}}}\in\mathbb{R}^{{\mathbb{V}}\times{\mathbb{I}}
_{+}}$ represent $\displaystyle\check{u}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}_{+}
\rightarrow\mathbb{R}$.

$$ $\widecheck{{\bm{U}}}=\left(\check{u}(\sigma^{(T)},v,i_{+})\right)_{(v,i_{+}) \in{\mathbb{V}}\times{\mathbb{I}}_{+}}=\widecheck{{\bm{U}}}^{(1)}$ (22) $$

Let $\displaystyle\widecheck{{\bm{S}}}\in\mathbb{R}^{{\mathbb{V}}\times{\mathbb{I}}
_{+}}$ be a dense matrix to be used in a later calculation.

$$ $\widecheck{{\bm{S}}}=\left(\begin{cases}{\bm{s}}_{v}&\left({\bm{M}}^{(V,I_{+}) }\right)_{v,i_{+}}=0\\ 1&\left({\bm{M}}^{(V,I_{+})}\right)_{v,i_{+}}=1\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ (23) $$

In order to represent a restriction (ignoring nature) of the “excepted” reach probabilities (defined in Equation 2) $\displaystyle\check{\pi}:{\Sigma}\times{\mathbb{V}}\times{\mathbb{I}}
\rightarrow\mathbb{R}$ with matrices, we, again, express the recurrence relations with matrices. We therefore define the following dense matrices: $\displaystyle\widecheck{{\bm{\Pi}}}^{(0)},\widecheck{{\bm{\Pi}}}^{(1)},
\widecheck{{\bm{\Pi}}}^{(2)},\ldots,\widecheck{{\bm{\Pi}}}^{(D)}\in\mathbb{R}^
{{\mathbb{V}}\times{\mathbb{I}}_{+}}$.

$$ $\forall l\in[0,D]\cap{\mathbb{Z}}\quad\widecheck{{\bm{\Pi}}}^{(l)}=\left( \begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T}}(v)\leq l\\ 0&d_{\mathcal{T}}(v)>l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ (24) $$

$$ $\widecheck{{\bm{\Pi}}}^{(0)}=\left(\bm{1}_{v=v_{0}}\right)_{(v,i_{+})\in{ \mathbb{V}}\times{\mathbb{I}}_{+}}$ (25) $$

$$ $\forall l\in[1,D]\cap{\mathbb{Z}}\quad\widecheck{{\bm{\Pi}}}^{(l)}=\left(\left ({\bm{L}}^{(l)}\right)^{\top}\widecheck{{\bm{\Pi}}}^{(l-1)}\right)\odot \widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ (26) $$

Let a dense vector $\displaystyle\widecheck{{\bm{\pi}}}\in\mathbb{R}^{{\mathbb{V}}}$ be the terms in Equation 3 for “counterfactual” reach probabilities $\displaystyle\tilde{\pi}:{\Sigma}\times{\mathbb{H}}\rightarrow\mathbb{R}$.

$$ $\widecheck{{\bm{\pi}}}=\left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T) },v,f_{i}(f_{h}(f_{Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}=\left({\bm{M}}^{(V,I_{+})}\odot \widecheck{{\bm{\Pi}}}^{(D)}\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ (27) $$

#### 3.2.2 Average Strategy Profile

The average strategy profile $\displaystyle\bar{\sigma}^{(T)}:{\mathbb{Q}}\rightarrow\mathbb{R}$ at an iteration $\displaystyle T$, formulated in Equation 8 and represented as a dense vector $\displaystyle\widebar{{\bm{\sigma}}}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$, can be updated from the previous iteration’s $\displaystyle\bar{\sigma}^{(T-1)}:{\mathbb{Q}}\rightarrow\mathbb{R}$, represented as a dense vector $\displaystyle\widebar{{\bm{\sigma}}}^{\prime}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$. For this, the “counterfactual” reach probabilities $\displaystyle\tilde{\pi}:{\Sigma}\times{\mathbb{H}}\rightarrow\mathbb{R}$ (Equation 3), a restriction of which is represented by a dense vector $\displaystyle\widetilde{{\bm{\pi}}}\in\mathbb{R}^{{\mathbb{H}}_{+}}$, and their sums, a restriction of which is represented by a dense vector $\displaystyle\widetilde{{\bm{\pi}}}^{(\Sigma)}\in\mathbb{R}^{{\mathbb{H}}_{+}}$, must be calculated. The previous sums of “counterfactual” reach probabilities is denoted as a dense vector $\displaystyle\widetilde{{\bm{\pi}}}^{(\Sigma)\prime}\in\mathbb{R}^{{\mathbb{H}
}_{+}}$.

$$ $\widetilde{{\bm{\pi}}}=\left(\tilde{\pi}(\sigma^{(T)},h_{+})\right)_{h_{+}\in{ \mathbb{H}}_{+}}=\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\left({\bm{M}}^{(Q _{+},V)}\right)\widecheck{{\bm{\pi}}}\right)\oslash\left(\left({\bm{M}}^{(H_{+ },Q_{+})}\right)\bm{1}_{|{\mathbb{Q}}_{+}|}\right)$ (28) $$

$$ $\widetilde{{\bm{\pi}}}^{(\Sigma)}=\left(\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{( \tau)},h_{+})\right)_{h_{+}\in{\mathbb{H}}_{+}}=\widetilde{{\bm{\pi}}}^{( \Sigma)\prime}+\widetilde{{\bm{\pi}}}$ (29) $$

$$ $\widebar{{\bm{\sigma}}}=\left(\bar{\sigma}^{(T)}(q_{+})\right)_{q_{+}\in{ \mathbb{Q}}_{+}}=\widebar{{\bm{\sigma}}}^{\prime}+\left(\left({\bm{M}}^{(H_{+} ,Q_{+})}\right)^{\top}\left(\widetilde{{\bm{\pi}}}\oslash\widetilde{{\bm{\pi}} }^{(\Sigma)}\right)\right)\odot\left({\bm{\sigma}}-\widebar{{\bm{\sigma}}}^{ \prime}\right)$ (30) $$

#### 3.2.3 Next Strategy Profile

Let a dense vector $\displaystyle\widetilde{{\bm{r}}}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$ represent instantaneous counterfactual regrets $\displaystyle\tilde{r}:{\Sigma}\times{\mathbb{Q}}_{+}\rightarrow\mathbb{R}$, defined in Equation 5, for a strategy profile $\displaystyle\sigma^{(T)}$ at an iteration $\displaystyle T$.

$$ $\widetilde{{\bm{r}}}=\left(\tilde{r}(\sigma^{(T)},q_{+})\right)_{q_{+}\in{ \mathbb{Q}}_{+}}=\left({\bm{M}}^{(Q_{+},V)}\right)\left(\widecheck{{\bm{\pi}}} \odot\left(\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{\bm{U }}}-{\bm{G}}^{\top}\widecheck{{\bm{U}}}\right)\right)\bm{1}_{|{\mathbb{I}}_{+} |}\right)\right)$ (31) $$

Average counterfactual regrets $\displaystyle\bar{r}^{(T)}:{\mathbb{Q}}_{+}\rightarrow\mathbb{R}$ in Equation 6 can be represented with a dense vector $\displaystyle\widebar{{\bm{r}}}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$. Let a dense vector $\displaystyle\widebar{{\bm{r}}}^{\prime}\in\mathbb{R}^{{\mathbb{Q}}_{+}}$ be the average counterfactual regrets at the previous iteration $\displaystyle\bar{r}^{(T-1)}:{\mathbb{Q}}_{+}\rightarrow\mathbb{R}$.

$$ $\widebar{{\bm{r}}}=\left(\bar{r}^{(T)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+} }=\widebar{{\bm{r}}}^{\prime}+\frac{1}{T}\left(\widetilde{{\bm{r}}}-\widebar{{ \bm{r}}}^{\prime}\right)$ (32) $$

The clipped regrets are normalized to get a restriction of the next strategy profile $\displaystyle\sigma^{(T+1)}:{\mathbb{Q}}_{+}\rightarrow\mathbb{R}$ from Equation 7 for (rational) player information set-action pairs, represented as a dense vector $\displaystyle{\bm{\sigma}}^{\prime}$.

$$ $\widebar{{\bm{r}}}^{(+,\Sigma)}=\left(\sum_{a^{\prime}\in A(h_{+})}\left(\bar{ r}^{(T)}(h_{+},a^{\prime})\right)^{+}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}= \left({\bm{M}}^{(H_{+},Q_{+})}\right)^{\top}\left(\left({\bm{M}}^{(H_{+},Q_{+} )}\right)\widebar{{\bm{r}}}^{+}\right)$ (33) $$

$$ ${\bm{\sigma}}^{\prime}=\left(\sigma^{(T+1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q} }_{+}}=\left(\begin{cases}\left(\widebar{{\bm{r}}}^{+}\oslash\widebar{{\bm{r}} }^{(+,\Sigma)}\right)_{q_{+}}&\left(\widebar{{\bm{r}}}^{(+,\Sigma)}\right)_{q_ {+}}>0\\ \left({\bm{\sigma}}^{(T=1)}\right)_{q_{+}}&\left(\widebar{{\bm{r}}}^{(+,\Sigma )}\right)_{q_{+}}=0\\ \end{cases}\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ (34) $$

## 4 Benchmarks

**Table 2: The average per-iteration runtimes of CFR implementations: reference OpenSpiel’s (Lanctot et al., ) and ours (with a CPU or a GPU). The performances of the fastest implementation for each game are bolded. The games are sorted by the number of nodes in the game tree and their names in the first column correspond exactly to the game name in Deepmind’s OpenSpiel (Lanctot et al., ) library. A similar table showing speedups or slowdowns are shown in Appendix B.**
| Game (in OpenSpiel) | Average CFR Iteration Runtime (seconds) |  |  |  |
| --- | --- | --- | --- | --- |
| OpenSpiel | Ours |  |  |  |
| Python | C++ | CPU | GPU |  |
| tiny_hanabi | 0.00085 | 0.00003 | 0.00051 | 0.00227 |
| kuhn_poker | 0.00101 | 0.00004 | 0.00061 | 0.00271 |
| kuhn_poker(players=3) | 0.01522 | 0.00072 | 0.00102 | 0.00383 |
| first_sealed_auction | 0.08123 | 0.00370 | 0.00144 | 0.00283 |
| leduc_poker | 0.15373 | 0.01544 | 0.00277 | 0.00467 |
| tiny_bridge_2p | 0.64078 | 0.03752 | 0.01936 | 0.00480 |
| liars_dice | 1.35128 | 0.09811 | 0.07802 | 0.00766 |
| tic_tac_toe | 2.62992 | 0.16539 | 0.11971 | 0.00746 |

We run 1,000 CFR iterations on 8 games of varying sizes implemented in Google DeepMind’s OpenSpiel (Lanctot et al., ) (see Appendix A for more details) using their Python and C++ CFR implementations and our implementations (with a CPU or GPU backend). The games represent a diverse range of sizes from small (tiny Hanabi and Kuhn poker), medium (Kuhn poker (3-player), first sealed auction, and Leduc poker), to large (tiny bridge (2-player), liar’s dice, and tic-tac-toe).

In our GPU implementation (written in Python), we use CuPy (Okuta et al., ) for GPU-accelerated matrix and vector operations. We also simply run our implementation with NumPy (Harris et al., ) and SciPy (Virtanen et al., ) (i.e. without a GPU) which we refer to as our CPU implementation. Our testbench computer contains an AMD Ryzen 9 3900X 12-core, 24-thread desktop processor, 128 GB memory, and Nvidia GeForce RTX 4090 24 GB VRAM graphics card.

Figure: Figure 1: Pairs of plots for each game tested showing the runtimes for up to 1,000 iterations and a bar graph showing the average runtimes per iteration for four implementations of CFR: Deepmind’s OpenSpiel (Lanctot et al., ) CFR implementation in Python and C++ and our implementation with a CPU or GPU backend.
Refer to caption: x1.png

Figure: Figure 2: A log-log graph showing the average CFR iteration runtime with respect to the game size. The four lines show the runtimes of Deepmind’s OpenSpiel (Lanctot et al., ) CFR implementation in Python and C++ and our implementation with a CPU or GPU backend.
Refer to caption: x17.png

The results are tabulated in Table 2 and plotted in Figure 1. The results vary depending on the size of the game being played. The relationship between the game sizes and the runtimes of each implementation is shown more clearly in the log-log graph in Figure 2. Note that our GPU implementation clearly scales better than both OpenSpiel’s (Lanctot et al., ) and our CPU implementation.

### 4.1 Small Games: Tiny Hanabi and Kuhn Poker

In small games like tiny Hanabi (55 nodes) and Kuhn poker (58 nodes), our CPU implementation shows modest gains over the OpenSpiel’s (Lanctot et al., ) Python baseline (about 1.7 times faster for both). However, our GPU implementation is actually about 2.7 times slower for both compared to OpenSpiel’s Python baseline. OpenSpiel’s C++ baseline vastly outperforms all others by at least an order of magnitude. This suggests the overheads from GPU and Python make our implementation impractical for games of similarly small sizes.

### 4.2 Medium Games: Kuhn Poker (3-Player), First Sealed Auction, and Leduc Poker

In medium-sized games like Kuhn poker (3-player) (617 nodes), first sealed auction (7096 nodes), and Leduc poker (9457 nodes), performance gains compared to OpenSpiel’s (Lanctot et al., ) Python implementation can be observed for both our CPU (about 14.9, 56.4, and 55.5 times faster, respectively) and GPU implementation (about 4.0, 28.7, and 32.9 times faster, respectively). However, comparisons with OpenSpiel’s C++ implementation is mixed. For Kuhn poker (3-player), OpenSpiel’s C++ implementation is about 1.4 times faster than our CPU implementation and 5.3 times faster than our GPU implementation. But, for first sealed auction and Leduc poker, our CPU implementation is about 2.6 and 5.6 times faster, respectively, and our GPU implementation is about 1.3 and 3.3 times faster, respectively, than their C++ baseline. Here, while we begin to see our implementations outperform OpenSpiel’s baselines, we see that our CPU implementation is faster than our GPU implementation. This suggests that, while the efficiency of our implementation overcomes the Python overhead, the remaining GPU overhead makes using a GPU less preferable than not.

### 4.3 Large Games: Tiny Bridge (2-Player), Liar’s Dice, and Tic-Tac-Toe

In games like tiny bridge (2-player) (107129 nodes), liar’s dice (294883 nodes), and tic-tac-toe (549946 nodes), noticeable performance gains over OpenSpiel’s (Lanctot et al., ) Python implementation can be observed for both our CPU (about 33.1, 17.3, and 22.0 times faster, respectively) and GPU implementation (about 133.5, 176.4, and 352.5 times faster, respectively). The same can be said for OpenSpiel’s C++ implementation to a lesser degree: our CPU implementation is about 1.9, 1.3, and 1.4 times faster, respectively, and our GPU implementation is about 7.8, 12.8, and 22.2 times faster, respectively. Here, the performance benefits of utilizing a GPU is clear, and we predict that the differences will be even more pronounced for games of sizes larger than the ones explored.

The total allocated CUDA memory by our GPU implementation to solve each game is plotted in Figure 3, and the peak memory usages of the benchmark scripts are shown in Table 3. Note that this is not a fair comparison, as, in our implementations, we unnecessarily store the object representations of all states. By not doing so, further reduction in process memory usages would be possible.

## 5 Discussion

In this work, we only explore parallelizing the vanilla CFR algorithm, as proposed by Zinkevich et al. (). Later variants of CFR show improvements, namely in convergence speeds, which modify various aspects of the algorithm. The discounting techniques proposed by Brown and Sandholm can trivially be applied by altering Equation 32 and Equation 30. However, pruning techniques (Brown & Sandholm, ) and alternating player updates (Burch et al., ) would require non-trivial manipulations on the game-related matrices – possibly between iterations – problematic since updating certain types of sparse matrices like the CSR format we use is computationally expensive.

Figure: Figure 3: A log-log graph showing the total allocated CUDA memory by our GPU implementation with respect to the game size. The values are tabulated in Appendix C.
Refer to caption: x18.png

Unlike sampling variants of CFR (Lanctot et al., ), on each iteration, our implementation deals with the entire game tree and stores values for every node – impractical for extremely large games. In traditional implementations of CFR, while a complete recursive game tree traversal is carried out, counterfactual values are typically not stored for each node but instead for each information set-actions. We demonstrate that it is possible to achieve a significant parallelization (and hence speedup) at a cost of higher memory usage. Our approach is also much easier (and likely more efficient) to be run on supercomputers compared to previous methods (Tammelin et al., ). Intuitively, the root-to-leaf paths can be partitioned to construct subgraphs of which separate adjacency and submask matrices can be loaded and applied as necessary. This may address the memory issue.

In our GPU implementation, we used CuPy (Okuta et al., ) without any customizations in configurations and did not profile or probe into resource usages. A careful analysis of these for further optimizations will most likely yield further performance improvements.

## 6 Conclusion

We introduce our implementation of CFR, designed to be highly parallelized by computing each iteration as dense and sparse matrix and vector operations and eliminating costly recursive tree traversal. While our goal was to run the algorithm on a GPU, the tight nature of our code also allows for a vastly more efficient computation when a GPU is not leveraged. Our experiments on solving 8 games of differing sizes show that, in larger games, our implementation achieves orders of magnitude performance improvements over Google DeepMind’s OpenSpiel (Lanctot et al., ) baselines in Python and C++, and predict that the performance benefit will be even more pronounced for games of sizes larger than those we tested. Addressing the memory inefficiency and incorporating the use of a GPU with non-vanilla CFR variants remains a promising avenue for future research.

## Appendix A Game Properties

**Table 4: The 8 games tested in our benchmark and relevant statistics: number of nodes, terminal nodes, information sets, actions, and (rational) players. The games are sorted by the number of nodes in the game tree and their names in the first column correspond exactly to the game name in Deepmind’s OpenSpiel (Lanctot et al., ) library.**
| Game (in OpenSpiel) | # Nodes | # Terminals | # Infosets | # Actions | # Players |
| --- | --- | --- | --- | --- | --- |
| tiny_hanabi | 55 | 36 | 11 | 3 | 2 |
| kuhn_poker | 58 | 30 | 16 | 3 | 2 |
| kuhn_poker(players=3) | 617 | 312 | 65 | 4 | 3 |
| first_sealed_auction | 7096 | 3410 | 3056 | 11 | 2 |
| leduc_poker | 9457 | 5520 | 1093 | 6 | 2 |
| tiny_bridge_2p | 107129 | 53340 | 3613 | 28 | 2 |
| liars_dice | 294883 | 147420 | 24583 | 13 | 2 |
| tic_tac_toe | 549946 | 255168 | 294778 | 9 | 2 |

Table 4 give details (e.g. number of nodes, terminal nodes, information sets, actions, and players) about the games we solve during our experimentation.

## Appendix B Speedups and slowdowns

**Table 5: The average per-iteration speedups or slowdowns in runtimes of our CFR implementations over reference OpenSpiel’s (Lanctot et al., ). The positive values represent speedups and the negative values represent the slowdowns. The games are sorted by the number of nodes in the game tree and their names in the first column correspond exactly to the game name in Deepmind’s OpenSpiel (Lanctot et al., ) library. A similar table showing the original raw runtime values are shown in Table 2.**
| Game (in OpenSpiel) | Average Speedup or Slowdown (times) |  |  |  |
| --- | --- | --- | --- | --- |
| OpenSpiel’s Python | OpenSpiel’s C++ |  |  |  |
| Our CPU | Our GPU | Our CPU | Our GPU |  |
| tiny_hanabi | 1.7 | -2.7 | -17.0 | -75.7 |
| kuhn_poker | 1.7 | -2.7 | -15.2 | -67.8 |
| kuhn_poker(players=3) | 14.9 | 4.0 | -1.4 | -5.3 |
| first_sealed_auction | 56.4 | 28.7 | 2.6 | 1.3 |
| leduc_poker | 55.5 | 32.9 | 5.6 | 3.3 |
| tiny_bridge_2p | 33.1 | 133.5 | 1.9 | 7.8 |
| liars_dice | 17.3 | 176.4 | 1.3 | 12.8 |
| tic_tac_toe | 22.0 | 352.5 | 1.4 | 22.2 |

The speedups or slowdowns of our implementation (with a GPU or a CPU backend) compared to OpenSpiel’s baselines (Python or C++ implementation) is tabulated in Table 5.

## Appendix C Total Allocated CUDA Memory

**Table 6: The total allocated CUDA memory during CFR iterations for each game experimented on. The games are sorted by the number of nodes in the game tree and their names in the first column correspond exactly to the game name in Deepmind’s OpenSpiel (Lanctot et al., ) library. A similar table showing the original raw runtime values are shown in Table 2.**
| Game (in OpenSpiel) | Total Allocated CUDA Memory (MB) |
| --- | --- |
| tiny_hanabi | 0.02867 |
| kuhn_poker | 0.03021 |
| kuhn_poker(players=3) | 0.23091 |
| first_sealed_auction | 1.68294 |
| leduc_poker | 2.92045 |
| tiny_bridge_2p | 31.89914 |
| liars_dice | 95.29395 |
| tic_tac_toe | 190.86490 |

The total allocated CUDA memory by CuPy (Okuta et al., ) in our GPU implementation to solve each game through CFR is tabulated in Table 6.

## Appendix D Expanded Equations

Subsections D.1, D.2, D.3, D.4, D.5, D.6, D.7, D.8, D.9, D.10, D.11, and D.12 show expanded forms of equations shown in Section 3.

### D.1 Initial Strategy Profile

An expanded form of Equation 16 is shown below.

$$ $\displaystyle{\bm{\sigma}}^{(T=1)}$ $\displaystyle=\left(\sigma^{(1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\frac{1}{|A(h_{+})|}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(|A(h_{+})|\right)_{(h_{+ },a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\sum_{h_{+}^{\prime}\in{ \mathbb{H}}_{+}}\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)|A(h_{+}^{\prime})| \right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left(\left(\bm{1}_{h_{+ }=h_{+}^{\prime}}\right)_{((h_{+},a),h_{+}^{\prime})\in{\mathbb{Q}}_{+}\times{ \mathbb{H}}_{+}}\right)\left(|A(h_{+})|\right)_{h_{+}\in{\mathbb{H}}_{+}}\right)$ $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left(\left(\bm{1}_{h_{+ }=h_{+}^{\prime}}\right)_{(h_{+},(h_{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{ \mathbb{Q}}_{+}}\right)^{\top}\left(|A(h_{+})|\right)_{h_{+}\in{\mathbb{H}}_{+ }}\right)$ Using Equation 12 $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left({\bm{M}}^{(H_{+},Q _{+})}\right)^{\top}\left(|A(h_{+})|\right)_{h_{+}\in{\mathbb{H}}_{+}}\right)$ $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left({\bm{M}}^{(H_{+},Q _{+})}\right)^{\top}\left(\sum_{(h_{+}^{\prime},a)\in{\mathbb{Q}}_{+}}\bm{1}_{ h_{+}=h_{+}^{\prime}}\right)_{h_{+}\in{\mathbb{H}}_{+}}\right)$ $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left({\bm{M}}^{(H_{+},Q _{+})}\right)^{\top}\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{(h_{+},( h_{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q}}_{+}}\right)\bm{1}_{|{ \mathbb{Q}}_{+}|}\right)$ Using Equation 12 $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left({\bm{M}}^{(H_{+},Q _{+})}\right)^{\top}\left({\bm{M}}^{(H_{+},Q_{+})}\right)\bm{1}_{|{\mathbb{Q}} _{+}|}\right)$ To take advantage of the sparsity of $\displaystyle{\bm{M}}^{(H_{+},Q_{+})}$ (see Table 1 ) $\displaystyle=\bm{1}_{|{\mathbb{Q}}_{+}|}\oslash\left(\left({\bm{M}}^{(H_{+},Q _{+})}\right)^{\top}\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\bm{1}_{|{ \mathbb{Q}}_{+}|}\right)\right)$ $$

### D.2 Strategies

An expanded form of Equation 17 is shown below.

$$ $\displaystyle{\bm{s}}$ $\displaystyle=\left(\begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v)),f_{a}(v))&v\in{ \mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}$ $\displaystyle=\left(\begin{cases}\begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v)),f_ {a}(v))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)_{v\in{\mathbb{V}}}$ $\displaystyle\qquad+\left(\begin{cases}\begin{cases}\sigma_{0}(f_{h}(f_{Pa}(v) ),f_{a}(v))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}$ Using Equation 14 $\displaystyle=\left(\begin{cases}\begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v)),f_ {a}(v))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)_{v\in{\mathbb{V}}}+{\bm{s}}^{(\sigma_{0})}$ $\displaystyle=\left(\begin{cases}\sum_{h_{+}\in{\mathbb{H}}_{+}}\left(\bm{1}_{ h_{+}=f_{h}(f_{Pa}(v))}\right)\sigma^{(T)}(h_{+},f_{a}(v))&v\in{\mathbb{V}}_{+ }\\ 0&v=v_{0}\end{cases}\right)_{v\in{\mathbb{V}}}+{\bm{s}}^{(\sigma_{0})}$ $\displaystyle=\left(\begin{cases}\sum_{q_{+}\in{\mathbb{Q}}_{+}}\left(\bm{1}_{ q_{+}=(f_{h}(f_{Pa}(v)),f_{a}(v))}\right)\sigma^{(T)}(q_{+})&v\in{\mathbb{V}}_ {+}\\ 0&v=v_{0}\end{cases}\right)_{v\in{\mathbb{V}}}+{\bm{s}}^{(\sigma_{0})}$ $\displaystyle=\left(\left(\begin{cases}\bm{1}_{q_{+}=(f_{h}(f_{Pa}(v)),f_{a}(v ))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)_{(v,q_{+})\in{\mathbb{V}}\times{\mathbb{Q}}_{+}} \right)\left(\sigma^{(T)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}+{\bm{s}}^{( \sigma_{0})}$ $\displaystyle=\left(\left(\begin{cases}\bm{1}_{q_{+}=(f_{h}(f_{Pa}(v)),f_{a}(v ))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)_{(q_{+},v)\in{\mathbb{Q}}_{+}\times{\mathbb{V}}} \right)^{\top}\left(\sigma^{(T)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}+{\bm {s}}^{(\sigma_{0})}$ Using Equation 11 and Equation 15 $\displaystyle=\left({\bm{M}}^{(Q_{+},V)}\right)^{\top}{\bm{\sigma}}+{\bm{s}}^{ (\sigma_{0})}$ $$

### D.3 Expected Payoffs

#### D.3.1 Initial Condition

An expanded form of Equation 20 is shown below.

$$ $\displaystyle\widecheck{{\bm{U}}}^{(D+1)}$ $\displaystyle=\left.\left(\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d _{\mathcal{T}}(v)\geq l-1\lor v\in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v)<l-1\land v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \right|_{l=D+1}$ $\displaystyle=\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T }}(v)\geq D\lor v\in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v)<D\land v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ Since $\displaystyle\forall d\in{\mathbb{D}}\quad d_{\mathcal{T}}(d)<D=\max_{t\in{ \mathbb{T}}}{d_{\mathcal{T}}(t)}$ $\displaystyle=\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&v\in{\mathbb{ T}}\\ 0&v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ Using Equation 1 $\displaystyle=\left(\begin{cases}\begin{cases}\sum_{s\in S(v)}\sigma^{(T)}(f_{ h}(v),f_{a}(s))\check{u}(\sigma^{(T)},s,i_{+})&v\in{\mathbb{D}}\\ u(v,i_{+})&v\in{\mathbb{T}}\\ \end{cases}&v\in{\mathbb{T}}\\ 0&v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\begin{cases}u(v,i_{+})&v\in{\mathbb{T}}\\ 0&v\in{\mathbb{D}}\end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I }}_{+}}$ $$

#### D.3.2 Recurrence

An expanded form of Equation 21 is shown below.

$$ $\displaystyle\forall l\in[1,D]\cap{\mathbb{Z}}$ $\displaystyle\widecheck{{\bm{U}}}^{(l)}$ $\displaystyle=\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T }}(v)\geq l-1\lor v\in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v)<l-1\land v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T }}(v)=l-1\land v\in{\mathbb{D}}\\ 0&d_{\mathcal{T}}(v)\neq l-1\lor v\in{\mathbb{T}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&(d_{ \mathcal{T}}(v)\neq l-1\lor v\in{\mathbb{T}})\land(d_{\mathcal{T}}(v)\geq l-1 \lor v\in{\mathbb{T}})\\ 0&(d_{\mathcal{T}}(v)=l-1\land v\in{\mathbb{D}})\lor(d_{\mathcal{T}}(v)<l-1 \land v\in{\mathbb{D}})\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T }}(v)=l-1\land v\in{\mathbb{D}}\\ 0&d_{\mathcal{T}}(v)\neq l-1\lor v\in{\mathbb{T}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{ \mathcal{T}}(v)\geq l\lor v\in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v)<l\land v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ Using Equation 19 $\displaystyle=\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T }}(v)=l-1\land v\in{\mathbb{D}}\\ 0&d_{\mathcal{T}}(v)\neq l-1\lor v\in{\mathbb{T}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\widecheck {{\bm{U}}}^{(l+1)}$ Using Equation 1 $\displaystyle=\left(\begin{cases}\begin{cases}\sum_{s\in S(v)}\sigma^{(T)}(f_{ h}(v),f_{a}(s))\check{u}(\sigma^{(T)},s,i_{+})&v\in{\mathbb{D}}\\ u(v,i_{+})&v\in{\mathbb{T}}\\ \end{cases}&d_{\mathcal{T}}(v)=l-1\land v\in{\mathbb{D}}\\ 0&d_{\mathcal{T}}(v)\neq l-1\lor v\in{\mathbb{T}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\begin{cases}\sum_{s\in S(v)}\sigma^{(T)}(f_{h}(v),f_{a}(s ))\check{u}(\sigma^{(T)},s,i_{+})&d_{\mathcal{T}}(v)=l-1\land v\in{\mathbb{D}} \\ 0&d_{\mathcal{T}}(v)\neq l-1\lor v\in{\mathbb{T}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\begin{cases}\sum_{s\in S(v)}\left(\bm{1}_{d_{\mathcal{T}} (s)=l}\right)\sigma^{(T)}(f_{h}(v),f_{a}(s))\check{u}(\sigma^{(T)},s,i_{+})&v \in{\mathbb{D}}\\ 0&v\in{\mathbb{T}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\widecheck {{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\sum_{v^{\prime}\in{\mathbb{V}}}\begin{cases}\left(\bm{1}_ {v=f_{Pa}(v^{\prime})\land d_{\mathcal{T}}(v^{\prime})=l}\right)\sigma^{(T)}(f _{h}(v),f_{a}(v^{\prime}))\check{u}(\sigma^{(T)},v^{\prime},i_{+})&v\in{ \mathbb{D}}\land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\sum_{v^{\prime}\in{\mathbb{V}}}\left(\begin{cases}\left( \bm{1}_{v=f_{Pa}(v^{\prime})\land d_{\mathcal{T}}(v^{\prime})=l}\right)\sigma^ {(T)}(f_{h}(v),f_{a}(v^{\prime}))&v\in{\mathbb{D}}\land v^{\prime}\in{\mathbb{ V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)\vphantom{\left(\begin{cases}\check{u}(\sigma^{(T)},v^{ \prime},i_{+})&d_{\mathcal{T}}(v^{\prime})\geq l\lor v^{\prime}\in{\mathbb{T}} \\ 0&d_{\mathcal{T}}(v^{\prime})<l\land v^{\prime}\in{\mathbb{D}}\\ \end{cases}\right)}\right.$ $\displaystyle\qquad\left.\vphantom{\sum_{v^{\prime}\in{\mathbb{V}}}\left( \begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime})\land d_{\mathcal{T}}(v^{\prime })=l}\right)\sigma^{(T)}(f_{h}(v),f_{a}(v^{\prime}))&v\in{\mathbb{D}}\land v^{ \prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)}\left(\begin{cases}\check{u}(\sigma^{(T)},v^{\prime},i_{+}) &d_{\mathcal{T}}(v^{\prime})\geq l\lor v^{\prime}\in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v^{\prime})<l\land v^{\prime}\in{\mathbb{D}}\\ \end{cases}\right)\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+ \widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime})\land d_{ \mathcal{T}}(v^{\prime})=l}\right)\sigma^{(T)}(f_{h}(v),f_{a}(v^{\prime}))&v \in{\mathbb{D}}\land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}$ $\displaystyle\qquad\left(\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})&d_{ \mathcal{T}}(v)\geq l\lor v\in{\mathbb{T}}\\ 0&d_{\mathcal{T}}(v)<l\land v\in{\mathbb{D}}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\widecheck {{\bm{U}}}^{(l+1)}$ Using Equation 19 $\displaystyle=\left(\left(\begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime})\land d _{\mathcal{T}}(v^{\prime})=l}\right)\sigma^{(T)}(f_{h}(v),f_{a}(v^{\prime}))&v \in{\mathbb{D}}\land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\widecheck{{\bm{U }}}^{(l+1)}+\widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\left(\begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime})\land d _{\mathcal{T}}(v^{\prime})=l}\right)\sigma^{(T)}(f_{h}(f_{Pa}(v^{\prime})),f_{ a}(v^{\prime}))&v\in{\mathbb{D}}\land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\widecheck{{\bm{U }}}^{(l+1)}$ $\displaystyle\qquad+\widecheck{{\bm{U}}}^{(l+1)}$ Using Equation 17 $\displaystyle=\left(\left(\begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime})\land d _{\mathcal{T}}(v^{\prime})=l}\right){\bm{s}}_{v^{\prime}}&v\in{\mathbb{D}} \land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\widecheck{{\bm{U }}}^{(l+1)}+\widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\left(\left(\begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime} )\land d_{\mathcal{T}}(v^{\prime})=l}\right)&v\in{\mathbb{D}}\land v^{\prime} \in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right){\bm{s}}_{v^{\prime}}\right)_{(v,v^{\prime})\in{\mathbb{V}}^ {2}}\right)\widecheck{{\bm{U}}}^{(l+1)}+\widecheck{{\bm{U}}}^{(l+1)}$ $\displaystyle=\left(\left(\left(\begin{cases}\left(\bm{1}_{v=f_{Pa}(v^{\prime} )\land d_{\mathcal{T}}(v^{\prime})=l}\right)&v\in{\mathbb{D}}\land v^{\prime} \in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\odot\left({\bm{s }}_{v^{\prime}}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\widecheck{{ \bm{U}}}^{(l+1)}+\widecheck{{\bm{U}}}^{(l+1)}$ Using Equation 10 and Equation 18 $\displaystyle=\left({\bm{L}}^{(l)}\odot{\bm{S}}\right)\widecheck{{\bm{U}}}^{(l +1)}+\widecheck{{\bm{U}}}^{(l+1)}$ $$

### D.4 “Excepted” Reach Probabilities

#### D.4.1 Initial Condition

An expanded form of Equation 25 is shown below.

$$ $\displaystyle\widecheck{{\bm{\Pi}}}^{(0)}$ $\displaystyle=\left.\left(\left(\begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+}) &d_{\mathcal{T}}(v)\leq l\\ 0&d_{\mathcal{T}}(v)>l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \right|_{l=0}$ $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal {T}}(v)\leq 0\\ 0&d_{\mathcal{T}}(v)>0\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&v=v_{0}\\ 0&v\in{\mathbb{V}}_{+}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ Using Equation 2 $\displaystyle=\left(\begin{cases}\begin{cases}\ldots&v\in{\mathbb{V}}_{+}\\ 1&v=v_{0}\\ \end{cases}&v=v_{0}\\ 0&v\in{\mathbb{V}}_{+}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\begin{cases}1&v=v_{0}\\ 0&v\in{\mathbb{V}}_{+}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\bm{1}_{v=v_{0}}\right)_{(v,i_{+})\in{\mathbb{V}}\times{ \mathbb{I}}_{+}}$ $$

#### D.4.2 Recurrence

An expanded form of Equation 26 is shown below.

$$ $\displaystyle\forall l\in[1,D]\cap{\mathbb{Z}}$ $\displaystyle\widecheck{{\bm{\Pi}}}^{(l)}$ $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal {T}}(v)\leq l\\ 0&d_{\mathcal{T}}(v)>l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal {T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\left( \begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T}}(v)\leq l-1\\ 0&d_{\mathcal{T}}(v)>l-1\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ Using Equation 24 $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal {T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\widecheck {{\bm{\Pi}}}^{(l-1)}$ Using Equation 2 $\displaystyle=\left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}( v),i_{+})\begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v)),f_{a}(v))&f_{i}(f_{h}(f_{ Pa}(v)))\neq i_{+}\\ 1&f_{i}(f_{h}(f_{Pa}(v)))=i_{+}\end{cases}&v\in{\mathbb{V}}_{+}\\ 1&v=v_{0}\\ \end{cases}&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\widecheck{{\bm{\Pi}}}^{(l-1)}$ Since $\displaystyle l\neq 0$ and therefore $\displaystyle v\neq v_{0}$ $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+}) \begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v)),f_{a}(v))&f_{i}(f_{h}(f_{Pa}(v))) \neq i_{+}\\ 1&f_{i}(f_{h}(f_{Pa}(v)))=i_{+}\end{cases}&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\widecheck {{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+ })&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)\left(\begin{cases}\begin{cases}\sigma^{(T)}(f_{h}(f_{Pa}(v) ),f_{a}(v))&f_{i}(f_{h}(f_{Pa}(v)))\neq i_{+}\\ 1&f_{i}(f_{h}(f_{Pa}(v)))=i_{+}\end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}} _{+}}$ $\displaystyle\qquad+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+})&d_{ \mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad\odot\left(\begin{cases}\begin{cases}\sigma^{(T)}(f_{h}(f_{ Pa}(v)),f_{a}(v))&f_{i}(f_{h}(f_{Pa}(v)))\neq i_{+}\\ 1&f_{i}(f_{h}(f_{Pa}(v)))=i_{+}\end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}+ \widecheck{{\bm{\Pi}}}^{(l-1)}$ Using Equation 17 and Equation 13 $\displaystyle=\left(\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+ })&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\left(\begin{cases}\begin{cases}{\bm{s}}_{v}&\left({\bm{M}}^{(V,I_{+})} \right)_{v,i_{+}}=0\\ 1&\left({\bm{M}}^{(V,I_{+})}\right)_{v,i_{+}}=1\end{cases}&v\in{\mathbb{V}}_{+ }\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\widecheck{{\bm{\Pi}}}^{(l-1)}$ Using Equation 17 $\displaystyle=\left(\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+ })&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\left(\begin{cases}\begin{cases}{\bm{s}}_{v}&\left({\bm{M}}^{(V,I_{+})} \right)_{v,i_{+}}=0\\ 1&\left({\bm{M}}^{(V,I_{+})}\right)_{v,i_{+}}=1\end{cases}&v\in{\mathbb{V}}_{+ }\\ {\bm{s}}_{v}&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}$ $\displaystyle\qquad+\widecheck{{\bm{\Pi}}}^{(l-1)}$ Using Equation 13 $\displaystyle=\left(\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+ })&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\left(\begin{cases}{\bm{s}}_{v}&\left({\bm{M}}^{(V,I_{+})}\right)_{v,i_{+ }}=0\\ 1&\left({\bm{M}}^{(V,I_{+})}\right)_{v,i_{+}}=1\end{cases}\right)_{(v,i_{+}) \in{\mathbb{V}}\times{\mathbb{I}}_{+}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ Using Equation 23 $\displaystyle=\left(\left(\begin{cases}\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+ })&d_{\mathcal{T}}(v)=l\\ 0&d_{\mathcal{T}}(v)\neq l\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\left(\begin{cases}\left(\bm{1}_{d_{\mathcal{T}}(v)=l} \right)\check{\pi}(\sigma^{(T)},f_{Pa}(v),i_{+})&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\left(\sum_{v^{\prime}\in{\mathbb{V}}}\begin{cases}\left( \bm{1}_{v^{\prime}=f_{Pa}(v)\land d_{\mathcal{T}}(v)=l}\right)\check{\pi}( \sigma^{(T)},v^{\prime},i_{+})&v^{\prime}\in{\mathbb{D}}\land v\in{\mathbb{V}} _{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\left(\sum_{v^{\prime}\in{\mathbb{V}}}\left(\begin{cases} \bm{1}_{v^{\prime}=f_{Pa}(v)\land d_{\mathcal{T}}(v)=l}&v^{\prime}\in{\mathbb{ D}}\land v\in{\mathbb{V}}_{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)\left(\begin{cases}\check{\pi}(\sigma^{(T)},v^{\prime},i_{+} )&d_{\mathcal{T}}(v^{\prime})\leq l-1\\ 0&d_{\mathcal{T}}(v^{\prime})>l-1\\ \end{cases}\right)\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}} \right)\odot\widecheck{{\bm{S}}}$ $\displaystyle\qquad+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{v^{\prime}=f_{Pa}(v)\land d _{\mathcal{T}}(v)=l}&v^{\prime}\in{\mathbb{D}}\land v\in{\mathbb{V}}_{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\left(\begin{ cases}\check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T}}(v)\leq l-1\\ 0&d_{\mathcal{T}}(v)>l-1\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\widecheck{{\bm{S}}}$ $\displaystyle\qquad+\widecheck{{\bm{\Pi}}}^{(l-1)}$ Using Equation 24 $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{v^{\prime}=f_{Pa}(v)\land d _{\mathcal{T}}(v)=l}&v^{\prime}\in{\mathbb{D}}\land v\in{\mathbb{V}}_{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\widecheck{{\bm{ \Pi}}}^{(l-1)}\right)\odot\widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{v=f_{Pa}(v^{\prime})\land d _{\mathcal{T}}(v^{\prime})=l}&v\in{\mathbb{D}}\land v^{\prime}\in{\mathbb{V}}_ {+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)^{\top}\widecheck {{\bm{\Pi}}}^{(l-1)}\right)\odot\widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{( l-1)}$ Using Equation 10 $\displaystyle=\left(\left({\bm{L}}^{(l)}\right)^{\top}\widecheck{{\bm{\Pi}}}^{ (l-1)}\right)\odot\widecheck{{\bm{S}}}+\widecheck{{\bm{\Pi}}}^{(l-1)}$ $$

### D.5 “Counterfactual” Reach Probability Terms

An expanded form of Equation 27 is shown below.

$$ $\displaystyle\widecheck{{\bm{\pi}}}$ $\displaystyle=\left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},v,f_{i} (f_{h}(f_{Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}$ $\displaystyle=\left(\begin{cases}\begin{cases}\sum_{i_{+}\in{\mathbb{I}}_{+}} \left(\bm{1}_{f_{i}(f_{h}(f_{Pa}(v)))=i_{+}}\right)\check{\pi}(\sigma^{(T)},v, i_{+})&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}$ $\displaystyle=\left(\begin{cases}\begin{cases}\left(\bm{1}_{f_{i}(f_{h}(f_{Pa} (v)))=i_{+}}\right)\check{\pi}(\sigma^{(T)},v,i_{+})&f_{h}(f_{Pa}(v))\in{ \mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\bm{1}_{|{ \mathbb{I}}_{+}|}$ $\displaystyle=\left(\begin{cases}\left(\bm{1}_{f_{i}(f_{h}(f_{Pa}(v)))=i_{+}} \right)\check{\pi}(\sigma^{(T)},v,i_{+})&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\bm{1}_{|{ \mathbb{I}}_{+}|}$ $\displaystyle=\left(\left(\begin{cases}\bm{1}_{f_{i}(f_{h}(f_{Pa}(v)))=i_{+}}& v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\check{\pi}(\sigma^{(T)},v,i_{+})\right)_{(v,i_{+})\in{ \mathbb{V}}\times{\mathbb{I}}_{+}}\bm{1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{f_{i}(f_{h}(f_{Pa}(v)))=i _{+}}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \odot\left(\check{\pi}(\sigma^{(T)},v,i_{+})\right)_{(v,i_{+})\in{\mathbb{V}} \times{\mathbb{I}}_{+}}\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ Using Equation 13 $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\check{\pi}( \sigma^{(T)},v,i_{+})\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}} \right)\bm{1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\begin{cases} \check{\pi}(\sigma^{(T)},v,i_{+})&d_{\mathcal{T}}(v)\leq D\\ 0&d_{\mathcal{T}}(v)>D\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)\bm{ 1}_{|{\mathbb{I}}_{+}|}$ Using Equation 24 $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\widecheck{{\bm{\Pi} }}^{(D)}\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ $$

### D.6 “Counterfactual” Reach Probabilities

An expanded form of Equation 28 is shown below.

$$ $\displaystyle\widetilde{{\bm{\pi}}}$ $\displaystyle=\left(\tilde{\pi}(\sigma^{(T)},h_{+})\right)_{h_{+}\in{\mathbb{H }}_{+}}$ Using Equation 3 $\displaystyle=\left(\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{ (T)},d,f_{i}(h_{+}))\right)_{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle=\left(\frac{|A(h_{+})|}{|A(h_{+})|}\sum_{d\in{\mathbb{D}}:f_{h}( d)=h_{+}}\check{\pi}(\sigma^{(T)},d,f_{i}(h_{+}))\right)_{h_{+}\in{\mathbb{H}} _{+}}$ $\displaystyle=\left(\left(\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}|A(h_{+})| \check{\pi}(\sigma^{(T)},d,f_{i}(h_{+}))\right)_{h_{+}\in{\mathbb{H}}_{+}} \right)\oslash\left(|A(h_{+})|\right)_{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle=\left(\sum_{v\in{\mathbb{V}}}\begin{cases}\left(\bm{1}_{h_{+}=f_ {h}(f_{Pa}(v))}\right)\check{\pi}(\sigma^{(T)},f_{Pa}(v),f_{i}(f_{h}(f_{Pa}(v) )))&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle\qquad\oslash\left(\sum_{(h_{+}^{\prime},a)\in{\mathbb{Q}}_{+}} \bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{h_{+}\in{\mathbb{H}}_{+}}$ Using Equation 2 $\displaystyle=\left(\sum_{v\in{\mathbb{V}}}\begin{cases}\left(\bm{1}_{h_{+}=f_ {h}(f_{Pa}(v))}\right)\check{\pi}(\sigma^{(T)},v,f_{i}(f_{h}(f_{Pa}(v))))&v\in {\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle\qquad\oslash\left(\sum_{(h_{+}^{\prime},a)\in{\mathbb{Q}}_{+}} \bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle=\left(\left(\begin{cases}\bm{1}_{h_{+}=f_{h}(f_{Pa}(v))}&v\in{ \mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}\vphantom{ \left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},v,f_{i}(f_{h}(f_{Pa}( v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}}\right.$ $\displaystyle\qquad\left.\vphantom{\left(\begin{cases}\bm{1}_{h_{+}=f_{h}(f_{ Pa}(v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}}\left( \begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},v,f_{i}(f_{h}(f_{Pa}(v))))& f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}\right)$ $\displaystyle\qquad\qquad\oslash\left(\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime} }\right)_{(h_{+},(h_{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q}}_{+}} \right)\bm{1}_{|{\mathbb{Q}}_{+}|}\right)$ Using Equation 12 $\displaystyle=\left(\left(\begin{cases}\bm{1}_{h_{+}=f_{h}(f_{Pa}(v))}&v\in{ \mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}\vphantom{ \left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},v,f_{i}(f_{h}(f_{Pa}( v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}}\right.$ $\displaystyle\qquad\left.\vphantom{\left(\begin{cases}\bm{1}_{h_{+}=f_{h}(f_{ Pa}(v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}}\left( \begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},v,f_{i}(f_{h}(f_{Pa}(v))))& f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}\right)$ $\displaystyle\qquad\qquad\oslash\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\bm {1}_{|{\mathbb{Q}}_{+}|}\right)$ Using Equation 27 $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{h_{+}=f_{h}(f_{Pa}(v))}&v \in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}\right) \widecheck{{\bm{\pi}}}\right)\oslash\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right )\bm{1}_{|{\mathbb{Q}}_{+}|}\right)$ $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{(h_{+},f_{a}(v))=(f_{h}(f _{Pa}(v)),f_{a}(v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}\right) \widecheck{{\bm{\pi}}}\right)\oslash\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right )\bm{1}_{|{\mathbb{Q}}_{+}|}\right)$ $\displaystyle=\left(\left(\left(\sum_{(h_{+}^{\prime},a)\in{\mathbb{Q}}_{+}} \bm{1}_{h_{+}=h_{+}^{\prime}}\begin{cases}\bm{1}_{(h_{+}^{\prime},a)=(f_{h}(f_ {Pa}(v)),f_{a}(v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(h_{+},v)\in{\mathbb{H}}_{+}\times{\mathbb{V}}}\right) \widecheck{{\bm{\pi}}}\right)$ $\displaystyle\qquad\oslash\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\bm{1}_{| {\mathbb{Q}}_{+}|}\right)$ $\displaystyle=\left(\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{(h_{+},( h_{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q}}_{+}}\right)\left(\left (\begin{cases}\bm{1}_{q_{+}=(f_{h}(f_{Pa}(v)),f_{a}(v))}&v\in{\mathbb{V}}_{+} \\ 0&v=v_{0}\end{cases}\right)_{(q_{+},v)\in{\mathbb{Q}}_{+}\times{\mathbb{V}}} \right)\widecheck{{\bm{\pi}}}\right)$ $\displaystyle\qquad\oslash\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\bm{1}_{| {\mathbb{Q}}_{+}|}\right)$ Using Equation 12 and Equation 11 $\displaystyle=\left(\left({\bm{M}}^{(H_{+},Q_{+})}\right)\left({\bm{M}}^{(Q_{+ },V)}\right)\widecheck{{\bm{\pi}}}\right)\oslash\left(\left({\bm{M}}^{(H_{+},Q _{+})}\right)\bm{1}_{|{\mathbb{Q}}_{+}|}\right)$ $$

### D.7 Counterfactual Reach Probability Sums

An expanded form of Equation 29 is shown below.

$$ $\displaystyle\widetilde{{\bm{\pi}}}^{(\Sigma)}$ $\displaystyle=\left(\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})\right) _{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle=\left(\left(\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+} )\right)+\tilde{\pi}(\sigma^{(T)},h_{+})\right)_{h_{+}\in{\mathbb{H}}_{+}}$ $\displaystyle=\left(\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+}) \right)_{h_{+}\in{\mathbb{H}}_{+}}+\left(\tilde{\pi}(\sigma^{(T)},h_{+})\right )_{h_{+}\in{\mathbb{H}}_{+}}$ Using Equation 29 and Equation 28 $\displaystyle=\widetilde{{\bm{\pi}}}^{(\Sigma)\prime}+\widetilde{{\bm{\pi}}}$ $$

### D.8 Average Strategy Profile

An expanded form of Equation 30 is shown below.

$$ $\displaystyle\widebar{{\bm{\sigma}}}$ $\displaystyle=\left(\bar{\sigma}^{(T)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ Using Equation 8 $\displaystyle=\left(\frac{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+}) \sigma^{(\tau)}(h_{+},a)}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})} \right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\frac{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+} )\sigma^{(\tau)}(h_{+},a)}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+}) }+\frac{\tilde{\pi}(\sigma^{(T)},h_{+})\sigma^{(T)}(h_{+},a)}{\sum_{\tau=1}^{T }\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\left(\frac{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)} ,h_{+})}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)\left( \frac{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+})\sigma^{(\tau)}(h_{ +},a)}{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)+\vphantom {\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau=1}^{T}\tilde{\pi}( \sigma^{(\tau)},h_{+})}\right)\sigma^{(T)}(h_{+},a)}\right.$ $\displaystyle\qquad\left.\vphantom{\left(\frac{\sum_{\tau=1}^{T-1}\tilde{\pi}( \sigma^{(\tau)},h_{+})}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})} \right)\left(\frac{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+})\sigma ^{(\tau)}(h_{+},a)}{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)},h_{+})} \right)}+\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau=1}^{T}\tilde{ \pi}(\sigma^{(\tau)},h_{+})}\right)\sigma^{(T)}(h_{+},a)\right)_{(h_{+},a)\in{ \mathbb{Q}}_{+}}$ Using Equation 8 $\displaystyle=\left(\left(\frac{\sum_{\tau=1}^{T-1}\tilde{\pi}(\sigma^{(\tau)} ,h_{+})}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)\bar{ \sigma}^{(T-1)}(h_{+},a)+\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{ \tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)\sigma^{(T)}(h_{+},a) \right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\left(1-\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau= 1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)\bar{\sigma}^{(T-1)}(h_{+},a)+ \vphantom{\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau=1}^{T}\tilde {\pi}(\sigma^{(\tau)},h_{+})}\right)\sigma^{(T)}(h_{+},a)}\right.$ $\displaystyle\qquad\left.\vphantom{\left(1-\frac{\tilde{\pi}(\sigma^{(T)},h_{+ })}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)\bar{\sigma}^{( T-1)}(h_{+},a)}+\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau=1}^{T} \tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)\sigma^{(T)}(h_{+},a)\right)_{(h_{+} ,a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\bar{\sigma}^{(T-1)}(h_{+},a)+\left(\frac{\tilde{\pi}( \sigma^{(T)},h_{+})}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})} \right)\left(\sigma^{(T)}(h_{+},a)-\bar{\sigma}^{(T-1)}(h_{+},a)\right)\right) _{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\bar{\sigma}^{(T-1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{ +}}$ $\displaystyle\qquad+\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau=1} ^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle\qquad\qquad\odot\left(\left(\left(\sigma^{(T)}(q_{+})\right)_{q_ {+}\in{\mathbb{Q}}_{+}}\right)-\left(\bar{\sigma}^{(T-1)}(q_{+})\right)_{q_{+} \in{\mathbb{Q}}_{+}}\right)$ Using Equation 30 and Equation 15 $\displaystyle=\widebar{{\bm{\sigma}}}^{\prime}+\left(\left(\frac{\tilde{\pi}( \sigma^{(T)},h_{+})}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})} \right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}\right)\odot\left({\bm{\sigma}}-\widebar {{\bm{\sigma}}}^{\prime}\right)$ $\displaystyle=\widebar{{\bm{\sigma}}}^{\prime}+\left(\left(\sum_{h_{+}^{\prime }\in{\mathbb{H}}_{+}}\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)\frac{\tilde{ \pi}(\sigma^{(T)},h_{+}^{\prime})}{\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{(\tau) },h_{+}^{\prime})}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}\right)\odot\left({\bm {\sigma}}-\widebar{{\bm{\sigma}}}^{\prime}\right)$ $\displaystyle=\widebar{{\bm{\sigma}}}^{\prime}+\left(\left(\left(\bm{1}_{h_{+} =h_{+}^{\prime}}\right)_{((h_{+},a),h_{+}^{\prime})\in{\mathbb{Q}}_{+}\times{ \mathbb{H}}_{+}}\right)\left(\frac{\tilde{\pi}(\sigma^{(T)},h_{+})}{\sum_{\tau =1}^{T}\tilde{\pi}(\sigma^{(\tau)},h_{+})}\right)_{h_{+}\in{\mathbb{H}}_{+}} \right)\odot\left({\bm{\sigma}}-\widebar{{\bm{\sigma}}}^{\prime}\right)$ $\displaystyle=\widebar{{\bm{\sigma}}}^{\prime}$ $\displaystyle\qquad+\left(\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{(h _{+},(h_{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q}}_{+}}\right)^{ \top}\vphantom{\left(\left(\left(\tilde{\pi}(\sigma^{(T)},h_{+})\right)_{h_{+} \in{\mathbb{H}}_{+}}\right)\oslash\left(\sum_{\tau=1}^{T}\tilde{\pi}(\sigma^{( \tau)},h_{+})\right)_{h_{+}\in{\mathbb{H}}_{+}}\right)}\right.$ $\displaystyle\qquad\qquad\left.\vphantom{\left(\left(\bm{1}_{h_{+}=h_{+}^{ \prime}}\right)_{(h_{+},(h_{+}^{\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q }}_{+}}\right)^{\top}}\left(\left(\left(\tilde{\pi}(\sigma^{(T)},h_{+})\right) _{h_{+}\in{\mathbb{H}}_{+}}\right)\oslash\left(\sum_{\tau=1}^{T}\tilde{\pi}( \sigma^{(\tau)},h_{+})\right)_{h_{+}\in{\mathbb{H}}_{+}}\right)\right)\odot \left({\bm{\sigma}}-\widebar{{\bm{\sigma}}}^{\prime}\right)$ Using Equation 12 , Equation 28 , and Equation 29 $\displaystyle=\widebar{{\bm{\sigma}}}^{\prime}+\left(\left({\bm{M}}^{(H_{+},Q_ {+})}\right)^{\top}\left(\widetilde{{\bm{\pi}}}\oslash\widetilde{{\bm{\pi}}}^{ (\Sigma)}\right)\right)\odot\left({\bm{\sigma}}-\widebar{{\bm{\sigma}}}^{ \prime}\right)$ $$

### D.9 Instantaneous Counterfactual Regrets

An expanded form of Equation 31 is shown below.

First, define a dense vector $\displaystyle{\bm{\rho}}\in\mathbb{R}^{\mathbb{V}}$ for intermediate values.

$$ $\begin{split}{\bm{\rho}}&=\left(\begin{cases}\begin{cases}\check{u}(\sigma^{(T )},v,f_{i}(f_{h}(f_{Pa}(v))))-\check{u}(\sigma^{(T)},f_{Pa}(v),f_{i}(f_{h}(f_{ Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}\\ &=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{\bm{U}}}-{\bm{ G}}^{\top}\widecheck{{\bm{U}}}\right)\right)\bm{1}_{|{\mathbb{I}}_{+}|}\\ \end{split}$ (35) $$

Then,

$$ $\displaystyle\widetilde{{\bm{r}}}$ $\displaystyle=\left(\tilde{r}(\sigma^{(T)},q_{+})\right)_{q_{+}\in{\mathbb{Q}} _{+}}$ Using Equation 5 $\displaystyle=\left(\tilde{\pi}(\sigma^{(T)},h_{+})(\tilde{u}(\sigma^{(T)}|_{h _{+}\rightarrow a},h_{+})-\tilde{u}(\sigma^{(T)},h_{+}))\right)_{(h_{+},a)\in{ \mathbb{Q}}_{+}}$ Using Equation 4 $\displaystyle=\left(\tilde{\pi}(\sigma^{(T)},h_{+})\vphantom{\left(\frac{\sum_ {d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{(T)}|_{h_{+}\rightarrow a },d,f_{i}(h_{+}))\check{u}(\sigma^{(T)}|_{h_{+}\rightarrow a},d,f_{i}(h_{+}))} {\tilde{\pi}(\sigma^{(T)}|_{h_{+}\rightarrow a},h_{+})}-\frac{\sum_{d\in{ \mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{(T)},d,f_{i}(h_{+}))\check{u}( \sigma^{(T)},d,f_{i}(h_{+}))}{\tilde{\pi}(\sigma^{(T)},h_{+})}\right)}\right.$ $\displaystyle\qquad\left(\frac{\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{ \pi}(\sigma^{(T)}|_{h_{+}\rightarrow a},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)}| _{h_{+}\rightarrow a},d,f_{i}(h_{+}))}{\tilde{\pi}(\sigma^{(T)}|_{h_{+} \rightarrow a},h_{+})}\right.$ $\displaystyle\qquad\qquad\left.\left.-\frac{\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_ {+}}\check{\pi}(\sigma^{(T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)},d,f_{i}(h_{ +}))}{\tilde{\pi}(\sigma^{(T)},h_{+})}\right)\right)_{(h_{+},a)\in{\mathbb{Q}} _{+}}$ $\displaystyle=\left(\tilde{\pi}(\sigma^{(T)},h_{+})\vphantom{\left(\frac{\sum_ {d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{(T)},d,f_{i}(h_{+})) \check{u}(\sigma^{(T)}|_{h_{+}\rightarrow a},d,f_{i}(h_{+}))}{\tilde{\pi}( \sigma^{(T)},h_{+})}-\frac{\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}( \sigma^{(T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)},d,f_{i}(h_{+}))}{\tilde{\pi }(\sigma^{(T)},h_{+})}\right)}\right.$ $\displaystyle\qquad\left(\frac{\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{ \pi}(\sigma^{(T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)}|_{h_{+}\rightarrow a}, d,f_{i}(h_{+}))}{\tilde{\pi}(\sigma^{(T)},h_{+})}\right.$ $\displaystyle\qquad\qquad\left.\left.-\frac{\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_ {+}}\check{\pi}(\sigma^{(T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)},d,f_{i}(h_{ +}))}{\tilde{\pi}(\sigma^{(T)},h_{+})}\right)\right)_{(h_{+},a)\in{\mathbb{Q}} _{+}}$ $\displaystyle=\left(\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{ (T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)}|_{h_{+}\rightarrow a},d,f_{i}(h_{+} ))\vphantom{-\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{(T)},d, f_{i}(h_{+}))\check{u}(\sigma^{(T)},d,f_{i}(h_{+}))}\right.$ $\displaystyle\qquad\left.\vphantom{\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}} \check{\pi}(\sigma^{(T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)}|_{h_{+} \rightarrow a},d,f_{i}(h_{+}))}-\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{ \pi}(\sigma^{(T)},d,f_{i}(h_{+}))\check{u}(\sigma^{(T)},d,f_{i}(h_{+}))\right) _{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\sum_{d\in{\mathbb{D}}:f_{h}(d)=h_{+}}\check{\pi}(\sigma^{ (T)},d,f_{i}(h_{+}))\left(\check{u}(\sigma^{(T)}|_{h_{+}\rightarrow a},d,f_{i} (h_{+}))-\check{u}(\sigma^{(T)},d,f_{i}(h_{+}))\right)\right)_{(h_{+},a)\in{ \mathbb{Q}}_{+}}$ $\displaystyle=\left(\sum_{v\in{\mathbb{V}}}\left(\begin{cases}\bm{1}_{q_{+}=(f _{h}(f_{Pa}(v)),f_{a}(v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\vphantom{\begin{cases}\begin{cases}\\ \\ \end{cases}\\ \\ \end{cases}}\right.$ $\displaystyle\qquad\left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},f_ {Pa}(v),f_{i}(f_{h}(f_{Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)$ $\displaystyle\qquad\left.\left(\begin{cases}\begin{cases}\left(\begin{ multlined}\check{u}(\sigma^{(T)}|_{f_{h}(f_{Pa}(v))\rightarrow a},f_{Pa}(v),f_ {i}(f_{h}(f_{Pa}(v))))\\ -\check{u}(\sigma^{(T)},f_{Pa}(v),f_{i}(f_{h}(f_{Pa}(v))))\end{multlined} \check{u}(\sigma^{(T)}|_{f_{h}(f_{Pa}(v))\rightarrow a},f_{Pa}(v),f_{i}(f_{h}( f_{Pa}(v))))\\ -\check{u}(\sigma^{(T)},f_{Pa}(v),f_{i}(f_{h}(f_{Pa}(v))))\right)&f_{h}(f_{Pa} (v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\sum_{v\in{\mathbb{V}}}\left(\begin{cases}\bm{1}_{q_{+}=(f _{h}(f_{Pa}(v)),f_{a}(v))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\vphantom{\begin{cases}\begin{cases}\\ \\ \end{cases}\\ \\ \end{cases}}\right.$ $\displaystyle\qquad\left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{(T)},v, f_{i}(f_{h}(f_{Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)$ $\displaystyle\qquad\left.\left(\begin{cases}\begin{cases}\check{u}(\sigma^{(T) },v,f_{i}(f_{h}(f_{Pa}(v))))-\check{u}(\sigma^{(T)},f_{Pa}(v),f_{i}(f_{h}(f_{ Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\begin{cases}\bm{1}_{q_{+}=(f_{h}(f_{Pa}(v)),f_{a}(v))}&v \in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(q_{+},v)\in{\mathbb{Q}}_{+}\times{\mathbb{V}}}$ $\displaystyle\qquad\left(\left(\begin{cases}\begin{cases}\check{\pi}(\sigma^{( T)},v,f_{i}(f_{h}(f_{Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}\right.$ $\displaystyle\qquad\qquad\left.\odot\left(\begin{cases}\begin{cases}\check{u}( \sigma^{(T)},v,f_{i}(f_{h}(f_{Pa}(v))))-\check{u}(\sigma^{(T)},f_{Pa}(v),f_{i} (f_{h}(f_{Pa}(v))))&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}\right)$ Using Equation 11 , Equation 27 , and Equation 35 $\displaystyle=\left({\bm{M}}^{(Q_{+},V)}\right)\left(\widecheck{{\bm{\pi}}} \odot{\bm{\rho}}\right)$ Using Equation 35 $\displaystyle=\left({\bm{M}}^{(Q_{+},V)}\right)\left(\widecheck{{\bm{\pi}}} \odot\left(\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{\bm{U }}}-{\bm{G}}^{\top}\widecheck{{\bm{U}}}\right)\right)\bm{1}_{|{\mathbb{I}}_{+} |}\right)\right)$ $$

#### D.9.1 Intermediate Values

An expanded form of Equation 35 is shown below.

$$ $\displaystyle{\bm{\rho}}$ $\displaystyle=\left(\begin{cases}\begin{cases}\check{u}(\sigma^{(T)},v,f_{i}(f _{h}(f_{Pa}(v))))-\check{u}(\sigma^{(T)},f_{Pa}(v),f_{i}(f_{h}(f_{Pa}(v))))&f_ {h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}$ $\displaystyle=\left(\left(\sum_{i_{+}\in{\mathbb{I}}_{+}}\begin{cases}\left( \bm{1}_{i_{+}=f_{i}(f_{h}(f_{Pa}(v)))}\right)\begin{cases}\check{u}(\sigma^{(T )},v,i_{+})-\check{u}(\sigma^{(T)},f_{Pa}(v),i_{+})&f_{h}(f_{Pa}(v))\in{ \mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{v\in{\mathbb{V}}}\right)$ $\displaystyle=\left(\left(\begin{cases}\left(\bm{1}_{i_{+}=f_{i}(f_{h}(f_{Pa}( v)))}\right)\begin{cases}\check{u}(\sigma^{(T)},v,i_{+})-\check{u}(\sigma^{(T) },f_{Pa}(v),i_{+})&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{+}\\ 0&f_{h}(f_{Pa}(v))\in{\mathbb{H}}_{0}\\ \end{cases}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)\bm{ 1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left(\begin{cases}\left(\bm{1}_{i_{+}=f_{i}(f_{h}(f_{Pa}( v)))}\right)\left(\check{u}(\sigma^{(T)},v,i_{+})-\check{u}(\sigma^{(T)},f_{Pa }(v),i_{+})\right)&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)\bm{ 1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left(\left(\begin{cases}\bm{1}_{i_{+}=f_{i}(f_{h}(f_{Pa}( v)))}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\left(\check{u}(\sigma^{(T)},v,i_{+})-\begin{cases}\check{u} (\sigma^{(T)},f_{Pa}(v),i_{+})&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}} \right)\bm{1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left(\begin{cases}\bm{1}_{f_{i}(f_{h}(f_{Pa}(v)))=i_{+}}& v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\vphantom{ \odot\left(\check{u}(\sigma^{(T)},v,i_{+})-\begin{cases}\check{u}(\sigma^{(T)} ,f_{Pa}(v),i_{+})&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}}\right.$ $\displaystyle\qquad\left.\vphantom{\left(\left(\begin{cases}\bm{1}_{f_{i}(f_{h }(f_{Pa}(v)))=i_{+}}&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)} \odot\left(\check{u}(\sigma^{(T)},v,i_{+})-\begin{cases}\check{u}(\sigma^{(T)} ,f_{Pa}(v),i_{+})&v\in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)\bm{ 1}_{|{\mathbb{I}}_{+}|}$ Using Equation 13 $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\check{u}( \sigma^{(T)},v,i_{+})-\begin{cases}\check{u}(\sigma^{(T)},f_{Pa}(v),i_{+})&v \in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)\bm{ 1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\left(\left( \check{u}(\sigma^{(T)},v,i_{+})\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb {I}}_{+}}\right)-\left(\begin{cases}\check{u}(\sigma^{(T)},f_{Pa}(v),i_{+})&v \in{\mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \right)\bm{1}_{|{\mathbb{I}}_{+}|}$ Using Equation 22 $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{ \bm{U}}}-\left(\begin{cases}\check{u}(\sigma^{(T)},f_{Pa}(v),i_{+})&v\in{ \mathbb{V}}_{+}\\ 0&v=v_{0}\\ \end{cases}\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right) \right)\bm{1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{ \bm{U}}}-\left(\sum_{v^{\prime}\in{\mathbb{V}}}\left(\begin{cases}\bm{1}_{v^{ \prime}=f_{Pa}(v)}&v^{\prime}\in{\mathbb{D}}\land v\in{\mathbb{V}}_{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)\check{u}(\sigma^{(T)},v^{\prime},i_{+})\right)_{(v,i_{+}) \in{\mathbb{V}}\times{\mathbb{I}}_{+}}\right)\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{ \bm{U}}}-\left(\left(\begin{cases}\bm{1}_{v^{\prime}=f_{Pa}(v)}&v^{\prime}\in{ \mathbb{D}}\land v\in{\mathbb{V}}_{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\left(\check{u}( \sigma^{(T)},v,i_{+})\right)_{(v,i_{+})\in{\mathbb{V}}\times{\mathbb{I}}_{+}} \right)\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ Using Equation 22 $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{ \bm{U}}}-\left(\left(\begin{cases}\bm{1}_{v^{\prime}=f_{Pa}(v)}&v^{\prime}\in{ \mathbb{D}}\land v\in{\mathbb{V}}_{+}\\ 0&v^{\prime}\in{\mathbb{T}}\lor v=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)\widecheck{{\bm{U }}}\right)\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{ \bm{U}}}-\left(\left(\begin{cases}\bm{1}_{v=f_{Pa}(v^{\prime})}&v\in{\mathbb{D }}\land v^{\prime}\in{\mathbb{V}}_{+}\\ 0&v\in{\mathbb{T}}\lor v^{\prime}=v_{0}\\ \end{cases}\right)_{(v,v^{\prime})\in{\mathbb{V}}^{2}}\right)^{\top}\widecheck {{\bm{U}}}\right)\right)\bm{1}_{|{\mathbb{I}}_{+}|}$ Using Equation 9 $\displaystyle=\left(\left({\bm{M}}^{(V,I_{+})}\right)\odot\left(\widecheck{{ \bm{U}}}-{\bm{G}}^{\top}\widecheck{{\bm{U}}}\right)\right)\bm{1}_{|{\mathbb{I} }_{+}|}$ $$

### D.10 Average Counterfactual Regrets

An expanded form of Equation 32 is shown below.

$$ $\displaystyle\widebar{{\bm{r}}}$ $\displaystyle=\left(\bar{r}^{(T)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ Using Equation 6 $\displaystyle=\left(\frac{1}{T}\sum_{\tau=1}^{T}\tilde{r}(\sigma^{(\tau)},q_{+ })\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\frac{1}{T}\left(\left(\sum_{\tau=1}^{T-1}\tilde{r}(\sigma ^{(\tau)},q_{+})\right)+\tilde{r}(\sigma^{(T)},q_{+})\right)\right)_{q_{+}\in{ \mathbb{Q}}_{+}}$ $\displaystyle=\left(\left(\frac{1}{T}\sum_{\tau=1}^{T-1}\tilde{r}(\sigma^{( \tau)},q_{+})\right)+\left(\frac{1}{T}\right)\tilde{r}(\sigma^{(T)},q_{+}) \right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\left(\frac{(T-1)}{T}\right)\left(\frac{1}{(T-1)}\sum_{ \tau=1}^{T-1}\tilde{r}(\sigma^{(\tau)},q_{+})\right)+\left(\frac{1}{T}\right) \tilde{r}(\sigma^{(T)},q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ Using Equation 6 $\displaystyle=\left(\left(\frac{(T-1)}{T}\right)\bar{r}^{(T-1)}(q_{+})+\left( \frac{1}{T}\right)\tilde{r}(\sigma^{(T)},q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{ +}}$ $\displaystyle=\left(\left(1-\frac{1}{T}\right)\bar{r}^{(T-1)}(q_{+})+\left( \frac{1}{T}\right)\tilde{r}(\sigma^{(T)},q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{ +}}$ $\displaystyle=\left(\bar{r}^{(T-1)}(q_{+})+\frac{1}{T}\left(\tilde{r}(\sigma^{ (T)},q_{+})-\bar{r}^{(T-1)}(q_{+})\right)\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\bar{r}^{(T-1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}+ \frac{1}{T}\left(\left(\tilde{r}(\sigma^{(T)},q_{+})\right)_{q_{+}\in{\mathbb{ Q}}_{+}}-\left(\bar{r}^{(T-1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}\right)$ Using Equation 32 and Equation 31 $\displaystyle=\widebar{{\bm{r}}}^{\prime}+\frac{1}{T}\left(\widetilde{{\bm{r}} }-\widebar{{\bm{r}}}^{\prime}\right)$ $$

### D.11 Regret Normalizers

An expanded form of Equation 33 is shown below.

$$ $\displaystyle\widebar{{\bm{r}}}^{(+,\Sigma)}$ $\displaystyle=\left(\sum_{a^{\prime}\in A(h_{+})}\left(\bar{r}^{(T)}(h_{+},a^{ \prime})\right)^{+}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\sum_{(h_{+}^{\prime},a^{\prime})\in{\mathbb{Q}}_{+}}\left (\bm{1}_{h_{+}=h_{+}^{\prime}}\right)\left(\bar{r}^{(T)}(h_{+}^{\prime},a^{ \prime})\right)^{+}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{((h_{+},a),(h_ {+}^{\prime},a^{\prime}))\in{\mathbb{Q}}_{+}^{2}}\right)\left(\left(\bar{r}^{( T)}(q_{+})\right)^{+}\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\left(\sum_{h_{+}^{\prime\prime}\in{\mathbb{H}}_{+}}\left( \bm{1}_{h_{+}=h_{+}^{\prime\prime}}\right)\left(\bm{1}_{h_{+}^{\prime}=h_{+}^{ \prime\prime}}\right)\right)_{((h_{+},a),(h_{+}^{\prime},a^{\prime}))\in{ \mathbb{Q}}_{+}^{2}}\right)\left(\left(\bar{r}^{(T)}(q_{+})\right)_{q_{+}\in{ \mathbb{Q}}_{+}}\right)^{+}$ Using Equation 32 $\displaystyle=\left(\left(\sum_{h_{+}^{\prime\prime}\in{\mathbb{H}}_{+}}\left( \bm{1}_{h_{+}=h_{+}^{\prime\prime}}\right)\left(\bm{1}_{h_{+}^{\prime}=h_{+}^{ \prime\prime}}\right)\right)_{((h_{+},a),(h_{+}^{\prime},a^{\prime}))\in{ \mathbb{Q}}_{+}^{2}}\right)\widebar{{\bm{r}}}^{+}$ $\displaystyle=\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{((h_{+},a),h_{ +}^{\prime}))\in{\mathbb{Q}}_{+}\times{\mathbb{H}}_{+}}\right)\left(\left(\bm{ 1}_{h_{+}=h_{+}^{\prime}}\right)_{(h_{+},(h_{+}^{\prime},a))\in{\mathbb{H}}_{+ }\times{\mathbb{Q}}_{+}}\right)\widebar{{\bm{r}}}^{+}$ $\displaystyle=\left(\left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{(h_{+},(h_{+}^ {\prime},a))\in{\mathbb{H}}_{+}\times{\mathbb{Q}}_{+}}\right)^{\top}\left( \left(\bm{1}_{h_{+}=h_{+}^{\prime}}\right)_{(h_{+},(h_{+}^{\prime},a))\in{ \mathbb{H}}_{+}\times{\mathbb{Q}}_{+}}\right)\widebar{{\bm{r}}}^{+}$ Using Equation 12 $\displaystyle=\left({\bm{M}}^{(H_{+},Q_{+})}\right)^{\top}\left({\bm{M}}^{(H_{ +},Q_{+})}\right)\widebar{{\bm{r}}}^{+}$ To take advantage of the sparsity of $\displaystyle{\bm{M}}^{(H_{+},Q_{+})}$ (see Table 1 ) $\displaystyle=\left({\bm{M}}^{(H_{+},Q_{+})}\right)^{\top}\left(\left({\bm{M}} ^{(H_{+},Q_{+})}\right)\widebar{{\bm{r}}}^{+}\right)$ $$

### D.12 Next Strategy Profile

An expanded form of Equation 34 is shown below.

$$ $\displaystyle{\bm{\sigma}}^{\prime}$ $\displaystyle=\left(\sigma^{(T+1)}(q_{+})\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ Using Equation 7 $\displaystyle=\left(\begin{cases}\begin{cases}\frac{(\bar{r}^{(T)}(h_{+},a))^{ +}}{\sum_{a^{\prime}\in A(h_{+})}(\bar{r}^{(T)}(h_{+},a^{\prime}))^{+}}&\sum_{ a^{\prime}\in A(h_{+})}(\bar{r}^{(T)}(h_{+},a^{\prime}))^{+}>0\\ \frac{1}{|A(h_{+})|}&\sum_{a^{\prime}\in A(h_{+})}(\bar{r}^{(T)}(h_{+},a^{ \prime}))^{+}=0\end{cases}&(h_{+},a)\in{\mathbb{Q}}_{+}\\ \sigma_{0}(h_{+},a)&(h_{+},a)\in{\mathbb{Q}}_{0}\\ \end{cases}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ $\displaystyle=\left(\begin{cases}\frac{(\bar{r}^{(T)}(h_{+},a))^{+}}{\sum_{a^{ \prime}\in A(h_{+})}(\bar{r}^{(T)}(h_{+},a^{\prime}))^{+}}&\sum_{a^{\prime}\in A (h_{+})}(\bar{r}^{(T)}(h_{+},a^{\prime}))^{+}>0\\ \frac{1}{|A(h_{+})|}&\sum_{a^{\prime}\in A(h_{+})}(\bar{r}^{(T)}(h_{+},a^{ \prime}))^{+}=0\end{cases}\right)_{(h_{+},a)\in{\mathbb{Q}}_{+}}$ Using Equation 32 , Equation 33 , and Equation 16 $\displaystyle=\left(\begin{cases}\left(\widebar{{\bm{r}}}^{+}\oslash\widebar{{ \bm{r}}}^{(+,\Sigma)}\right)_{q_{+}}&\left(\widebar{{\bm{r}}}^{(+,\Sigma)} \right)_{q_{+}}>0\\ \left({\bm{\sigma}}^{(T=1)}\right)_{q_{+}}&\left(\widebar{{\bm{r}}}^{(+,\Sigma )}\right)_{q_{+}}=0\\ \end{cases}\right)_{q_{+}\in{\mathbb{Q}}_{+}}$ $$

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: N/A
soundness: 3
strengths: Originality: The paper introduces a creative approach by reformulating Counterfactual Regret Minimization (CFR) as matrix operations suitable for GPU processing. This novel restructuring allows a highly parallelizable version of CFR, which has not been extensively explored in existing CFR literature.

Efficiency in Design: By avoiding recursive tree traversal, the implementation achieves substantial speed gains, especially in larger games, demonstrating an efficient design choice that effectively leverages GPU hardware.

Thorough Empirical Evaluation: The paper evaluates the new approach on a diverse set of games with varying complexity and size, rigorously benchmarking it against established OpenSpiel baselines in both Python and C++. This experimental breadth strengthens the validity of its claims about speedup and scalability.

Significant Potential for Scalability: The approach is well-suited for large-scale games, with experiments showing up to 352.5 times faster performance than OpenSpiel’s Python baseline and 22.2 times faster than its C++ counterpart, especially promising for future work on supercomputing platforms or even more extensive imperfect information games.
summary: The paper presents a GPU-accelerated approach for Counterfactual Regret Minimization (CFR), a class of no-regret learning algorithms widely used in solving large-scale imperfect information games like poker. Traditionally, CFR algorithms rely on recursive tree traversal, which limits their efficiency. This work proposes a restructured CFR algorithm that converts the operations into a series of dense and sparse matrix and vector computations, making it highly parallelizable on GPUs at the cost of increased memory usage.

The study concludes that the proposed approach could serve as a foundational step for highly scalable CFR on supercomputing infrastructures, enabling faster solutions to complex game-theoretic problems.
weaknesses: Originality Limitations: Although innovative, the paper applies GPU parallelization to the vanilla CFR algorithm, which is somewhat limited in novelty given the existence of other CFR variants that incorporate modern enhancements (e.g., CFR+ or discounting techniques). A broader implementation encompassing these would increase the relevance of this work.

Limited Exploration of Advanced CFR Variants: The paper does not explore compatibility with modern CFR variants, such as sampling-based or discounting techniques, which are widely used in state-of-the-art game-solving algorithms. This omission reduces the approach’s applicability in advanced game AI contexts.

High Memory Requirements: The matrix-based reformulation, while speeding up calculations, results in high memory consumption, especially for larger games. This trade-off is not thoroughly analyzed or discussed, particularly regarding potential bottlenecks for memory-constrained systems, which limits practical usability.

Narrow Application Scope: The results indicate that this GPU implementation is unsuitable for small games, where it can actually perform worse than CPU implementations due to overhead. This could reduce its perceived impact and limits its practicality in domains that deal with a wide range of game sizes.

---

confidence: 4
contribution: 3
initial_rating: 3
presentation: 3
questions: - What was the inspiration for using CuPy?
- Why are there no exploitability results?
- How long does it take to setup the game tree?
- Were 32 or 64-bit floats used? Were tensor cores enabled?

- 022- The abstract is used in the introduction
- 037- GPU is defined twice
- 062- What is the philosophical reason for making the nature player have infosets? I find this very nonstandard
- 163- While CFR can find approximate coarse correlated equilibrium, the formulation presented in this paper does not. The reason is that it is not the product of average strategies that converges to the set of CCEs, but rather the average product.
- 175- The introduction should include the CFR theorem ($r^{(T)}(i_{+,j}\in\mathbf{I}_{+})$ is bounded by the sum of the local regrets)
- 201- Case in point in that this paper tries to inflate its notation, $l\in[1, D]\cap \mathbf{Z}$ is just weird.
- 292- Hadamard product was not defined. I would argue that it is not a common notation and should be defined explicitly.
- 397- It is not clear what purpose Figure 1 serves in the paper.
- 432- Why is there no error bar on the time measurements?
- 515- I understand that pruning the tree may be expensive (surely a very big downside) but why is alternating CFR hard to implement?
- 523- "Our approach is also much easier (and likely more efficient) to be run on supercomputers compared to previous methods" This statement is not backed by anything in this paper, see Weaknesses.
- 651- the number of infosets for liars_dice seems to be wrong, it should be 24576 not 24583 (or 12288 if we remove infosets with only one action).
soundness: 3
strengths: This paper is interesting because it tries to solve two problems at the same time:
- APIs like [GraphBLAS](https://graphblas.org/) have successfully represented graph algorithms as a sequence of BLAS-like operations over semirings. This paper tries to do the same for CFR.
- It's not obvious how GPUs, the powerhouse of deep learning, can be used to accelerate game solving (other than calling neural networks). This paper tries to solve this gap.
summary: This paper aims to frame the CFR algorithm as a sequence of matrix operations (Think GraphBlas).
weaknesses: Overall, this paper tries to aim for a best-of-both-worlds approach: low coding effort and high performance. 
Instead, it ends up with an exposition that is somehow less clear than the original CFR paper, benchmarks that don't inspire confidence, and the resulting algorithm seems to be not very flexible and requires major efforts to do the simplest changes like going from simultaneous to alternating variants of CFR.
 
- The open spiel codebase is not an example of a performant CFR implementation, it is meant to be extremely generic. Comparing with more reasonable implementations is necessary (for instance the Cepheus codebase for Leduc, there are other codebases as well).
- The games tested are extremely tiny. The largest game (tic tac toe) takes less than 3 seconds to traverse on a pure Python implementation and is a perfect information game. It's not clear what a perfect information game is doing there. The number of nodes in Appendix A is the number of infosets + terminals (i.e., there is only one node per infoset), and looking at the code, `tic_tac_toe.py` is not a dark variant of tic-tac-toe.
- The updates are batched and masked. Effectively, for each depth $d$, a (sparse) matrix multiply is done but only the output at depth $d$ is stored. As a matter of efficiency, this method becomes more and more wasteful as the depth of the game increases.
- Modifying the algorithm seems extremely expensive and cumbersome. (see  line 515)
- The computations presented here are probably not very GPU friendly and a lot of FLOPS are probably wasted (Yet this has not been analyzed).
- The paper does not include any exploitability results.

---

confidence: 1
contribution: 2
initial_rating: 3
presentation: 2
questions: see above
soundness: 2
strengths: The acceleration seems quite significant as the author claimed.
summary: This paper studies hardware acceleration for counterfactual regret minimization.
weaknesses: Well, it is unclear to me if this paper fits well for ICLR since there is no new algorithm / methodology / theory proposed. It may fit more to ML system venue. The benchmark selected (Game in OpenSpiel) is less known. I will suggest show improvements on more common benchmarks. I have to admit I do not have sufficient GPU hardware background to evaluate this paper.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: * What is the space complexity of the method?
* Can this method be used to accelerate the calculation of exploitability?

Minor Suggestions:

* It will help to improve clearity by adding a symbol table and an example figure.
* It will help to enhance readability by keeping the symbol descriptions consistent with CFR literatures, such as using $I$ for an information set and $h$ for a history node.
soundness: 3
strengths: * The paper is well-written, and the notations are clearly defined.
* The GPU implementation significantly boosts the speed of the CFR algorithm, and the difference from the OpenSpiel implementation grows as the game size increases.
* The code is open-sourced, making it easy to apply to games in OpenSpiel.
summary: This paper proposes a GPU implementation of the CFR algorithm. It stores the game tree structure in matrices and performs a series of matrix operations to compute reach probabilities, expected payoffs, and other relevant information level by level, thereby avoiding the costly tree traversal process. By leveraging GPU acceleration for these matrix operations, the approach significantly enhances CFR’s speed, albeit at the expense of increased memory usage.
weaknesses: This is not the first approach to implementing CFR on GPUs. For example, the thesis by Reis [1] and the report by Weng [2] also present GPU implementations of CFR. Additionally, DeepStack [3] [4] constructs the look-ahead tree and runs CFR on GPUs. These works and this paper use a similar approach, computing relevant information in CFR level by level and accelerating it with GPUs. However, the paper does not compare or discuss these related works.

[1] Reis J. A gpu implementation of counterfactual regret minimization. Master Thesis, University of Porto, 2015.

[2] Weng L. Counterfactual regret minimization on gpu.
https://cent.felk.cvut.cz/courses/GPU/archives/2020-2021/W/rudolja1/, 2021

[3] Moravčík M, Schmid M, Burch N, et al. Deepstack: Expert-level artificial intelligence in heads-
up no-limit poker. Science, 2017, 356(6337): 508-513.

[4] Schmid M. DeepStack for Leduc Hold'em. https://github.com/lifrordi/DeepStack-Leduc, 2017

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: * Is OpenSpiel’s implementation paralleled? I think this can have a lot of differences in the performance. Only comparing with the benchmark implementation can be limited.
* You showed there is a trade-off for memory efficiency and computation time. However I don’t see there are any reasons on this if we store every sparse matrix within the corresponding format. Can you further explain this?
soundness: 2
strengths: * Leveraging GPUs to improve the computation for game solving is still under-explored and this manuscript has a solid step towards it.
summary: This manuscript discussed about how to leverage GPU’s computation power on sparse matrix multiplication to improve the computation speed for large scale games.
weaknesses: * This is a more engineering-driven paper without lots of scientific contribution.
* I’m not quite sure about where the benefit is from. See the questions.

Meta-review: Before going into details, I want to thank again the reviewers and the authors for engaging so actively on this paper. 

My position on this paper was summarized in detail in my post during the response period. To restate the crux of it, from my point of view, the main merit of the authors' contribution is that it would provide the community with an open-source implementation of CFR that is significantly faster than the default Python one in OpenSpiel, while retaining compatibility with OpenSpiel games. Furthermore, I think that the authors have addressed many of the points that the reviewers brought up.

After the end of the response period, I contacted Reviewer dyt9 to try to understand better their position, and we had an in-depth conversation. Overall, I think I made progress in convincing them that the community would find the contribution useful. However, they still seemed not enthusiastic about the paper. From my understanding, their point of view is that nobody that really needs to squeeze performance out of a game solver would use or compare against OpenSpiel's implementations. And on top, they were not in love with the graph-based approach used in this paper to implement CFR, and thought that a level-based approach would do better. Finally, they didn't love the fact that alternation was not supported.

Overall, while I like the paper, for me to override five reviewers and push this paper through seems extreme. The review panel included knowledgeable people on extensive-form games, and I know that Reviewer dyt9 has hands-on experience with implementing GPU-accelerated first-order optimization solvers. 

As a concrete suggestion for future iterations, I would recommend implementing alternation, both as a way to dismiss concerns that the approach used in the paper is too restrictive, and also since alternation usually performs well in extensive-form games. It might also help to discuss different design that have been considered and why they were discarded; such a discussion could also help future implementations by other groups as well.

Decision: Reject