CFR-MIX: Solving Imperfect Information Extensive-Form Games with Combinatorial Action Space

1 Introduction

Extensive-form games provide a versatile framework capable of representing multiple agents, imperfect information, and stochastic events. Now there are many researches about solving two-player zero-sum extensive-games, such as computing Nash equilibria by linear programs [Shoham and LeytonBrown, 2008], double oracle algorithms [McMahan et al., 2003; Jain et al., 2011], and CFR [Zinkevich et al., 2008]. Meanwhile, these scalable algorithms have achieved many accomplishments. Double oracle algorithms [McMahan et al., 2003; Jain et al., 2011] have subsequently been applied to real-world attacker-defender scenarios. Heads-up limit hold'em poker was essentially solved [Bowling et al., 2015]. Later, significant progress has been made for heads-up nolimit hold'em poker based on CFR, such as Libratus [Brown et al., 2017] and DeepStack [Moravˇc´ık et al., 2017].

∗Equal contribution.

CFR is one of the most popular algorithms to solve imperfect-information extensive-form games which is an iterative algorithm to approximate a Nash equilibrium with repeated self-play between two regret-minimizing algorithms. Some sampling-based CFR variants [Lanctot et al., 2009; Gibson et al., 2012] are proposed to solve large games effectively. Nowadays, neural network function approximation is applied to CFR to solve larger games. Deep CFR [Brown et al., 2019], Single Deep CFR [Steinberger, 2019] and Double Neural CFR [Li et al., 2019] are algorithms aiming to approximate CFR using deep neural networks.

In this paper, we focus on a special type of two-player imperfect-information extensive-form zero-sum games, Team Adversary Games, in which a team of cooperative agents plays against an adversary and all agents in the team share one utility function. This game model captures many realworld scenarios, such as many policemen coordinate with each other to catch an attacker [Basilico et al., 2017]. The challenge of solving this type of games is that the size of the team's joint action space is exponential with the number of agents. For example, if the number of agents is 8 and every agent has 10 actions, then the size of team's action space will be 108 . CFR and its sampling-based variants use the tabular-form to record the joint action strategy which results in impracticality due to the limited memory. For algorithms using deep neural networks, e.g., Deep CFR and Double Neural CFR, it is ineffective to train the strategy network over the large action space. One way to avoid computing the joint action strategy is to let each agent compute its policy independently. However, this approach cannot promote the cooperative interaction between agents in the team and there is no theoretical guarantee to converge to the equilibrium in multiplayer games [Abou Risk et al., 2010]. Therefore, it is impractical to solve this type of game with existing algorithms.

To solve the exponential combinatorial action space problems in Team-Adversary Games, we propose a new framework of CFR: CFR-MIX. Firstly, inspired by the idea of centralized training with decentralized execution [Rashid et al., 2018], we propose a novel strategy representation that represents the team's joint action strategy using the individual strategy of each agent. We also define a consistency relationship between these two strategy representations to maintain the cooperation among agents in the team, which guarantees that the equilibrium with new strategy representation is a special team-maxmin equilibrium. To compute Nash equilibrium with individual strategy representation under the CFR framework, we transform the consistency relationship between strategies to the consistency relationship between the cumulative regret values of joint actions and the cumulative regret values of individual actions. Furthermore, a novel decomposition method over cumulative regret values is proposed to guarantee the consistency relationship between the cumulative regret values. To implement the decomposition method, CFR-MIX employs a mixing layer that estimates cumulative regret values of joint actions as a non-linear combination of cumulative regret values of individual actions. To further improve the performance, the parameter sharing technique is applied among all agents in the team, which also reduces the network parameters dramatically. Finally, experimental results show that CFR-MIX outperforms state-of-theart algorithms significantly on games in different domains.

2 Background

2.1 Extensive-FormGame

