Hierarchical Deep Counterfactual Regret Minimization

First, we introduce the extensive game model with imperfect information (Osborne and Rubinstein (1994)). In an extensive game, players make sequential moves represented by a game tree. At each non-terminal state, the player in control chooses from a set of available actions. At each terminal state, each player receives a payoff. In the presence of imperfect information, a player may not know which state they are in. For instance, in a poker game, a player sees its own cards and all cards laid on the table but not the opponents’ hands. Therefore, at each time step, each player makes decisions based on an information set – a collection of states that the controlling player cannot distinguish. Formally, the extensive game model can be represented by a tuple $<N,H,A,P,\sigma_{c},u,\mathcal{I}>$. $N$ is a finite set of players. $H$ is a set of histories, where each history is a sequence of actions of all players from the start of the game and corresponds to a game state. For $h,h^{\prime}\in H$, we write $h\sqsubseteq h^{\prime}$ if $h$ is a prefix of $h^{\prime}$. The set of actions available at $h\in H$ is denoted as $A(h)$. Suppose $a\in A(h)$, then $(ha)\in H$ a successor history of $h$. Histories with no successors are terminal histories $H_{TS}\subseteq H$. $P:H\backslash H_{TS}\rightarrow N\cup\{c\}$ maps each non-terminal history to the player that chooses the next action, where $c$ is the chance player that acts according to a predefined distribution $\sigma_{c}(\cdot|h)$. This chance player represents the environment’s inherent randomness, such as using a dice roll to decide the starting player. The utility function $u:N\times H_{TS}\rightarrow\mathbb{R}$ assigns a payoff for every player at each terminal history. For a player $i$, $\mathcal{I}_{i}$ is a partition of $\{h\in H:P(h)=i\}$ and each element $I_{i}\in\mathcal{I}_{i}$ is an information set as introduced above. $I_{i}$ also represents the observable information for $i$ shared by all histories $h\in I_{i}$. Due to the indistinguishability, we have $A(h)=A(I_{i}),\ P(h)=P(I_{i})$. Notably, our work focus on the two-player zero-sum setting, where $N=\{1,2\}$ and $u_{1}(h)=-u_{2}(h),\ \forall\ h\in H_{TS}$, like previous works on CFR (Zinkevich et al. (2007); Brown et al. (2019); Davis et al. (2020)).

Every player $i\in N$ selects actions according to a strategy $\sigma_{i}$ that maps each information set $I_{i}$ to a distribution over actions in $A(I_{i})$. Note that $\sigma_{i}(\cdot|h)=\sigma_{i}(\cdot|I_{i}),\ \forall\ h\in I_{i}$. The learning target of CFR is a Nash Equilibrium (NE) strategy profile $\sigma^{*}=\{\sigma_{1}^{*},\sigma_{2}^{*}\}$, where no player has an incentive to deviate from their specified strategy. That is, $u_{i}(\sigma^{*})\geq\max_{\sigma_{i}}u_{i}(\{\sigma_{i},\sigma_{-i}^{*}\}),\ \forall\ i\in{N}$, where $-i$ represents the players other than $i$, $u_{i}(\sigma)$ is the expected payoff to player $i$ of $\sigma$ and defined as follows:

$\displaystyle u_{i}(\sigma)=\sum_{h^{\prime}\in H_{TS}}u_{i}(h^{\prime})\pi^{\sigma}(h^{\prime}),\ \pi^{\sigma}(h^{\prime})=\prod_{(ha)\sqsubseteq h^{\prime}}\sigma_{P(h)}(a|I(h))$

(1)

$I(h)$ denotes the information set containing $h$, and $\pi^{\sigma}(h)$ is the reach probability of $h$ when employing $\sigma$. $\pi^{\sigma}(h)$ can be decomposed as $\prod_{i\in N\cup\{c\}}\pi_{i}^{\sigma}(h)$, where $\pi_{i}^{\sigma}(h)=\prod_{(ha)\sqsubseteq h^{\prime},P(h)=i}\sigma_{i}(a|I(h))$. In addition, $\pi^{\sigma}(I)=\sum_{h\in I}\pi^{\sigma}(h)$ represents the reach probability of the information set $I$.

CFR proposed in Zinkevich et al. (2007) is an iterative algorithm which accumulates the counterfactual regret $R_{i}^{T}(a|I)$ for each player $i$ at each information set $I\in\mathcal{I}_{i}$. This regret informs the strategy determination. $R_{i}^{T}(a|I)$ is defined as follows:

	$\displaystyle R_{i}^{T}(a|I)=\frac{1}{T}\sum_{t=1}^{T}\pi^{\sigma^{t}}_{-i}(I)(u_{i}(\sigma^{t}|_{I\rightarrow a},I)-u_{i}(\sigma^{t},I))$		(2)
	$\displaystyle u_{i}(\sigma,I)=\sum_{h\in I}\pi_{-i}^{\sigma}(h)\sum_{h^{\prime}\in H_{TS}}\pi^{\sigma}(h,h^{\prime})u_{i}(h^{\prime})/\pi^{\sigma}_{-i}(I)$

where $\sigma^{t}$ is the strategy profile at iteration $t$, $\sigma^{t}|_{I\rightarrow a}$ is identical to $\sigma^{t}$ except that the player always chooses the action $a$ at $I$, $\pi^{\sigma}(h,h^{\prime})$ denotes the reach probability from $h$ to $h^{\prime}$ which equals $\frac{\pi^{\sigma}(h^{\prime})}{\pi^{\sigma}(h)}$ if $h\sqsubseteq h^{\prime}$ and 0 otherwise. Intuitively, $R_{i}^{T}(a|I)$ represents the expected regret of not choosing action $a$ at $I$. With $R_{i}^{T}(a|I)$, the next strategy profile $\sigma^{T+1}_{i}(\cdot|I)$ is acquired with regret matching (Abernethy et al. (2011)), which sets probabilities proportional to the positive regrets: $\sigma^{T+1}_{i}(a|I)\propto\max(R_{i}^{T}(a|I),0)$. Defining the average strategy $\overline{\sigma}^{T}_{i}(\cdot|I)$ such that $\overline{\sigma}^{T}_{i}(a|I)\propto\sum_{t=1}^{T}\pi_{i}^{\sigma^{t}}(I)\sigma^{t}_{i}(a|I)$, CFR guarantees that the strategy profile $\overline{\sigma}^{T}=\{\overline{\sigma}^{T}_{i}|i\in N\}$ converges to a Nash Equilibrium as $T\rightarrow\infty$.

As proposed in Sutton et al. (1999), an option $z\in\mathcal{Z}$ can be described with three components: an initiation set $Init_{z}\subseteq\mathcal{S}$, an intra-option policy $\sigma_{z}(a|s):\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$, and a termination function $\beta_{z}(s):\mathcal{S}\rightarrow[0,1]$. $\mathcal{S}$, $\mathcal{A}$, $\mathcal{Z}$ represent the state, action, option space, respectively. An option $z$ is available in state $s$ if and only if $s\in Init_{z}$. Once the option is taken, actions are selected according to $\sigma_{z}$ until it terminates stochastically according to $\beta_{z}$, i.e., the termination probability at the current state. A new option will be activated by a high-level policy $\sigma_{\mathcal{Z}}(z|s):\mathcal{S}\times\mathcal{Z}\rightarrow[0,1]$ once the previous option terminates. In this way, $\sigma_{\mathcal{Z}}(z|s)$ and $\sigma_{z}(a|s)$ constitute a hierarchical policy for a certain task. Hierarchical policies tend to have superior performance on complex long-horizon tasks which can be broken down into and processed as a series of subtasks.