An Extensive-Form Game (EFG) [Shoham and Leyton-Brown, 2008] can be formulated by a tuple (N,H,A, P, I, u). N = {1, ..., n} is a set of players. H is a set of histories (i.e., the possible action sequences). The empty sequence ∅ which is the root node of game tree is in H, and every prefix of a sequence in H is also in H. Z ⊂ H is the set of the terminal histories. A(h) = {a : (h, a) ∈ H} is the set of available actions at a non-terminal history h ∈ H. P is the player function. P(h) is the player who takes an action at the history h, i.e., P(h) ↦→ P ∪ {c}. c denotes the "chance player", which represents stochastic events outside of the players' control. If P(h) = c then chance determines the action taken at history h. Information sets Ii form a partition over histories h where player i ∈ N takes action. Therefore, every information set Ii ∈ Ii corresponds to one decision point of player i which means that P(h1) = P(h2) and A(h1) = A(h2) for any h1, h2 ∈ Ii. For convenience, we use A(Ii) to represent the set A(h) and P(Ii) to represent the player P(h) for any h ∈ Ii. For each player i ∈ N, a utility function is a mapping ui : Z → R.

A player's behavior strategy σi is a function mapping every information set of player i to a probability distribution over A(Ii). A strategy profile σ consists of a strategy for each player σ1, σ2, ..., with σ-i referring to all the strategies in σ except σi. Let πσ (h) be the reaching probability of history h if players choose actions according to σ. Given a strategy profile σ, the overall value to player i is the expected payoff of the resulting terminal node, ui(σ) = ∑h∈Z πσ (h)ui(h).

In this paper, we consider a type of imperfect-information extensive-form games, Team-Adversary Game, that consists of an adversary V and one team T. The team is formed by multiple agents R = {1, ..., n}. Every agent i has its own available action set ATi . Therefore, the team's action set includes all joint actions that are the combinations of all agents'

individual actions, i.e., AT = ×i∈RATi . Here, we focus on zero-sum games, i.e., uT(z) = -uV(z) for ∀z ∈ Z. Nash equilibrium [Nash, 1950] is adopted as our solution concept which is a strategy profile such that no player can get more reward by switching to a different strategy unilaterally. Formally, in Team-Adversary Games, a Nash Equilibrium (NE) is a strategy profile σ where

An approximation of a Nash Equilibrium or ϵ-Nash equilibrium is a strategy profile σ where

2.2 Counterfactual Regret Minimization

CFR is a family of iterative algorithms that are the most popular approach to approximately solve large imperfectinformation games [Zinkevich et al., 2008]. To define the concept, first consider repeatedly playing games. Let σt i be the strategy used by player i on round t. We define ui(σ, h) as the expected utility of player i given that the history h is reached and then all players play according to strategy σ from that point on. Let's define ui(σ, h·a) as the expected utility of player i given that the history h is reached and then all players play according to strategy σ except that player i selects action a in the history h. Formally, ui(σ, h) = ∑z∈Z πσ (h, z)ui(z) and ui(σ, h · a) = ∑z∈Z πσ (h · a, z)ui(z).

The counterfactual value uσi (I) is the expected value of an information set I given that player i tries to reach it. This value is the weighted average of the value of each history in an information set. The weight is proportional to the contribution of all players other than i to reach each history. Thus, uσi (I) = ∑h∈I πσ-i (h) ∑z∈Z πσ (h, z)ui(z).

For any action a ∈ A(I), the counterfactual value of an action a is uσi (I, a) = ∑h∈I πσ-i (h) ∑z∈Z πσ (h · a, z)ui(z). The instantaneous regret for action a in information set I on iteration t is rt (I, a) = uσt P (I) (I, a) - uσt P(I) (I). The cumulative regret for action a in I on iteration T is RT (I, a) = ∑Tt=1 rt (I, a). In CFR, players use Regret Matching to pick a distribution over actions in an information set in proportion to the positive cumulative regret on those actions. Formally, on iteration T +1, player i selects actions a ∈ A(I) according to probability

where RT+(I, a) = max(RT (I, a), 0) because we often mostly concern about cumulative regret when it is positive. If a player plays according to CFR in every iteration, then on iteration T , RT (I) ≤ ∆i√|Ai|√T where ∆i = maxz ui(z)- minz ui(z) is the range of utility of player i. Moreover, RT i ≤ ∑I∈Ii RT (I) ≤ |Ii|∆i√|Ai|√T. Therefore, as T → ∞, RT i T → 0. In two-player zero-sum games, if both players' average regret RT i T ≤ ϵ, then their average strategies (σT1 , σT2 ) form a 2ϵ-equilibrium [Waugh et al., 2009].

To solve large games effectively, some sampling-based CFR algorithms are proposed, such as external sampling, outcome sampling [Lanctot et al., 2009], probe sampling [Gibson et al., 2012] and other reduce variance sampling algorithms [Schmid et al., 2019; Steinberger et al., 2020]. External sampling algorithm has the lowest variance. However, it runs slowly because it traverses all actions of one player every iteration. Although outcome sampling algorithm runs faster than external sampling algorithm, it has large variance which influences the convergence rate. Compared to outcome sampling algorithm, probe sampling algorithm attempts to reduce variance by replacing "zeroed-out" counterfactual values of non-sampled actions with closer estimates of the true counterfactual values. In this paper, we adopt the probe sampling algorithm to traverse the game tree to collect regret value data.

3 Strategy Representation

In this paper, we focus on solving the Team-Adversary Games in which a team of agents plays against an adversary and all agents share one utility function. Note that the team's joint action space grows exponentially with the number of team players. Thus, it is impractical to solve this type of games with existing approaches due to the large action space. To address this problem, we propose a novel strategy representation, which significantly reduces the strategy space.

3.1 Individual Strategy Representation

In this section, we introduce a new strategy representation to denote the team's joint action strategy using the individual action strategies of all the team players. Different from the exponential combinatorial action space, the new individual action space of all the agents is linear with the number of agents. It is worth noting that all agents share the same history of the team T, i.e., the player function can be extended as P (h) = T = {1, 2, 3, ..., n}. In other words, all the agents share the same information sets of the team T. Therefore, the new strategy representation of the team is defined as fT = (σ1, σ2, ..., σn), where σi is agent i's strategy which maps each information set of player T to a probability distribution over agent i's action space ATi . For clarity, we call this new representation as individual strategy representation and denote the old team strategy representation by joint strategy representation. Given a strategy profile σ = (σV, fT) = (σV, σ1, ..., σn), the expected payoff of every agents is the same one ui(σ) = ∑h∈Z uT(h)πσ (h). πσ (h) is the reaching probability of history h if players choose actions according to σ which means that each team agent i chooses its action according to its strategy σi independently.

3.2 Strategy Consistency

Despite that the individual strategy representation reduces the search space efficiently, it cannot represent all join action strategy space. To clarify the difference between these two strategy representations, we first propose a consistency relationship between the two strategy representations which can be defined as

where σT(·) and σi(·) are the probability of a joint action and the probability of an individual action, respectively. In short, the joint strategy representation can be decomposed into the individual strategy representation. Note that the consistency relationship divides the whole joint action space S into two parts S1, S2 (Fig. 1). We set the strategy space of adversary as SV and (S, SV ) forms a two-player zero-sum game. Under our new strategy representation, the strategy space of the team becomes S1, and (S1, SV ) forms a two-player zero-sum game with the consistency relationship holds which is the game we focus on in this paper. The difference between these two games is that in game (S1, SV ), each team's joint strategy can be decomposed into the agents' individual strategies. Obviously, some joint strategies cannot be decomposed (S2). For example, a joint action strategy σ = (0.5, 0, 0, 0.5) is based on the joint action set {(a1, b1), (a1, b2), (a2, b1), (a2, b2)}. We cannot get the corresponding individual strategy representation following Eq. (1). Therefore, if the team's NE strategy of (S, SV ) is in the strategy space S1, the NE of (S1, SV ) equals the NE of (S, SV ) (See Theorem 1). Otherwise, the team's NE strategy of (S1, SV ) is a special team-maxmin equilibrium strategy that can be decomposed into individual strategy which is different from the NE of (S, SV ). In this case, the team may lose some utility after reducing strategy space since the utility of the team's joint strategy is always not lower than the utility of the team's strategy which can be decomposed. However, experimental results show that solving the game (S1, SV ) can get good strategies faster than solving the large game (S, SV ). The reason could be that the exponential action space influences the computing process of the join action strategy significantly.