The one-step option framework (Li et al. (2021a)) is proposed to learn the hierarchical policy without the extra need to justify the exact beginning and breaking condition of each option, i.e., $Init_{z}$ and $\beta_{z}$. First, it assumes that each option is available at each state, i.e., $Init_{z}=\mathcal{S},\forall\ z\in\mathcal{Z}$. Second, it redefines the high-level and low-level policies as $\sigma^{H}(z|s,z^{\prime})$ ($z^{\prime}$: the option in the previous timestep) and $\sigma^{L}(a|s,z)$, respectively, and implementing them as end-to-end neural networks. In particular, the Multi-Head Attention (MHA) mechanism (Vaswani et al. (2017)) is adopted in $\sigma^{H}(z|s,z^{\prime})$, which enables it to temporally extend options in the absence of the termination function $\beta_{z}$. Intuitively, if $z^{\prime}$ still fits $s$, $\sigma^{H}(z|s,z^{\prime})$ will assign a larger attention weight to $z^{\prime}$ and thus has a tendency to continue with it; otherwise, a new option with better compatibility will be sampled. Then, the option is sampled at each timestep rather than after the previous option terminates. With this simplified framework, we only need to train the hierarchical policy, i.e., $\sigma^{H}$ and $\sigma^{L}$.

The option framework is proposed within the realm of RL as opposed to CFR; however, these two fields are closely related. The authors of (Srinivasan et al. (2018); Fu et al. (2022)) propose actor-critic algorithms for multi-agent adversarial games with partial observability and show that they are indeed a form of MCCFR for IIGs. This insight inspires our adoption of the one-step option framework to create a hierarchical extension for CFR.

At a game state $h$, the player $i$ makes its $t$-th decision by selecting a hierarchical action $\widetilde{a}_{t}\triangleq(z_{t},a_{t})$, i.e., the option (a.k.a., skill) and primitive action, based on the observable information for player $i$ at $h$, including the private observations $o_{1:t}$ and decision sequence $\widetilde{a}_{1:(t-1)}$ of player $i$, and the public information for all players (defined by the game). All histories that share the same observable information are considered indistinguishable to player $i$ and belong to the same information set $I_{i}$. Thus, in this work, we also use $I_{i}$ to denote observations upon which player $i$ makes decisions. With the hierarchical actions, we can redefine the extensive game model as $<N,H,\widetilde{A},P,\sigma_{c},u,\mathcal{I}>$. Here, $N$, $P$, $u$, and $\mathcal{I}$ retain the definitions in Section 2.1. $H$ includes all the possible histories, each of which is a sequence of hierarchical actions of all players starting from the first time step. $\widetilde{A}(h)=Z(h)\times A(h)$, where $Z(h)$ and $A(h)$ represent the options and primitive actions available at $h$ respectively. $\sigma_{c}((z_{c},a)|h)=\sigma_{c}(a|h)$, where $\sigma_{c}(a|h)$ is the predefined distribution in the original game model and $z_{c}$ (a dummy variable) is the only option choice for the chance player.

The learning target for player $i$ is a hierarchical strategy $\sigma_{i}(\widetilde{a}_{t}|I_{i})$, which, by the chain rule, can be decomposed as $\sigma_{i}^{H}(z_{t}|I_{i})\cdot\sigma_{i}^{L}(a_{t}|I_{i},z_{t})$. Note that although $I_{i}$ includes $z_{1:t-1}$, we follow the conditional independence assumption of the one-step option framework (Li et al. (2021a); Zhang and Whiteson (2019)) which states that $z_{t}\perp\!\!\!\perp z_{1:(t-2)}\ |\ z_{t-1}$ and $a_{t}\perp\!\!\!\perp z_{1:(t-1)}\ |\ z_{t}$, thus only $z_{t-1}$ ($z_{t}$) is used for $\sigma_{i}^{H}$ ($\sigma_{i}^{L}$) to determine $z_{t}$ ($a_{t}$). With the hierarchical strategy, we can redefine the expected payoff and reach probability in Equation (1) by simply substituting $a$ with $\widetilde{a}$, based on which we have the definition of the average overall regret of player $i$ at iteration $T$: (From this point forward, $t$ refers to a certain learning iteration rather than a time step within an iteration.)

$\displaystyle R_{full,i}^{T}=\frac{1}{T}\max_{\sigma_{i}^{{}^{\prime}}}\sum_{t=1}^{T}(u_{i}(\{\sigma_{i}^{{}^{\prime}},\sigma_{-i}^{t}\})-u_{i}(\sigma^{t}))$