Theorem 1. Under the new strategy representation, the Nash Equilibrium strategy profile between the adversary and the team keeps unchanged if Eq. (1) holds for the team's Nash equilibrium strategy. 1

4 CFR-MIX

Now we introduce a novel algorithm CFR-MIX to compute an NE for the Team-Adversary game with strategy consistency (S1, SV ). Firstly, we introduce the consistency relationship between cumulative regret values which is transformed from Eq. (1). Secondly, a novel decomposition method over cumulative regret values is proposed based on the consistency relationship. Then, we introduce our algorithm CFR-MIX in which the decomposition method is implemented by a mixing layer. Finally, we provide the theoretical analysis.

1 The complete proof is in https://arxiv.org/pdf/2105.08440.pdf

4.1 Regret Consistency

For extensive-form games, one of the most popular algorithms to compute NEs is CFR-based algorithm which leverages regret-matching to compute strategy according to cumulative regret values. In other words, the probability of each action is related to the cumulative regret value of the action. Therefore, to compute the individual strategy for each agent, we need to know the cumulative regret values of its actions explicitly. However, all the agents share the same team utility function and we can only get the regret values of joint actions. To this end, we propose a decomposition method over cumulative regret values. Before describing the decomposition method, we first transform the consistency relationship between strategies into the consistency relationship between cumulative regret values which can be defined as follows:

where πi(·) and πT(·) are the probabilities of individual action and joint action, i.e., πi(R(I, a)) = σi(I, a). a = (a1, ..., an) is the joint action composed by every agent's action. Rtot and Ri are the cumulative regret values of a joint action and an individual action, respectively. Since these probabilities are computed using regret-matching based on cumulative regret value, we can reformulate this consistency relationship as

when ∑∀a′ Rtot(I, a′ )+ > 0 and ∑b∈Ai(I) Ri(I, b)+ > 0. If ∑∀a′ Rtot(I, a′ )+ ≤ 0, the cumulative regret values of individual actions need to satisfy: ∑b∈Ai(I) Ri(I, b)+ ≤ 0, ∀i ∈ {1, ..n}. The consistency relationship guarantees that the probability of a joint action equals the product of the probabilities of all individual actions selected by each player.

4.2 Product-FormDecomposition

To guarantee these consistency relationships (Eqs. (1-3)), we propose a product-form decomposition method over cumulative regret values which can be defined as follows:

Here, we set Rtot = 0 if Rtot ≤ 0 following the setting of regret-matching+ [Tammelin et al., 2015] which is a regret-minimizing algorithm that operates very similarly to regret-matching. Compare with the regret matching which ignores actions that have an cumulative negative regret, regretmatching+ actively resets any cumulative negative regret back to zero. In the remaining paper, we consider that all cumulative regret values are non-negative.

Theorem 2. If product-form decomposition (Eq. (4)) holds, the consistency relationship between the joint action strategy and the individual strategy (Eq. (1)) can be guaranteed.

These equations are derived by the regret matching+ and product-form decomposition equation.

The above derivation is following the rules of polynomial multiplication and product-form decomposition equation. Therefore, the Eq. (1) holds.

4.3 Mixing Layer

This section introduces our algorithm, CFR-MIX, which employs a mixing layer to implement the product-form decomposition under the Double Neural CFR framework. The reasons that we do not implement decomposition in tabular CFR framework are described as follows. If we use tabular CFR to compute every cumulative regret value of individual action according to Eq. (4), we will get a nonlinear equation which is difficult to be solved efficiently. For example, in a Team-Adversary Game, there are two agents R = {1, 2} in the team. At an information set IT, agent 1 has two actions {a11, a12} and agent 2 has two actions {a21, a22}. We only know the cumulative regret values of all joint actions Rtot(I, a), where a ∈ {(a11, a21), (a11, a22), (a12, a21), (a12, a22)}. Then we need to compute the cumulative regret value of each individual action following the equations:

Solving the above equations is a resource intensive task, especially when the game has a large number of agents. Therefore, we adopt to combine CFR with deep neural networks and utilize the great capabilities of neural networks in function approximation properties (e.g., Double Neural CFR).