(3)

The following theorem (Theorem 2 from Zinkevich et al. (2007)) provides a connection between the average overall regret and the Nash Equilibrium solution.

Here, the average strategy $\overline{\sigma}^{T}_{i}$ is defined as ($\forall\ i\in N,I\in\mathcal{I}_{i},\widetilde{a}\in\widetilde{A}(I)$):

$\displaystyle\overline{\sigma}^{T}_{i}(\widetilde{a}|I)=\left(\Sigma_{t=1}^{T}\pi_{i}^{\sigma^{t}}(I)\sigma^{t}_{i}(\widetilde{a}|I)\right)/\Sigma_{t=1}^{T}\pi_{i}^{\sigma^{t}}(I)$

(4)

An $\epsilon$-Nash Equilibrium $\sigma$ approximates a Nash Equilibrium, with the property that $u_{i}(\sigma)+\epsilon\geq\max_{\sigma_{i}^{{}^{\prime}}}u_{i}(\{\sigma_{i}^{{}^{\prime}},\sigma_{-i}\}),\ \forall\ i\in{N}$. Thus, $\epsilon$ measures the distance of $\sigma$ to the Nash Equilibrium in expected payoff. Then, according to Theorem 1, as $R_{full,i}^{T}\rightarrow 0$ ($\forall\ i\in N$), $\overline{\sigma}^{T}$ converges to NE. Notably, Theorem 1 can be applied directly to our hierarchical setting, as the only difference from the original setting related to Theorem 1 is the replacement of $a$ with $\widetilde{a}$ in $R_{full,i}^{T}$ and $\overline{\sigma}^{T}_{i}(\widetilde{a}|I)$. This difference can be viewed as employing a new action space (i.e., $A\rightarrow\widetilde{A}$) and is independent of using the option framework (i.e., the hierarchical extension).

One straightforward way to learn a hierarchical strategy $\sigma_{i}(\widetilde{a}|I)=\sigma_{i}^{H}(z|I)\cdot\sigma_{i}^{L}(a|I,z)$ is to view $\sigma_{i}(\widetilde{a}|I)$ as a unified strategy defined on a new action set $\widetilde{A}$, and then apply CFR directly to learn it. However, this approach does not allow for the explicit separation and utilization of the high-level and low-level components, such as extracting and reusing skills (i.e., low-level parts) or initializing them with human knowledge. In this section, we treat $\sigma_{i}^{H}$ and $\sigma_{i}^{L}$ as distinct functions and introduce Hierarchical CFR (HCFR) to separately learn $\sigma_{i}^{H}(z|I)$ and $\sigma_{i}^{L}(a|I,z),\forall\ I\in\mathcal{I}_{i},z\in Z(I),a\in A(I)$. Additionally, we provide the convergence guarantee for HCFR.

Taking inspiration from CFR (Zinkevich et al. (2007)), we derive an upper bound for the average overall regret $R_{full,i}^{T}$, which is given by the sum of high-level and low-level counterfactual regrets at each information set, namely $R^{T,H}_{i}(z|I)$ and $R^{T,L}_{i}(a|I,z)$. In this way, we can minimize $R^{T,H}_{i}(z|I)$ and $R^{T,L}_{i}(a|I,z)$ for each individual $I\in\mathcal{I}_{i}$ independently by adjusting $\sigma_{i}^{H}(z|I)$ and $\sigma_{i}^{L}(a|I,z)$ respectively, and in doing so, minimize the average overall regret. The learning of the high-level and low-level strategy is also decoupled.

Here, $R^{T,H}_{i,+}(I)=\max(R^{T,H}_{i}(I),0),\ R^{T,L}_{i,+}(I,z)=\max(R^{T,L}_{i}(I,z),0)$, $u_{i}(\sigma^{t},Iz)$ is the expected payoff for choosing option $z$ at $I$, $\sigma^{t}|_{Iz\rightarrow a}$ is a hierarchical strategy profile identical to $\sigma^{t}$ except that the intra-option (i.e., low-level) strategy of option $z$ at $I$ is always choosing $a$. Detailed proof of Theorem 2 is available in Appendix A.