Our CFR-MIX algorithm is built on the Double Neural CFR framework, considering it can represent cumulative regret explicitly. Specifically, CFR-MIX uses the Probe sampling algorithm to traverse the game tree to collect training data (the data of cumulative regret values and strategies). In the sampling process, when it turns the team player to act, every agent plays according to its strategy and composes their strategies into the joint action strategy which is used to compute regret values only. Because all agents share one team utility function, it computes regret values for all joint actions based on the joint action strategy and joint action values. Then, CFR-MIX trains one cumulative regret value network and one average strategy network for each player.

The key to our method is the new cumulative regret network for the team which is shown in Fig. 2. To decompose the global cumulative regret values of joint actions, we design a mixing layer as a product operation on the cumulative regret values of all individual actions. The Agent network takes the information sets, agent i's observations and agent i's available actions as input and outputs the cumulative regret value of the agent i's actions. The mixing layer takes all the outputs of the Agent network as input and outputs the cumulative regret value of the corresponding joint action. In this way, the mixing layer guarantees that the consistency between cumulative regret values of individual action and joint action. Therefore, the mixing layer can also guarantee the strategy consistency relationship. When training this cumulative regret network, we use the cumulative regret values of joint actions which are the sum of: (1) the regret values obtained from the sampling process and (2) the estimated cumulative regret values obtained from the cumulative regret network in the last iteration.

To get the individual strategy of each agent, we only use the Agent network to estimate the cumulative regret value for each agent's action and compute the agent's strategy using regret-matching+ based on the estimated cumulative regret value. Therefore, CFR-MIX only needs to traverse the action spaces of all the agents which are linear with the number of agents. On the contrary, to get the joint strategy, Double Neural CFR needs to traverse the whole joint action space which is exponential with the number of agents. Furthermore, in CFR-MIX, we adopt the parameter sharing technique which means that all agents share the same Agent network. The parameter sharing can reduce the parameters and improve the performance significantly. For the average strategy network, we also only use one network for all agents. The training data of the strategy network are all agents' strategies. However, in the Double Neural CFR algorithm, the training data of the average strategy network are the team strategies defined over all the joint actions.

4.4 Convergence Analysis

Recall that we focus on a subset of joint action strategy space which can be decomposed into individual action strategies.

Therefore, we compute a new equilibrium of game (S1, SV ) with proposed CFR-MIX and provide a bound of regret under mild conditions based on Deep CFR [Brown et al., 2019].

Theorem 3. Let T denote the number of CFR-MIX iterations, |A| the maximum number of actions at any infoset and K the number of traversals per iteration. Let LtR be the average MSE loss for Rp(I, a|θt ) on a sample in Mr,p at iteration t, and let LtR∗ be the minimum loss achievable for any function R. Let LtR -LtR∗ ≤ ϵL. If the value memories are sufficiently large and Eq. (4) holds, then with probability 1 - ρ total regret of player p at time T is bounded by

As T → ∞, the average regret RT p T is bounded by 4|Ip|√|A|∆ϵL with high probability.

Proof. Compared with the proof of Deep CFR, the only difference is that the agent in the team plays the individual strategy instead of the joint action strategy. The establishment of Eq. (4) guarantees the consistency relationship of strategies (Eq. (1)) which means that under the new strategy representation, the Nash Equilibrium keeps unchanged (Theorem 1). Therefore, the regret bound for the new representation is same as the joint strategy representation. 2

5 Evaluation

To verify the effectiveness of CFR-MIX, we deploy Double Neural CFR and Deep CFR as baselines and compare these baselines with CFR-MIX and Deep CFR with mixing layer. We also compare CFR-MIX with the algorithm that every agent learns its strategy independently (Individual Deep CFR). Furthermore, to verify the effectiveness of the parameter sharing technique, we evaluate the performance of CFRMIX with and without parameter sharing. Without loss of generality, we select two different domain games. Experiments are performed on a server with a 10 core 3.3GHz Intel i9-9820X CPU and a NVIDIA RTX 2080 Ti GPU.

5.1 Goofspiel