After obtaining $R^{T,H}_{i}$ and $R^{T,L}_{i}$, we can compute the high-level and low-level strategies for the next iteration as follows: ($\forall\ i\in N,I\in\mathcal{I}_{i},z\in Z(I),a\in A(I)$)

		$\displaystyle\ \ \ \ \sigma_{i}^{T+1,H}(z|I)=\left\{\begin{aligned} R^{T,H}_{i,+}(z|I)/\mu^{H}&,&\mu^{H}>0,\\ 1/|Z(I)|&,&o\backslash w.\end{aligned}\right.\ \ \ \ \mu^{H}=\sum_{z^{\prime}\in Z(I)}R^{T,H}_{i,+}(z^{\prime}|I)$		(6)
		$\displaystyle\sigma_{i}^{T+1,L}(a|I,z)=\left\{\begin{aligned} R^{T,L}_{i,+}(a|I,z)/\mu^{L}&,&\mu^{L}>0,\\ 1/|A(I)|&,&o\backslash w.\end{aligned}\right.\ \ \ \ \mu^{L}=\sum_{a^{\prime}\in A(I)}R^{T,L}_{i,+}(a^{\prime}|I,z)$

In this way, the counterfactual regrets and strategies are calculated alternatively (i.e., $\sigma^{1:t}\rightarrow R^{t}\rightarrow\sigma^{t+1},\ \sigma^{1:t+1}\rightarrow R^{t+1}\rightarrow\sigma^{t+2},\ \cdots$) with Equation (5) and (6) for iterations until convergence (i.e., $R_{full,i}^{T}\rightarrow 0$). The convergence rate of this algorithm is presented in the following theorem:

Thus, as $T\rightarrow\infty$, $R_{full,i}^{T}\rightarrow 0$. Additionally, the convergence rate is $\mathcal{O}(T^{-0.5})$, which is the same as CFR (Zinkevich et al. (2007)). Thus, the introduction of the option framework does not compromise the convergence guarantee, while allowing skill-based strategy learning. The proof of Theorem 3 is provided in Appendix B.

With $\sigma^{t,H}_{i}$ and $\sigma^{t,L}_{i}$, we can compute the average high-level and low-level strategies as:

$\displaystyle\overline{\sigma}^{T,H}_{i}(z|I)=\frac{\Sigma_{t=1}^{T}\pi_{i}^{\sigma^{t}}(I)\sigma^{t,H}_{i}(z|I)}{\Sigma_{t=1}^{T}\pi_{i}^{\sigma^{t}}(I)},\ \ \ \ \overline{\sigma}^{T,L}_{i}(a|I,z)=\frac{\Sigma_{t=1}^{T}\pi_{i}^{\sigma^{t}}(Iz)\sigma^{t,L}_{i}(a|I,z)}{\Sigma_{t=1}^{T}\pi_{i}^{\sigma^{t}}(Iz)}$

(7)

where $\pi_{i}^{\sigma^{t}}(Iz)=\pi_{i}^{\sigma^{t}}(I)\sigma_{i}^{t,H}(z|I)$. Then, we can state:

The proof is based on Theorem 1, for which you can refer to Appendix C.

In vanilla CFR, counterfactual regrets and immediate strategies are updated for every information set during each iteration. This necessitates a complete traversal of the game tree, which becomes infeasible for large-scale game models. Monte Carlo CFR (MCCFR) (Lanctot et al. (2009)) is a framework that allows CFR to only update regrets/strategies on part of the tree for a single agent (i.e., the traverser) at each iteration. MCCFR features two sampling scheme variants: External Sampling (ES) and Outcome Sampling (OS). In OS, regrets/strategies are updated for information sets within a single trajectory that is generated by sampling one action at each decision point. In ES, a single action is sampled for non-traverser agents, while all actions of the traverser are explored, leading to updates over multiple trajectories. ES relies on perfect game models for backtracking and becomes impractical as the horizon increases, with which the search breadth grows exponentially. Our algorithm is specifically designed for domains with deep game trees, leading us to adopt OS as the sampling scheme. Nevertheless, OS is challenged by high sample variance, an issue that exacerbates with an increasing decision-making horizon. Therefore, in this section, we further complete our algorithm with a low-variance outcome sampling extension.

MCCFR’s main insight is substituting the counterfactual regrets $R^{T}_{i}$ with unbiased estimations, while maintaining the other learning rules (as in Section 3.2). This allows for updating functions only on information sets within the sampled trajectories, bypassing the need to traverse the full game tree. With MCCFR, the average overall regret $R_{full,i}^{T}\rightarrow 0$ as $T\rightarrow\infty$ at the same convergence rate as vanilla CFR, with high probability, as stated in Theorem 5 of Lanctot et al. (2009). Therefore, to apply the Monte Carlo extension, we propose unbiased estimations of $R^{T,H}_{i}(z|I)$ and $R^{T,L}_{i}(a|I,z)$, $\forall\ i\in N,I\in\mathcal{I}_{i},z\in Z(I),a\in A(I)$.

First, we define $R^{T,H}_{i}(z|I)$ and $R^{T,L}_{i}(a|I,z)$ with the immediate counterfactual regrets $r^{t}_{i}$ and values $v_{i}^{t}$: ($v^{t,H}_{i}(\sigma^{t},h)=u_{i}(h),\ \forall\ h\in H_{TS}$)

		$\displaystyle\quad\ R_{i}^{T,H}(z|I)=\frac{1}{T}\sum_{t=1}^{T}r_{i}^{t,H}(I,z),\ r_{i}^{t,H}(I,z)=\sum_{h\in I}\pi_{-i}^{\sigma^{t}}(h)\left[v^{t,L}_{i}(\sigma^{t},hz)-v^{t,H}_{i}(\sigma^{t},h)\right]$		(8)
		$\displaystyle R_{i}^{T,L}(a|I,z)=\frac{1}{T}\sum_{t=1}^{T}r_{i}^{t,L}(Iz,a),\ r_{i}^{t,L}(Iz,a)=\sum_{h\in I}\pi_{-i}^{\sigma^{t}}(h)\left[v^{t,H}_{i}(\sigma^{t},hza)-v^{t,L}_{i}(\sigma^{t},hz)\right]$
		$\displaystyle v^{t,H}_{i}(\sigma^{t},h)=\sum_{z\in Z(h)}\sigma^{t,H}_{P(h)}(z|h)v_{i}^{t,L}(\sigma^{t},hz),\ v_{i}^{t,L}(\sigma^{t},hz)=\sum_{a\in A(h)}\sigma^{t,L}_{P(h)}(a|h,z)v^{t,H}_{i}(\sigma^{t},hza)$

The equivalence between Equation (8) and (5) is proved in Appendix D.

Next, we propose to collect trajectories $h^{\prime}\in H_{TS}$ with the sample strategy $q^{t}$ at each iteration $t$, and compute the corresponding sampled immediate counterfactual regrets $\hat{r}^{t}_{i}$ and values $\hat{v}_{i}^{t}$ as follows:

		$\displaystyle\ \ \hat{r}_{i}^{t,H}(I,z|h^{\prime})=\sum_{h\in I}\frac{\pi_{-i}^{\sigma^{t}}(h)}{\pi^{q^{t}}(h)}\left[\hat{v}^{t,H}_{i}(\sigma^{t},h,z|h^{\prime})-\hat{v}^{t,H}_{i}(\sigma^{t},h|h^{\prime})\right]$		(9)
		$\displaystyle\hat{r}_{i}^{t,L}(Iz,a|h^{\prime})=\sum_{h\in I}\frac{\pi_{-i}^{\sigma^{t}}(h)}{\pi^{q^{t}}(hz)}\left[\hat{v}^{t,L}_{i}(\sigma^{t},hz,a|h^{\prime})-\hat{v}^{t,L}_{i}(\sigma^{t},hz|h^{\prime})\right]$

Here, inspired by Davis et al. (2020), $\hat{v}^{t,H}_{i}(\sigma^{t},h,z|h^{\prime})$ and $\hat{v}^{t,L}_{i}(\sigma^{t},hz,a|h^{\prime})$ are incorporated with the baseline function $b^{t}_{i}$ for variance reduction: ($\hat{v}^{t,H}_{i}(\sigma^{t},h^{\prime}|h^{\prime})=u_{i}(h^{\prime})$)

		$\displaystyle\quad\ \ \hat{v}^{t,H}_{i}(\sigma^{t},h,z|h^{\prime})=\frac{\delta(hz\sqsubseteq h^{\prime})}{q^{t}(z|h)}\left[\hat{v}^{t,L}_{i}(\sigma^{t},hz|h^{\prime})-b_{i}^{t}(h,z)\right]+b^{t}_{i}(h,z)$		(10)
		$\displaystyle\hat{v}^{t,L}_{i}(\sigma^{t},hz,a|h^{\prime})=\frac{\delta(hza\sqsubseteq h^{\prime})}{q^{t}(a|h,z)}\left[\hat{v}^{t,H}_{i}(\sigma^{t},hza|h^{\prime})-b^{t}_{i}(h,z,a)\right]+b^{t}_{i}(h,z,a)$

where $\delta(\cdot)$ is the indicator function. Accordingly, $\hat{v}^{t,H}_{i}(\sigma^{t},h|h^{\prime})$ and $\hat{v}^{t,L}_{i}(\sigma^{t},hz|h^{\prime})$ are defined as $\sum_{z\in Z(h)}\sigma^{t,H}_{P(h)}(z|h)\hat{v}_{i}^{t,H}(\sigma^{t},h,z|h^{\prime})$ and $\sum_{a\in A(h)}\sigma^{t,L}_{P(h)}(a|h,z)\hat{v}_{i}^{t,L}(\sigma^{t},hz,a|h^{\prime})$. (For superscripts on $\hat{r}$ and $\hat{v}$: use $H$ when the agent is in state $h$ or $hza$ for high-level option choices, and $L$ in state $hz$ for low-level action decisions.)

Regarding estimators proposed in Equation (9) and (10), we have the following theorems:

Therefore, we can acquire unbiased estimations of $R^{T}_{i}$ by substituting $r_{i}^{t}$ with $\hat{r}^{t}_{i}$ in Equation (8). This theorem is proved in Appendix E. Notably, Theorem 4 doesn’t prescribe any specific form for the baseline function $b^{t}_{i}$. Yet, the baseline design can affect the sample variance of these unbiased estimators. As posited in Gibson et al. (2012), given a fixed $\epsilon>0$, estimators with reduced variance necessitate fewer iterations to converge to an $\epsilon$-Nash equilibrium. Hence, we propose the following ideal criteria for the baseline function to minimize the sample variance:

The proof can be found in Appendix F. The ideal criteria for the baseline function proposed in Theorem 5 is incorporated into our objective design in Section 3.4.

To sum up, by employing the immediate counterfactual regret estimators shown as Equation (9) and (10), and making appropriate choices for the baseline function (introduced in Section 3.4), we are able to bolster the adaptability and learning efficiency of our method through a low-variance outcome Monte Carlo sampling extension.

Building upon theoretical foundations discussed in Section 3.2 and 3.3, we now present our algorithm – HDCFR. While the algorithm outline is similar to tabular CFR algorithms (Kakkad et al. (2019); Davis et al. (2020)), HDCFR differentiates itself by introducing NNs as function approximators for the counterfactual regret $R_{i}^{t}$, average strategy $\overline{\sigma}^{T}_{i}$, and baseline $b^{t}_{i}$. These approximations enable HDCFR to handle large-scale state spaces and are trained with specially-designed objective functions. In this section, we introduce the deep learning objectives, demonstrate their alignment with the theoretical underpinnings provided in Section 3.2 and 3.3, and then present the complete algorithm in pseudo-code form.

Three types of networks are trained: the counterfactual regret networks $R^{t,H}_{i,\theta},\ R^{t,L}_{i,\theta}$, average strategy networks $\overline{\sigma}^{T,H}_{i,\phi},\ \overline{\sigma}^{T,L}_{i,\phi}$, and baseline network $b^{t}$. Notably, we do not maintain the counterfactual values $\hat{v}^{t}$ and baselines $b^{t}$ for each player. Instead, we leverage the property of two-player zero-sum games where the payoff of the two players offsets each other. Thus, we track the payoff for player 1 and use the opposite value as the payoff for player 2. That is, $b^{t}=b^{t}_{1}=-b^{t}_{2}$, $v^{t}=v^{t}_{1}=-v^{t}_{2}$.

First, the counterfactual regret networks are trained by minimizing the following two objectives, denoted as $\mathcal{L}^{t,H}_{R,i}$ and $\mathcal{L}^{t,L}_{R,i}$, respectively.

$\displaystyle\mathop{\mathbb{E}}_{(I,\hat{r}^{t^{\prime},H}_{i})\sim\tau^{i}_{R}}\left[\sum_{z\in Z(I)}(R^{t,H}_{i,\theta}(z|I)-\hat{r}^{t^{\prime},H}_{i}(I,z))^{2}\right],\mathop{\mathbb{E}}_{(Iz,\hat{r}^{t^{\prime},L}_{i})\sim\tau^{i}_{R}}\left[\sum_{a\in A(I)}(R^{t,L}_{i,\theta}(a|I,z)-\hat{r}^{t^{\prime},L}_{i}(Iz,a))^{2}\right]$

(13)

Here, $\tau^{i}_{R}$ represents a memory containing the sampled immediate counterfactual regrets gathered from iterations 1 to $t$. As mentioned in Section 3.3, the counterfactual regrets (i.e., $R^{t,H}_{i}$ and $R^{t,L}_{i}$) should be replaced with their unbiased estimations acquired via Monte Carlo sampling. As a justification of our objective design, we claim:

Please refer to Appendix G for the proof. Observe that the counterfactual regrets are employed solely for calculating the strategy in the subsequent iteration, as per Equation (6). The positive scale factors $C_{1}$ and $C_{2}$ do not impact this calculation, as they appear in both the numerator and denominator and cancel each other out. Thus, $R^{t,H}_{i,*}$ and $R^{t,L}_{i,*}$ can be used in place of $R^{t,H}_{i}$ and $R^{t,L}_{i}$.

Second, the average strategy networks are learned based on the immediate strategies from iteration 1 to $T$. Specifically, they are learned by minimizing $\mathcal{L}^{H}_{\overline{\sigma},i}$ and $\mathcal{L}^{L}_{\overline{\sigma},i}$:

$\displaystyle\mathop{\mathbb{E}}_{(I,\sigma^{t,H}_{i})\sim\tau^{i}_{\overline{\sigma}}}\left[\sum_{z\in Z(I)}(\overline{\sigma}^{T,H}_{i,\phi}(z|I)-\sigma^{t,H}_{i}(z|I))^{2}\right],\ \mathop{\mathbb{E}}_{(Iz,\sigma^{t,L}_{i})\sim\tau^{i}_{\overline{\sigma}}}\left[\sum_{a\in A(I)}(\overline{\sigma}^{T,L}_{i,\phi}(a|I,z)-\sigma^{t,L}_{i}(a|I,z))^{2}\right]$

(14)

Notably, in our algorithm, the sampling scheme is specially designed to fulfill the subsequent proposition. Define $q^{t,i}$ as the sample strategy profile at iteration $t$ when $i$ is the traverser, meaning exploration occurs during $i$’s decision-making. $q^{t,i}_{p}$ is a uniformly random strategy when $p=i$, and equals to $\sigma^{t}_{p}$ when $p=3-i$ (i.e., the other player). Furthermore, samples in $\tau^{i}_{\overline{\sigma}}$ are gathered when the traverser is $3-i$ (so $i$ samples with $\sigma^{t}_{i}$). With this scheme, we assert: (refer to Appendix H for proof)