Goofspiel [Ross, 1971] is a bidding card game where players have a hand of cards numbered 1 to K, and take turns secretly bidding on the top point-valued card in a point card stack using the cards in their hands (Fig. 3(a)). In each bidding process, the player with the higher point of the card will get the point of the top point-valued card. Finally, the player with the highest total points wins. Here, we use an imperfect informational version [Lis`y et al., 2015; Brown and Sandholm, 2019] which is widely used: players can only observe the results of each bid while cannot know the cards used to bid. Meanwhile, we consider the special two-player case in which several players form a team to play against an opponent. If one of the team players wins, the whole team wins. Here, as shown in Fig. 3, we use different number of cards (6C, 10C and 13C) and team players (4P and 6P). Note that Double Neural CFR + MIX refers to CFR- MIX and Deep CFR + MIX denotes the Deep CFR algorithm with mixing layer. We can see that the algorithms with mixing layer outperform the others in 6C4P6R game. In 10C6P and 13C6P games, the joint action space is very large at some information sets (about 106 and 136 ), and only CFR-MIX can get satisfactory strategies in a limited time.

2 The complete proof is in https://arxiv.org/pdf/2105.08440.pdf

5.2 Pursuit-Evasion game

Pursuit-evasion games appear in many scenarios in robotics and security domains, where a team of pursuers aims to capture the evader, while the evader aims for the opposite [Hor´ak and Boˇsansk`y, 2016]. Here we consider a more realistic version of the pursuit-evasion game, NEtwork purSuiT game (NEST) [Zhang et al., 2017; Zhang et al., 2019], which takes the tracking devices into consideration. Thus, pursuers can get the real-time location of the evader. We set a limited number of steps in which if the evader cannot escape to the exits or at least one pursuer catches the evader, the game ends and the defender gets a unit reward. Otherwise, the defender gets a zero payoff. Our experiments are conducted on grid networks in which each node connects to its neighbors. We choose some nodes on the edges as exits. The initial locations of the evader and all pursuers are chosen randomly. As shown in Fig. 4(a-c), the algorithms with the mixing layer outperform other algorithms. In Fig. 4(a), we also compare our algorithm with the algorithm that every pursuer uses Double Neural CFR independently. The result shows that Individual Double Neural CFR cannot converge to NE in a limited time. To verify the effectiveness of parameter sharing, we conduct an ablation experiment in which every pursuer uses different Agent neural networks. The results in Fig. 4(b) indicate that CFR-MIX with parameter sharing performs better than that without parameter sharing (PS). In Fig. 4(c), we only compare CFR-MIX with Double Neural CFR because Deep CFR is time-consuming and needs large memory. We can see that CFR-MIX still exhibits better performance. In complicated games with large number of pursuers (Fig. 4(d), although CFR-MIX does not converge in a limited time, it still shows the tendency of growth which means that CFRMIX get a better strategy than random strategy (initial strategy). In conclusion, for different domains games, CFR-MIX outperforms other algorithms significantly. In large games with many players, CFR-MIX can still get some satisfactory results within a limited time while other algorithms cannot solve these large games due to the combinatorial action space.

6 Conclusion

In this paper, we propose a novel framework to solve the Team-Adversary Games with the combinatorial action space. Instead of using the joint action strategy representation, we represent the team's strategy with a novel individual strategy representation to reduce the strategy space. To maintain the cooperation among team players, we define a consistency relationship between these two strategy representations. Moreover, to compute the equilibrium with new strategy representation, we transform the consistency relationship between strategies to the consistency relationship between cumulative regret values. Finally, under the guarantee of these consistency, we propose the CFR-MIX framework which employs a mixing layer to implement the novel decomposition method over cumulative regret values. Experimental results show that our algorithm significantly outperforms other state-of-the-art CFR-based algorithms.

Acknowledgments

This research is partially supported by Singtel Cognitive and Artificial Intelligence Lab for Enterprises (SCALE@NTU), which is a collaboration between Singapore Telecommunications Limited (Singtel) and Nanyang Technological University (NTU) that is funded by the Singapore Government through the Industry Alignment Fund - Industry Collaboration Projects Grant.