Year: 2021

Abstract:
The deep policy gradient method has demonstrated promising results in many largescale games, where the agent learns purely from its own experience. Yet, policy gradient methods suffer convergence problems to a Nash Equilibrium (NE) in multiagent situations. Counterfactual regret minimization (CFR) has a convergence guarantee to a NE in 2-player zero-sum games, but it usually needs domain-specific abstractions to deal with large-scale games. Inheriting merits from both methods, in this paper we extend the actor-critic algorithm framework in deep reinforcement learning to tackle a large-scale 2-player zero-sum imperfect-information game, 1-on-1 Mahjong, whose information set size and game length are much larger than poker. The proposed algorithm, named Actor-Critic Hedge (ACH), modifies the policy optimization objective from originally maximizing the discounted returns to minimizing a type of weighted cumulative counterfactual regrets. This modification is achieved by approximating the regrets via a deep neural network and minimizing the regrets via generating self-play strategies using Hedge. ACH is theoretically justified as it is derived from a neural-based weighted CFR, for which we prove the convergence to a NE under certain conditions. Experimental results on the proposed 1-on-1 Mahjong benchmark and benchmarks from the literature demonstrate that ACH outperforms related state-of-the-art methods. Also, the agent obtained by ACH defeats a human champion in 1-on-1 Mahjong.

heading: 1 INTRODUCTION
text: Policy gradient methods using deep neural networks as policy and value approximators have been successfully applied to many large-scale games (Berner et al., 2019; Vinyals et al., 2019; Ye et al., 2020). Usually, a score function representing the discounted returns is maximized by the policy, i.e., the actor. In the meantime, a value function, known as the critic, is learned to guide the directions and magnitudes of the policy gradients. This type of actor-critic methods are efficiently scalable with regard to the game size and the amount of computational resources. However, as pointed out in Srinivasan et al. (2018) and Hennes et al. (2020), policy gradient methods have no convergence guarantee to optimal solutions in competitive Imperfect-Information Games (IIGs). The main reason is that the policy gradient theorem (Sutton et al., 1999) is established within the single agent situation, where the environment is Markovian. However, learning becomes non-stationary and non-Markovian when multiple agents learn simultaneously in a competitive environment.
An optimal solution to a 2-player zero-sum IIG usually refers to a Nash Equilibrium (NE), where no player could improve by unilaterally deviating to a different policy. Tremendous progress in computing such optimal solutions has been made by a family of tabular methods: Counterfactual Regret Minimization (CFR) (Zinkevich et al., 2008). CFR is a type of iterative self-play algorithm based on regret minimization, and it guarantees to converge to a NE with regard to the average policy in 2-player zero-sum IIGs. A game model is required in CFR to sample many if not all actions from a state during self-play. To handle large-scale IIGs with CFR, abstractions1, applied to either the action space or the state space, are usually employed to reduce the game to a manageable size (Moravčík et al., 2017; Brown & Sandholm, 2018; 2019). However, abstractions are domain specific (Waugh et al., 2009; Johanson et al., 2013; Ganzfried & Sandholm, 2014). Besides, some large-scale IIGs may be inherently difficult to be abstracted.
1DeepStack (Moravčík et al., 2017) employs sparse lookahead trees, much like action abstraction.
In this paper, we investigate a large-scale IIG, Mahjong. Li et al. (2020b) has recently developed a strong 4-player Mahjong AI based on supervised learning and traditional Reinforcement Learning (RL). In comparison, we study Mahjong from a game-theoretic perspective, i.e., aiming for a NE. We focus on a 2-player (1-on-1) zero-sum Mahjong game, whose information set size and game length are much larger than poker2. We are interested in methods using only trajectory samples to learn, as it is infeasible to consistently sample multiple actions for each state in game trees of large-scale IIGs with long episodes. Also, we employ deep neural networks to generalize across states, since the state abstraction in 1-on-1 Mahjong is not as straightforward as in poker, which is explained in the Appendix A.2. To summarize, we make the following contributions.
• Inheriting the scalability of deep RL methods and the convergence property of CFR, we develop a new actor-critic algorithm, named Actor-Critic Hedge (ACH), for approaching a NE in largescale 2-player zero-sum IIGs, such as 1-on-1 Mahjong. ACH employs a deep neural network to approximate a type of weighted cumulative counterfactual regrets. In the meantime, ACH minimizes the regrets via generating self-play strategies using Hedge (Freund & Schapire, 1997).
• We introduce a Neural-based Weighted CFR (NW-CFR), for which we prove that the exploitability of the average strategy decreases at the rate of O(T−1/2) +O(1), where T denotes the number of iterations. ACH is a practical implementation of NW-CFR and hence theoretically justified.
• To facilitate research on large-scale 2-player zero-sum IIGs and Mahjong, we propose a 1-on-1 Mahjong benchmark. The corresponding game enjoys a large population in online games.
• We build a 1-on-1 Mahjong agent, named JueJong, based on ACH. In an initial evaluation against human players including a Mahjong champion3, JueJong demonstrates superior performance.

heading: 2 NOTATIONS AND BACKGROUND
text: In this section, we introduce notations in the context of IIGs and NE. Related background on RL (focusing on policy gradient methods) and CFR are briefly described.

heading: 2.1 IMPERFECT-INFORMATION GAMES AND NASH EQUILIBRIUM
text: An IIG is usually represented in an extensive-form, i.e., a game tree. A node (history) h ∈ H in the tree represents all information of the current situation. Given a history h, P : H → P ∪ {c} maps h to the unique player p ∈ P who acts at h or the chance player c, where the chance player is responsible for taking actions for random events. When P (h) ∈ P , the player P (h) has to take an action a ∈ A. We use A(h) to represent the set of legal actions of P (h). The set of terminal nodes is denoted as Z . At each z ∈ Z , there is a payoff up : Z → R for each player p ∈ P . In this paper, we focus on 2-player zero-sum games, where P = {0, 1} and u0(z) + u1(z) = 0 for each z ∈ Z . For either player p, the set of historiesH is partitioned into information sets (infosets). We denote the set of infosets for player p as Ip and an infoset in Ip as Ip. Two histories h, h′ ∈ H are in the same infoset if and only if h and h′ are indistinguishable from the perspective of player p. As a result, a player p’s strategy πp maps an infoset to a probability distribution over legal actions. For the same reason, we define A(Ip) = A(h),∀h ∈ Ip and P (Ip) = P (h),∀h ∈ Ip. A strategy profile π is simply a tuple of strategies (πp, π−p), where π−p represents the player p’s opponent strategy. The expected payoff for player p under π is then denoted as up(πp, π−p). We use ∆(I) to denote the range of payoffs reachable from a history h in infoset I . Let ∆ = maxI∈Ip,p∈P ∆(I). f
π(h) denotes the joint reaching probability of h under π. fπp (h) is the contribution of player p to f
π(h), and fπ−p(h) is the contribution of the opponent and chance: fπ(h) = fπp (h)f π −p(h). We focus on the perfect-recall setting, where each player recalls the sequence of their own infosets reached. We define fπp (Ip) = fπp (h),∀h ∈ Ip, fπ−p(Ip) = ∑ h∈Ip f π −p(h), and f π(Ip) = ∑ h∈Ip f π(h) = fπp (Ip)f π −p(Ip).
A best response BR(π−p) to π−p is a player p’s strategy, which satisfies up(BR(π−p), π−p) = maxπ′p up(π ′ p, π−p). A NE is a strategy profile π
∗, where each player plays a best response to the other: up(π∗p , π ∗ −p) = maxπ′p up(π ′ p, π ∗ −p), ∀p ∈ P . The exploitability of a player’s strategy,
2Without specification, we mean Heads-up No-Limit Texas Hold’em in this paper. 3Haihua Cheng is the Competition Mahjong champion of 2014 World Mahjong Master Tournament, 2018
Tencent Mahjong Tournament, and 2019 Tencent Mahjong Tournament.
denoted as e(πp), measures the performance gap between πp and a NE strategy π∗p: e(πp) = up(π ∗ p, π ∗ −p)− up(πp, BR(πp)). The average exploitability is = 1|P| ∑ p∈P e(πp).

heading: 2.2 REINFORCEMENT LEARNING AND POLICY GRADIENT METHODS
text: RL usually assumes a Markov decision process, where the agent selects an action ai from the action set A(si) in state si ∈ S4 at each time step i. The agent then receives a reward ri from the environment and transitions to a new state si+1. The objective in RL is to learn a policy that maximizes the expected discounted returns, i.e., the state value, starting from any state s: V π(s) = Eπ[ ∑∞ j=i γ j−irj |si = s] = Eπ[G], with the discount factor γ ∈ [0, 1).
A large family of methods in RL belong to policy gradient methods, in which the parameters θ of policy π(a|s; θ) are updated by performing gradient ascent directly on Eπθ [G]. One early example is the standard REINFORCE algorithm (Williams, 1992) that updates θ in the direction ∇θ log π(a|s; θ)G, which is an unbiased estimate of ∇θEπθ [G]. To further reduce the variance of the gradient, an action-independent baseline is often subtracted from G: ∇θ log π(a|s; θ)[G−B(s)]. A recent policy gradient method, named Advantage Actor-Critic (A2C) (Mnih et al., 2016), learns a parameterized value function as the baseline: B(s) = V πθ (s;w), where w often shares some parameters with θ. Moreover, the value G−B(s) is replaced in A2C with the estimated advantage of action a in state s: A(s, a) = Q(s, a)− V (s). Q(s, a) is usually estimated using sampled rewards and predicted values of future states. A2C updates parameters θ and w in a synchronous manner, while its asynchronous version is Asynchronous Advantage Actor-Critic (A3C) (Mnih et al., 2016).
In an asynchronous training environment, the behavioral policy is usually different from the learning policy. Proximal Policy Optimization (PPO) (Schulman et al., 2017) takes this discrepancy into account by multiplying A2C gradient with an importance ratio r(a|s; θ) = π(a|s; θ)/π(a|s; θold), which results in r(a|s; θ)∇θ log π(a|s; θ)A(s, a) = ∇θr(a|s; θ)A(s, a). Furthermore, PPO constrains the KL divergence between the learning policy πθ and the old behavioral policy πθold by clipping the ratio to a small interval around 1.0.

heading: 2.3 COUNTERFACTUAL REGRET MINIMIZATION
text: CFR is an iterative algorithm that minimizes the total regret of strategies by minimizing the cumulative counterfactual regrets in every state (infoset). The cumulative counterfactual regret of an action a in state s is defined as Rct(s, a) = ∑t k=1 r c k(s, a), where r c k(s, a) denotes the instantaneous counterfactual regret of action a in state s at iteration k. rct (s, a) is equal to f πt −p(s)A
πt(s, a) (as proven in Srinivasan et al. (2018)), where Aπt(s, a) is the advantage function of player p = P (s) at state s as defined in traditional RL. Intuitively, rct (s, a) represents how regretful player p is that he does not select the action a in state s at iteration t. The term fπt−p(s) = ∑ h∈s f πt −p(h) is needed here to reflect the fact that the reaching of state s is also controlled by the opponent −p. To minimize the counterfactual regrets, a regret minimizer is utilized in each state at each iteration, generating a series of local policies π1(s), . . . , πt(s). Once πt is obtained, rct (s, a) is generated by a model-based game tree traversing using πt, and Rct(s, a) is updated accordingly: R c t(s, a) = R c t−1(s, a) + r c t (s, a).
Define the total regret of player p as RcT = maxπ′ ∑T t=1 (up(π
′, π−p,t)− up(πp,t, π−p,t)). It is proven in Zinkevich et al. (2008) that RcT ≤ ∑ s∈S [R c T (s)]
+, where [·]+ = max{·, 0} and RcT (s) = maxa∈A(s)R c T (s, a). As a result, the total regret can be minimized by minimizing
the cumulative counterfactual regrets at each state. Moreover, the average strategy π̄T (a|s) =∑ t∈T f πt p (s)πt(a|s)/ ∑ t∈T f πt p (s) converges to a NE if R c T grows sub-linearly with T (Zinkevich et al., 2008). There are two commonly used regret minimizers: Regret Matching (RM) and Hedge (Cesa-Bianchi & Lugosi, 2006). In RM, a player selects an action with probability in proportion to its positive cumulative counterfactual regret. In Hedge, the strategy πt+1(a|s) is decided according to:
πt+1(a|s) = eη(s)R c t (s,a)∑
a′ e η(s)Rct (s,a
′) . (1)
4We use state s and infoset Ip interchangeably in this paper.
If a player plays according to Hedge in state s and η(s) = √
8 log(|A(s)|)/(∆2(s)T ), thenRcT (s) ≤ ∆(s) √ log(|A(s)|)T/2 (Cesa-Bianchi & Lugosi, 2006). In other words, the total regret grows sub-linearly with T , and therefore the average strategy π̄T (a|s) converges to a NE.

heading: 3 THE MOTIVATION OF ACTOR-CRITIC HEDGE
text: In this section, we motivate ACH by introducing a new neural-based CFR algorithm, NW-CFR, which employs neural networks to generalize across states and relies on only trajectory samples for training. The key idea in NW-CFR is that a neural network (called the policy net) is used to approximate the expectation of the sum of sampled advantages Rat (s, a) := E[ ∑t k=1 Ã
πk(s, a)]. Ãπk(s, a) is set to Aπk(s, a) if s is visited at iteration k (given that only one trajectory is sampled at each iteration) and 0 otherwise. As a result, the expectation E[Ãπk(s, a)] depends on both the advantage Aπk(s, a) and the sampling strategy µk at iteration k.
At the beginning of iteration t, suppose Rat−1(s, a) is well approximated by the output y(a|s; θt−1) of the policy net, parameterized as θt−1, in NW-CFR. The strategy πt for iteration t is first obtained via Hedge, i.e., softmaxing on η(s)y(a|s; θt−1). The reason we use Hedge instead of RM is that softmaxing is shift-invariant, which may be more robust to the function approximation error compared to the threshold operation in RM. M trajectories are then sampled into the buffer Bv via self-play using the strategy profile πt = (πp,t, π−p,t). Those samples in Bv are used to train the action value net, parameterized as ω, by minimizing the squared loss: 12 [Q(s, a;ω)−G]
2, where G is the sampled return. Afterwards, another M trajectories are sampled into the buffer Bπ via self-play using another sampling strategy profile µt = (µp,t, π−p,t). We use an additional behavioral policy µp,t for player p for more flexibility in the convergence (more details are provided in the next section). The policy θ is then optimized according to the following squared loss function:
Lπ =
{∑ s ∑ a{y(a|s; θ)− [y(a|s; θt−1) + 1 M ∑M i=1 1s∈τiA
πt(s, a)]}2 if s ∈ Bπ,∑ s ∑ a{y(a|s; θ)− [y(a|s; θt−1) + 0]}2 otherwise,
(2)
where τi is the ith sampled trajectory in Bπ. The next iteration of NW-CFR begins after the policy training finishes. The pseudocode of NW-CFR is given in Algorithm 1. Note that we present NWCFR from the perspective of player p, and the same procedure applies to player −p. NW-CFR runs concurrently for both players and synchronizes at the beginning of each iteration.
A potential benefit of training on the sampled advantage (as done in NW-CFR) over the sampled counterfactual regret (as done in Brown et al. (2019), Li et al. (2020a), and Steinberger et al. (2020)) is that the variance of the sampled advantage could be lower. Given that rck(s, a) = f πk −p(s)A πk(s, a) (Srinivasan et al., 2018), a sampled counterfactual regret r̃ck(s, a) is equal to f πk −p(s) fµk (s) Ã πk(s, a) = [fµkp (s)] −1Ãπk(s, a), where [fµkp (s)]
−1 is an importance sampling ratio. As a result, the variance of the sampled counterfactual regret could be much higher than that of the sampled advantage, which may have a large influence on the performance when neural network function approximation is used with only trajectory samples. This influence is magnified in games with long episodes.

heading: 4 THEORETICAL PROPERTIES OF NW-CFR
text: In this section, we prove the convergence of NW-CFR to an approximate NE. To this end, we first deduce that the policy target in NW-CFR is Rat (s, a), which is a type of weighted cumulative counterfactual regret. We then define a new family of CFR algorithms: weighted CFR. Finally, we show that NW-CFR is equivalent to a type of weighted CFR with Hedge under certain conditions. The convergence properties of weighted CFR with Hedge and hence NW-CFR are proven accordingly.
We can rewrite the NW-CFR policy loss (in Equation 2) at iteration t as Lπ = ∑ s∈S ∑ a{y(a|s; θ)−
[y(a|s; θt−1) + 1M ∑M i=1 1s∈τiA
πt(s, a)]}2. In other words, the target of y(a|s; θ) at iteration t is y(a|s; θt−1) + 1M ∑M i=1 1s∈τiA πt(s, a), whose expectation is
Eτk,i∼(µp,k,π−p,k)
[ t∑
k=1 M∑ i=1 1 M 1s∈τk,iA πk(s, a) ] = Eτk∼(µp,k,π−p,k) [ t∑ k=1 Ãπk(s, a) ] = Rat (s, a).
Algorithm 1: Neural-based Weighted CFR Function Neural-based Weighted CFR(p,N,M, θ, ω):
ω0 ← ω, θ0 ← θ. for t← 1 to N do
# Obtain the policy: πt ← Softmax(η(s)y(a|s; θt−1)). # Train the action value net: Reset Bv ← ∅. for i← 1 to M do
τi ∼ SelfPlay(πp,t, π−p,t), Bv ← Bv ∪ τi Train ω on the loss E(s,a,G)∼Bv{ 12 [Q(s, a;ω)−G]
2} ωt ← ω # Train the policy net: Reset Bπ ← ∅. for i← 1 to M do
τi ∼ SelfPlay(µp,t, π−p,t), Bπ ← Bπ ∪ τi Estimate Aπ t (s, a),∀a ∈ A(s),∀s ∈ Bπ as Q(s, a;ωt)− ∑ b πt(b|s)Q(s, b;ωt). Sum aggregate advantage Aπ t
(s, a) in Bπ by state s. Train θ on the loss Es∼S{Lπ}, where Lπ is defined in Equation 2. θt ← θ. # Save θt to a strategy buffer.
Also, Eτk∼(µp,k,π−p,k)1s∈τkAπk(s, a) = fµkp (s)f πk −p(s)A πk(s, a), where fµkp (s)f πk −p(s) is the reaching probability of state s at iteration k. Therefore, Rat (s, a) = ∑t k=1 f µk p (s)f πk −p(s)A
πk(s, a). Since rck(s, a) = f πk −p(s)A πk(s, a) (Srinivasan et al., 2018), we have Rat (s, a) = ∑t k=1 f µk p (s)r c k(s, a).
As a result, Rat (s, a) can be viewed as a type of weighted cumulative counterfactual regret that weighs each instantaneous regret with fµkp (s). Without loss of generality, we define a new family of CFR algorithms, weighted CFR, below. Afterwards, we present Theorem 1.
Definition 1. Weighted CFR follows the same procedure as the original CFR, except that the instantaneous regret rct (s, a) is weighted by some weight wt(s), wt(s) > 0 and ∑∞ t=0 wt(s) =∞. The original CFR is a type of weighted CFR with wt(s) = 1.0.
Theorem 1. NW-CFR is equivalent to a type of weighted CFR with Hedge whenwt(s) = fµtp (s) > 0, given that enough trajectories are sampled and y(a|s; θt) is sufficiently close to Rat (s, a). Further, if η(s) = √ 8 ln |A(s)|/{[wh(s)]2∆2(s)T} and wt(s) = fµtp (s) ∈ [wl(s), wh(s)] ⊂ (0, 1], t = 1, . . . , T , the average strategy π5 of the corresponding weighted CFR with Hedge and equivalently NW-CFR with πp(a|s) = ∑T t=1 [ fπtp (s)πt(a|s) ] / ∑T t=1 f πt p (s),∀p ∈ P , converges to a -Nash equilibrium after T iterations, where
= |S|∆ √ 1
2T ln |A|+ |A|∆ ∑ s∈S (wh(s)− wl(s)) wh(s) . (3)
In Theorem 1, we proved that the exploitability of NW-CFR is bounded by when y(a|s; θt) is sufficiently close to Rat (s, a). There are two terms in the bound . The first term converges to zero at the rate of O(T−1/2), and the second term is O(1), which is weighted by the sum of the normalized range of the weights ∑ s∈S (wh(s)− wl(s))/wh(s). However, it is possible to reduce the second term to an arbitrarily small value via tightening the range of fµtp (s), which is experimentally demonstrated in the Appendix D.
Corollary 1. If the behavioral policy µp,t for each player p ∈ P is constant across iterations, and fµtp (s) > 0,∀s ∈ S, t > 0, NW-CFR is equivalent to CFR with Hedge when y(a|s; θt) is sufficiently close to Rat (s, a).
5Given πp,t at each iteration, we could obtain πp using the techniques introduced in Steinberger (2019).
As shown in Corollary 1, when the behavioral policy µp,t for each player p ∈ P is time-invariant, i.e., wh(s) = fµtp (s) = wl(s),∀s ∈ S, t > 0, the second term in disappears, and CFR with Hedge is recovered. All the proofs are given in the Appendix C.

heading: 5 ACH: A PRACTICAL IMPLEMENTATION OF NW-CFR
text: When applying NW-CFR to large-scale problems, two practical issues need to be addressed:
The average policy. Theorem 1 and Corollary 1 state the convergence property of the average policy in NW-CFR. Yet, as pointed out in Srinivasan et al. (2018), Hennes et al. (2020), and Perolat et al. (2021), obtaining the average policy with deep neural nets in large-scale games is inherently difficult, due to either the computation or the memory demand. Alternatively, we could employ some additional technique to hopefully induce the current policy convergence towards a NE. Srinivasan et al. (2018) and Hennes et al. (2020) handled this by adding an entropy regularization to the current policy training, which is, to some extent, theoretically justified later in Perolat et al. (2021).
Training on states not sampled. Theoretically, in order to optimize Equation 2, we need to collect both sampled and non-sampled states. Optimizing with only sampled states makes y(a|s; θt) a biased estimation of Rat (s, a). Yet, collecting non-sampled states may be intractable in large-scale games (Li et al., 2020a) or in situations where a perfect environment model is not available.
To strike a balance between theoretical soundness and practical efficiency, we provide a practical implementation of NW-CFR, which is called ACH. ACH adapts NW-CFR by training the current policy with an entropy regularization on only sampled states, without the calculation of the average policy. In order to utilize distributed clusters, ACH employs a framework of decoupled acting and learning, similar to IMPALA (Espeholt et al., 2018), trains the network with mini batches, and handles asynchronous training with the importance ratio clipping of PPO. The behavior policy µp,t is set to πp,t 6 in ACH. More details of ACH are presented in the Appendix E.

heading: 6 RELATED WORK
text: To obviate the need of abstractions, various neural forms of CFR methods have been developed. An early work of this direction is regression CFR (Waugh et al., 2015), which calculates weights for a number of hand-crafted features to approximate the regrets. Deep CFR (Brown et al., 2019) is similar to regression CFR but employs a neural network to approximate the regrets. Also, deep CFR traverses a part of the game tree using external sampling, in comparison to the full traversal of the game tree in regression CFR. Double neural CFR (Li et al., 2020a) is another method that approximates the regrets and the average policy using deep neural networks, where a novel robust sampling technique is developed. Both deep CFR and double neural CFR build on the tabular Monte Carlo CFR (MCCFR) (Lanctot et al., 2009), where either outcome sampling (sampling one action in a state) or external sampling (sampling all actions in a state) could be employed.
When dealing with games with long episodes, a necessity may be that only trajectory samples are allowed. To improve the learning performance with only trajectory samples, DREAM (Steinberger et al., 2020) adapts deep CFR by using a learned Q-baseline, which is inspired by the variance reduction techniques in tabular MCCFR (Schmid et al., 2019; Davis et al., 2020). Another recent work using only trajectory samples is ARMAC (Gruslys et al., 2020). By replaying through past policies and using a history-based critic, ARMAC predicts conditional advantages, based on which the policy for each iteration is generated. Other popular neural network based methods, which learn from trajectory samples and are inspired by game-theoretic approaches other than CFR, include neural fictitious self-play (Heinrich & Silver, 2016), policy space response oracles (Lanctot et al., 2017), and exploitability descent (Lockhart et al., 2019), all of which require to compute an approximate best response at each iteration. Such computation may be prohibitive in large-scale games.
The most related methods to ACH are Regret Policy Gradient (RPG) (Srinivasan et al., 2018) and Neural Replicator Dynamics (NeuRD) (Hennes et al., 2020), both of which employ the actor-critic framework and thus have similar computation and memory complexities as ACH.
6In a preliminary experiment presented in the Appendix F, we find that the performance of the current strategy in ACH (trained with an entropy regularization) is not sensitive to the choice of µp,t.
RPG minimizes a loss that is an upper bound on the regret after threshold, and the corresponding policy gradient is ∇RPGθ (s) = − ∑ a∇θ[Q(s, a;w) − ∑ b π(b|s; θ)Q(s, b;w)]+. However, RPG requires a l2 projection after every gradient step for the convergence to a NE, while such projection is not required in ACH. NeuRD is inspired by the replicator dynamics, a well studied model in evolutionary game theory (Gatti et al., 2013). The policy gradient in NeuRD is ∇NeuRDθ (s) = ∑ a[∇θy(a|s; θ)][Q(s, a;w) − ∑ b π(b|s)Q(s, b;w)], where y(a|s; θ) is the output of the policy net. There are important differences between ACH and NeuRD in how the algorithm is motivated and how the policy net at each iteration is optimized. Also, the convergence analysis was given only for the single-state, all-actions, tabular NeuRD (Hennes et al., 2020). Yet, we prove the convergence of NW-CFR, of which ACH is a practical implementation, in full extensive-form games.

heading: 7 EXPERIMENTAL STUDIES
text: We firstly introduce a 1-on-1 Mahjong benchmark, on which we compare ACH with related stateof-the-art methods of similar computation complexity: PPO, RPG, and NeuRD. Since our goal is to approximate a NE, the standard and default performance metric, exploitability, is employed. We approximate a lower bound on the exploitability of an agent (i.e., solution) by training a best response against it as suggested in Timbers et al. (2020) and Steinberger et al. (2020), because traversing the full game tree to compute the exact exploitability is intractable in such a large-scale game as 1-on-1 Mahjong. As a complement, head-to-head performance of different methods on 1-on-1 Mahjong is also presented. Moreover, the agent obtained by ACH is evaluated against practised Mahjong human players. To further validate the performance of ACH in IIGs other than 1-on-1 Mahjong, experimental results on a non-trivial poker game, i.e., heads-up Flop Hold’em Poker (FHP) (Brown et al., 2019) are presented. Also, deep CFR with outcome sampling (OS-DCFR) and DREAM are added to enable a more thorough comparison. Additional results on smaller benchmarks from OpenSpiel (Lanctot et al., 2019) are given in the Appendix G. Note that results are reported for the current policy in ACH, PPO, NeuRD, and RPG and the average policy in OS-DCFR and DREAM.

heading: 7.1 A 2-PLAYER ZERO-SUM MAHJONG BENCHMARK
text: Mahjong is a tile-based game that is played world wide with many regional variations, such as Japanese Riichi Mahjong and Competition Mahjong. Like poker, Mahjong is an IIG and is full of strategy, chance, and calculation. To facilitate Mahjong research from a game-theoretic perspective, we propose a 2-player zero-sum Mahjong benchmark7, whose game rules are similar to Competition Mahjong. The corresponding game, “2-player Mahjong Master”, is played by humans in Tencent mobile games. A full description of the game rules is in the Appendix A.1. Apart from being the first benchmark for the 1-on-1 Mahjong game, our benchmark has a larger infoset size and a longer game length, compared with existing poker benchmarks (Lanctot et al., 2019). The infoset size (i.e., the number of distinct histories in an infoset) in 1-on-1 Mahjong is around 1011, compared to 103 in poker. This is due to the fact that only two private cards are invisible in poker, while there are 13 invisible tiles in 1-on-1 Mahjong. In addition, players can decide up to about 40 sequential actions in 1-on-1 Mahjong, whereas most 1-on-1 poker games end within 10 steps. More details about the 1-on-1 Mahjong benchmark are given in the Appendix A.

heading: 7.2 RESULTS ON OUR 1-ON-1 MAHJONG BENCHMARK
text: All methods run in an asynchronous training platform with overall 800 CPUs, 3200 GB memory, and 8 M40 GPUs in the Ubuntu 16.04 operating system. Each method shares the same neural network architecture, a full description of which is given in the Appendix B. We performed a mild hyper-parameter search on PPO and shared the best setting for all methods. The advantage value is estimated by the Generalized Advantage Estimator (GAE(λ)) (Schulman et al., 2016) for all methods. An overview of the hyper-parameters is listed in the Appendix H.1.
Approximate Lower Bound Exploitability. To approximate a lower bound on the exploitability of the agents obtained by each method, we train a best response against each agent. The agent of each method is selected at the 1e6th training step. Note that the agent is fixed as a part of the 1-on-1 Mahjong environment when training the best response. We train the best response using PPO with
7Our benchmark and related algorithms will be open sourced.
the same hyper-parameters that were used to train the PPO agent8. During the training of the best response, we evaluate the best response every 500 training steps using 10, 000 head-to-head plays against each agent. According to the average scores each agent loses to its best response in Figure 1(a), we may conclude that ACH is significantly more difficult to exploit than other methods in the large-scale 1-on-1 Mahjong environment.
Head-to-Head Evaluation. We then compare the head-to-head performance of PPO, RPG, NeuRD, and ACH in the 1-on-1 Mahjong environment. First, we compare the training process of each method by evaluating each agent every 500 training steps against a common rule-based agent9 using 10, 000 head-to-head plays, the results of which are shown in Figure 1(b). As we can see, all methods beat the common rule-based agent significantly, while ACH has a clear advantage over other methods in terms of stability and final performance. The relatively slow convergence of RPG may due to the threshold operation on the advantage, which could reduce sample efficiency in large-scale IIGs. Second, the superior performance of ACH is further validated in head-to-head evaluations with other agents in Table 1, where all the agents are selected at the 1e6th training step. The agent of ACH wins all other agents by a significant margin.
Human Evaluation. We evaluate the agent, selected at the 1e6th training step, of ACH against human players. First, the agent, named JueJong, is roughly evaluated by playing over 7, 700 games against 157 practiced Mahjong players, where JueJong won an average of 4.56 scores per game. Second, we select the top 4 out of 157 players according to their performances against JueJong and play JueJong against the four players for 200 games each. As shown in Figure 2(a), the average winning scores of JueJong oscillate in the first 120 games but all plateau above 0 afterwards. More importantly, we evaluate JueJong against the Mahjong champion Haihua Cheng for 1, 000 games, as shown in Figure 2(b). After playing 1, 000 games, JueJong won the champion by a score of 0.82± 0.96 (mean ± standard deviation), with a p-value of 0.19 under one-tailed t-test. Hence, we may conclude that Haihua Cheng failed to exploit JueJong effectively within 1, 000 games.
8There exists the potential risk that parameters used in the self-play PPO might not work satisfactorily with the PPO as a best response.
9The rule-based agent is implemented such that it selects Hu, Ting, Kong, Chow, and Pong in descending priority whenever available and discards the tile that has the fewest neighbours.

heading: 7.3 RESULTS ON THE FHP BENCHMARK
text: We further evaluate ACH and compare it with OS-DCFR, DREAM, A2C10, RPG, and NeuRD on FHP. FHP is a simplified Heads-up Limit Texas Hold’em (HULH), which includes only the first two of the four bettings in HULH. It is a medium-sized game with over 1012 nodes and 109 infosets. All the methods share the same neural network architecture proposed in Brown et al. (2019). We perform a mild hyper-parameter search for ACH, A2C, RPG, and NeuRD. For OS-DCFR and DREAM, we follow the hyper-parameters presented in Steinberger et al. (2020). The exploitability is measured in the number of chips per game, where a big blind is 100 chips. All the hyper-parameters and the running environment are described in the Appendix H.2.
As shown in Figure 3, ACH performs competitively with OS-DCFR and slightly worse than DREAM on FHP in terms of exploitability per episodes generated. However, ACH is much more sample efficient: ACH achieves an exploitability of 10 almost 100 times faster than DREAM and 1,000 times faster than OS-DCFR. Also, in comparison with methods of similar sample efficiency (A2C, RPG, and NeuRD), ACH converges significantly faster and achieves a lower exploitability.

heading: 8 CONCLUSIONS
text: In this paper, we investigated the problem of adapting policy gradient methods in deep RL to tackle a large-scale IIG, i.e., 1-on-1 Mahjong. To this end, we developed a new model-free actor-critic algorithm, i.e, ACH, for approximating a NE in large-scale IIGs. ACH is memory and computation efficient, as it uses only trajectory samples at the current iteration and requires no computation of best response. ACH is theoretically justified as it is derived from a new neural-based CFR, NW-CFR, for which we proved the convergence to an approximate NE in 2-player zero-sum IIGs under certain conditions. The superior performance of ACH was validated on both our 1-on-1 Mahjong benchmark and other common benchmarks. Secondly, to facilitate research on large-scale IIGs, we proposed the first 1-on-1 zero-sum Mahjong benchmark, whose infoset size and game length are much larger than poker. Finally, using ACH we obtained the 1-on-1 Mahjong agent JueJong, which has demonstrated stronger performance against the Mahjong champion Haihua Cheng.
10PPO is replaced with A2C in a synchronous training environment.

heading: REPRODUCIBILITY STATEMENT
text: The experiments on the 1-on-1 Mahjong benchmark were run in a large cluster of thousands of machines, on which we have developed an efficient actor-learner training platform, similar to IMPALA (Espeholt et al., 2018). The codes of both the platform and the 1-on-1 Mahjong benchmark are not released currently but are planned to be open sourced in the near future. Yet, the codes for both the actor part and the learner part of each algorithm (PPO, RPG, NeuRD, and ACH) are included in the supplementary materials. All the hyper-parameters are listed in the Appendix H.
We implement the FHP benchmark as well as the FHP specific best response algorithm based on the OpenSpiel project. The codes will be open sourced in the future. All the hyper-parameters are listed in the Appendix H.
The experiments on the benchmarks in OpenSpiel were run using the OpenSpiel environment. We include the necessary codes, rand seeds, and instructions to reproduce all the results on OpenSpiel in the supplementary materials. All the hyper-parameters are listed in the Appendix H.
All the theoretical results are presented in the main text, with all the proofs given in the Appendix C.

heading: A.1 THE GAME RULES

heading: Category Name Type Copy Count
text: There are 24 unique tiles and 72 tiles in total in the 1-on-1 Mahjong game, as shown in Figure 5. At the beginning of the 1-on-1 Mahjong game, each player is dealt with 13 tiles, the content of which is invisible to the other. Afterwards, each player takes actions in turn. Typically, the first player draws a tile from the deck wall and then discards a tile, and the next player takes the same types of actions in sequence. There are exceptional cases where the player does not draw a tile from the deck wall but Chow, Pong, or Kong the tile the opponent just discarded. Afterwards, the player discards a tile, and the game proceeds. Also, after drawing a tile from the deck wall, there are cases where the player could Kong, after which the player draws and discards a tile in sequence. There are 10 types of actions with 105 different actions in total, a full description of which is listed in Table 2.
The goal of each player is to complete a legal hand prior to the opponent, by drawing a tile or using the tile the opponent just discarded. A legal hand is generally in the form of four melds and a pair, with an exception of 7 pairs. Different categories of legal hands, 64 in total, come with different points, which is fully described in Table 3. Besides, a legal hand can belong to multiple categories, and the score of a legal hand is the sum of points of corresponding categories. Legal hands with higher points are generally more difficult to form in terms of either luck or strategy, and it is critical for a player to trade off the winning probability and the corresponding winning points. If no player completes a legal hand before the tiles are exhausted, the game is tied. A flow chart of the game is illustrated in Figure 6.
English name Points Pattern descriptions Conflicts
1 Pure Double
Chow 1 Two identical sequences of 3 character tiles.
2 Short Straight 1 A hand with two successive sequences.
3 Two Terminal
Chows 1 A hand with two sequences 123 and 789.
4 Melded Kong 1 A hand with exposed quads.
5 Edge Wait 1 A hand completion with the situation there is only one tile name to complete because you have the incomplete sequence in edge (12 or 89).
6 Closed Wait 1 A hand completion with the situation there is only one tile name to complete because you have the incomplete sequence lacking center (like 24 and 79).
7 Single Wait 1 A hand completion solely waiting on a tile to form a pair.
8 Self Draw 1 A hand completion by draw.
9 Flower Tile 1 Whenever a player draws a flower or season tile, this is counted as 1 point.
10 Ready Hand 2 A hand that is one tile away from winning.
11 Dragon Pung 2 A hand with a triplet or quad of dragon tile.
12 Concealed Hand 2 A hand without exposed melds and completed by seizing the discarded tile.
13 All Chows 2 A hand with four sequences and a pair in characters.
14 Tile Hog 2 A hand with four same tiles, other than a melded quad.
15 Two Concealed
Pungs 2 A hand with two concealed triplets or quads.
16 Concealed Kong 2 A hand with a concealed quad.
17 All Simples 2 A hand consisting of no character 1, 9 and honor tile.
18 Outside Hand 4 A hand that includes terminals and honors in each meld, including the pair.
19 Fully Concealed
Hand 4 A hand without exposed melds and completed by drawing a tile. Self Draw
20 Two Melded
Kongs 4 A hand with two exposed quads. Melded Kong
21 Last Tile 4 Winning on a tile that is the last of its kind. Three of the other tiles on the table already revealed to all players.
22 Little Three
Winds 6 A hand with two wind triplets or quads and a wind pair.
23 All Pungs 6 A hand with four triplets or quads.
24 Half Flush 6 A hand consisting of character and honor tiles.
25 Two Dragon
Pungs 6 A hand containing two dragon triplets or quads.
Dragon Pung
26 Two Concealed
Kongs 6 A hand containing two concealed quads. Concealed Kong
27 Melded Hand 6 Every set in the hand must be completed with tiles discarded by other players.
Single Wait
28 Out with
Replacement Tile 8 Hand completion with supplemental tile when you melding quad.
Self Draw
29 Rob Kong 8 Winning off the tile that opponent adds to a melded triplet(to create a Kong).
Last Tile
30 Last Tile
Claim 8 Winning off another player on the last tile (of the game).
31 Pure Straight 16 A hand with three sequences 123, 456 and 789 in characters.
Short Straight, Two Terminal Chows
32 Pure Shifted
Chows 16 Three sequences in characters each shifted either one or two numbers up from the last, but not a combination of both.
33 All Flowers 16 A player has or draws all flower tiles. Flower Tiles 34 Full Flush 16 A hand consisting of only characters.
35 Three Concealed
Pungs 16 A hand with three concealed quads or triplets. Two Concealed Pungs
36 Four Honour
Pungs 24 A hand with four honor triplets or quads. All Pungs
37 Big Three
Winds 24 A hand with three winds be triplets or quads. Little Three Winds
38 Seven Pairs 24 A hand with seven pairs.
Concealed Hand, Single Wait, Fully Concealed Hand.
39 Pure Triple
Chow 24 A hand with three identical sequences.
Pure Double Chow
40 Pure Shifted
Pungs 24 A hand with three number triplets or quads with successive numbers. Pure Triple Chow
41 Four Pure
Shifted Chows 32 Four shifted number sequences, each shifted either one or two numbers up from the last, but not a combination of both. Pure Shifted Chows, Short Straight, Two Terminal Chows, Pure Double Chow
42 Three Kongs 32 A hand with three quad melds.
Two Melded Kongs, Melded Kong, Two Concealed Kongs, Concealed Kong
43 All Terminals and Honours
32 A hand consisting of only terminal and honor tiles. All Pungs, Outside Hand
44 Heavenly Ready
Hand 32 A hand that is one tile away from winning at the beginning of the game. Ready Hand
45 Quadruple Chow 48 A hand with four identical sequences.
Pure Triple Chow, Tile Hog, Pure Double Chow, Two Terminal Chow, Pure Shifted Pungs
46 Four Pure
Shifted Pungs 48 A hand with four character triplets or quads with successive numbers. Pure Shifted Pungs, Pure Triple Chow, All Pungs
47 Four Winds Seven Pairs
48 Seven pairs hand with four different wind pairs.
Seven Pairs, Concealed Hand, Single Wait, Fully Concealed Hand
48 Three Dragons
Seven Pairs 48 Seven pairs hand with three different dragon pairs. Seven Pairs, Concealed Hand, Single Wait, Fully Concealed Hand
49 Little Four
Winds 64 A hand with three winds be triplets or quads, and the last wind be pair. Big Three Winds, Little Three Winds
50 Little Three
Dragons 64 A hand with two dragons be triplets or quads, and the last dragon be pair. Two Dragon Pungs, Dragon Pung
51 All Honours 64 A hand consisting of only honor tiles.
All Terminals And Honours, All Pungs, Four Honour Pungs, Outside Hand
52 Four Concealed
Pungs 64 A hand with four concealed triplets or quads. Concealed Hand, All Pungs, Three Concealed Pungs, Two Concealed Pungs, Fully Concealed Hand
53 Pure Terminal
Chows 64 A hand with two Two Terminal Chows and a pair of number 5 in character. All Chows, Seven Pairs, Full Flush, Pure Double Chow, Two Terminal Chows
54 Big Four Winds
88 A hand with triplets or quads of all four winds and an pair.
All Pungs, Little Three Winds, Big Three Winds, Four Honor Pungs
55 Big Three Dragons
88 A hand with triplets or quads of all three dragons.
Dragon Pung, Two Dragon Pungs
56 Nine Gates 88 Collecting number tiles 1112345678999 without melding, and completing with any tile of characters.
Full Flush, Concealed Hand, Fully Concealed Hand
57 Four Kongs 88 A hand with four quad melds.
Three Kongs, Two Melded Kongs, Melded Kong, Single Wait, Concealed Kong, Two Concealed Kongs, All Pungs
58 Seven Shifted
Pairs 88 Seven pairs hand with successive seven numbers in characters.
Seven Pairs, Single Wait, Concealed Hand, Full Flush, Fully Concealed Hand

heading: A.2 THE STATE AND ACTION SPACE
text: The state space size of 1-on-1 Mahjong, shown as the infoset count in Figure 4, is approximately 1074. Yet, the state space of 1-on-1 Mahjong is not as easily abstracted as in poker. The primary reason is that a single tile difference in the state could significantly impact the strategy, e.g., making a legal hand illegal and vice versa. In contrast, states that have similar strength in poker could share a common strategy. For instance, the optimal preflop strategy could be very similar for “Ace-Four" and “Ace-Three" in poker. Another reason is that a state in 1-on-1 Mahjong is divided into different information groups, as demonstrated in Figure 7(a). Different information groups have significantly different meanings. For instance, one group denotes the player’s hand, which is invisible to the opponent, while another one denotes the player’s discarded tiles, which are visible to both players.
There are 105 different actions in total, as demonstrated in Table 2. The number of legal actions in a state is relatively small compared to poker. Yet, the game length in 1-on-1 Mahjong is larger than that in poker. Players can decide up to about 40 sequential actions in 1-on-1 Mahjong, whereas most 1-on-1 poker games end within 10 steps. As a result, the reaching probability of states in 1-on-1 Mahjong may vary more significantly than that in poker.

heading: A.3 THE EFFECTS OF A LARGER INFOSET SIZE AND A LONGER GAME LENGTH
text: As shown in Figure 4, 1-on-1 Mahjong has a larger infoset size than poker. The infoset size does not seem to have an influence on the convergence of a tabular CFR (Zinkevich et al., 2008). However, when trajectory sampling and function approximation are used together, the situation may be different. To be more specific, in a trajectory sampling algorithm, the variance of the sampled counterfactual values (regrets) of a larger infoset may tend to be higher, which may have a large influence on
performance when neural network function approximation is used. In other words, 1-on-1 Mahjong may be complementary to poker in evaluating algorithms using deep neural networks and only trajectory samples.
The game length has a direct impact on the sampling methods used. For poker, which has a relatively short game length, methods that samples multiple actions in a state are very common in the literature. Yet, sampling multiple actions consistently in game trees with long episodes is certainly prohibitive, as the number of samples goes exponentially with the game length. 1-on-1 Mahjong has a maximal game length about 40, which may be daunting for methods that try to sample multiple actions in a state. In other words, 1-on-1 Mahjong may be complementary to poker in evaluating algorithms when only trajectory samples are allowed.

heading: B THE MODEL DESIGN OF OUR 1-ON-1 MAHJONG AGENT JUEJONG
text: The model of JueJong is an end-to-end neural network that takes all relevant information as input and outputs both the probabilities of all actions and the state value. This is different from five separated neural networks in Suphx (Li et al., 2020b), representing five different types of actions. Also, we train JueJong from zero by pure self-play using ACH, while the five neural networks in Suphx were trained by supervised learning on human data, with only the “Discard” network further enhanced by RL. Figure 7 gives an overview of the model design of JueJong.
The marked regions in Figure 7(a) summarize the information an agent can observe. Regions 1 to 7 are encoded in image-like features, which represent the player’s hand, the player’s Chow, Pong, and Kong, the player’s concealed-Kong, the player’s Discard, the opponent’s Chow, Pong, and Kong, the opponent’s concealed-Kong, and the opponent’s Discard respectively. A feature map, as shown in Figure 7(b), of height 4 and width 17 is employed, where a 0 or 1 in the ith row and jth column means whether there are i tiles of the jth type for the input set of tiles. Therefore, a single or two successive convolutional layers with 3× 3 kernels efficiently derive row and column combinations. Note that, in Suphx (Li et al., 2020b), the feature maps are one-dimensional vectors, where 1 × 3 kernels are used. The black tile in Figure 7(b) is designed exclusively for Region 6 to indicate how many concealed-Kongs the opponent has. For discarded tiles in Region 4 or 7, 24 such feature maps are used to indicate the latest 24 discarded tiles in order, with one feature map encoding one discard tile. All the feature maps are concatenated in the channel dimension, and therefore the final image-like features are in the shape of 4× 17× 53 (h× w × c). Regions 8 to 11 are encoded in one-hot features, which represent the player’s position (0 or 1), the is_ready state of both players, and the bonus tiles of both players. Additionally, the last action (not shown as a region in Figure 7(a)) for each player is encoded in a one-hot feature vector as well.
We apply residual blocks (He et al., 2016) to transform the image-like features. There are totally 3 stages with 3 residual blocks and 1 transition layer in each stage, as shown in Figure 7(c). Each block contains two convolutional layers with kernel size 3× 3 and number of output feature maps 32, 64, and 128 for each stage. The transition layer is point-wise convolution 1× 1, and the one in the final stage scales the input to 32 channels. Subsequently, the transformed image-like features are reshaped to a vector, which is concatenated with the one-hot feature vectors. A fully-connected layer (dimension 1024) is then used to transform the concatenated feature vector, and two branches with two fully-connected layers (dimension 512× 512) each output the action probabilities and the state value respectively. Besides, we apply batch normalization (Ioffe & Szegedy, 2015) and ReLU non-linearity after all convolutional layers and fully-connected layers.

heading: C THEORETICAL PROPERTIES OF NW-CFR

heading: C.1 PROOF FOR THEOREM 1
text: In order to prove Theorem 1, we first prove the following Lemma.
Lemma 1. For a weighted CFR, if wt(s) ∈ [wl(s), wh(s)], 0 < wl(s) ≤ wh(s) ≤ 1, then
max a∈A(s) t∑ k=1 rck(s, a) ≤ maxa∈A(s)R w t (s, a) wh(s) + (wh(s)− wl(s))|A(s)|∆t wh(s) . (4)
Proof. First, for any state s ∈ S and action a ∈ A(s), we have
Rwt (s, a) := t∑ k=1 wt(s)r c k(s, a)
= ∑
k:rck(s,a)≥0
wk(s)|rck(s, a)| − ∑
k′:rc k′ (s,a)<0
wk′(s)|rck′(s, a)|
≥ ∑
k:rck(s,a)≥0
wl(s)|rck(s, a)| − ∑
k′:rc k′ (s,a)<0
wh(s)|rck′(s, a)|.
(5)
So,
Rwt (s, a) ≥ wh(s) t∑
k=1
rck(s, a)− (wh(s)− wl(s)) ∑
k′:rc k′ (s,a)≥0
|rck′(s, a)|. (6)
In other words, t∑
k=1
rck(s, a) ≤ Rwt (s, a)
wh(s) + (wh(s)− wl(s)) wh(s) ∑ k′:rc
k′ (s,a)≥0
|rck′(s, a)| (7)
So,
max a∈A(s) t∑ k=1 rck(s, a) ≤ maxa∈A(s)R w t (s, a) wh(s) + (wh(s)− wl(s))|A(s)|∆t wh(s) . (8)
Then we can prove the Theorem:
Proof. For NW-CFR, the policy at iteration t is generated according to Hedge:
πt(s, a) = eη(s)R a t−1(s,a)∑
a′ e η(s)Rat−1(s,a
′) , (9)
where
Rat−1(s, a) = t−1∑ k=1 fµkp (s)r c k(s, a). (10)
On the other hand, weighted CFR with Hedge generates policy at iteration t according to
πt(s, a) = eη(s)R w t−1(s,a)∑
a′ e η(s)Rwt−1(s,a
′) , (11)
where
Rwt−1(s, a) = t−1∑ k=1 wk(s)r c k(s, a). (12)
So, when wk(s) = fµkp (s) ≥ wl(s) > 0 for any s ∈ S and k > 0, NW-CFR and weighted CFR with Hedge generates the same policy at each iteration, and therefore NW-CFR is equivalent to weighted CFR with Hedge.
Then, we can prove the convergence property of NW-CFR. Let Swt (s) = ∑
a∈A(s)
eη(s)R w t (s,a). (13)
We have ln Swt Sw0
= ln ∑
a∈A(s)
eη(s)R w t (s,a) − ln |A(s)|
≥ ln (
max a∈A(s)
eη(s)R w t (s,a) ) − ln |A(s)|
=η(s) max a∈A(s)
Rwt (s, a)− ln |A(s)|.
(14)
On the other hand, for each k = 1, . . . , t,
ln Swk Swk−1 = ln
(∑ a∈A(s) e
η(s)Rwk−1(s,a)eη(s)wk(s)r c k(s,a)∑
a∈A(s) e η(s)Rwk−1(s,a)
)
= ln  ∑ a∈A(s) πk(s, a)e η(s)wk(s)r c k(s,a) . (15) Since
lnE[esX ] ≤ sEX + s 2(b− a)2
8 , (16)
ln Swk Swk−1
≤ η(s) ∑
a∈A(s)
πk(s, a)wk(s)r c k(s, a) +
η2(s)∆2(s)w2k(s)
8 . (17)
Note that rck(s, a) = v c k(s, a)− ∑ a∈A(s) πk(s, a)v
c k(s, a). So∑
a∈A(s)
πk(s, a)wk(s)r c k(s, a) = 0. (18)
Therefore,
ln Swk Sw0 ≤ η2(s)∆2(s)
∑t k=1 w 2 k(s) 8 . (19)
So,
η(s) max a∈A(s)
Rwt (s, a)− ln |A(s)| ≤ η2(s)∆2(s)
∑t k=1 w 2 k(s) 8 , (20)
i.e.,
max a∈A(s) Rwt (s, a) ≤ ln |A(s)| η(s) + η(s)∆2(s)
∑t k=1 w 2 k(s) 8 . (21)
According to Lemma 1,
max a∈A(s) Rct(s, a) ≤ ln |A(s)| η(s)wh(s) + η(s)∆2(s)
∑t k=1 w 2 k(s)
8wh(s) + (wh(s)− wl(s))|A(s)|∆t wh(s) . (22)
When η(s) = √
8 ln |A(s)|/{[wh(s)]2∆2(s)T} and wt(s) ∈ [wl(s), wh(s)] ⊂ (0, 1], t = 1, . . . , T , we have
max a∈A(s)
RcT (s, a) ≤
√ ln |A(s)|∆2(s)w2h(s)T
2w2h(s) + (wh(s)− wl(s))|A(s)|∆T wh(s)
≤∆ √ T
2 ln |A(s)|+ (wh(s)− wl(s))|A(s)|∆T wh(s) .
(23)
According to Theorem 2 in Zinkevich et al. (2008), the total regret RT ≤ ∑ s∈S max a∈A(s) [RcT (s, a)] +
≤ ∑ s∈S
( ∆ √ T
2 ln |A(s)|+ (wh(s)− wl(s))|A(s)|∆T
wh(s)
)
≤|S|∆ √ T
2 ln |A|+ |A|∆T ∑ s∈S (wh(s)− wl(s)) wh(s) .
(24)
As a result, according to the folk theorem in Zinkevich et al. (2008), the average strategy converges to an -equilibrium, where
= RT T
= |S|∆ √ 1
2T ln |A|+ |A|∆ ∑ s∈S (wh(s)− wl(s)) wh(s) . (25)

heading: C.2 PROOF FOR COROLLARY 1
text: Proof. When the behavioral policy µp,k of each player p ∈ P across iterations k > 0 is constant, the reaching probability fµkp (s) of any state s ∈ S is also constant. Assume fµkp (s) = w(s), then,
Rat−1(s, a) = t−1∑ k=1 fµkp (s)r c t (s, a) = w(s) t−1∑ k=1 rct (s, a) = w(s)R c t−1(s, a). (26)
In other words, Rat−1(s, a) is equal to the cumulative counterfactual regret scaled by a time-invariant weight w(s). Hence, the policy at iteration t is
πt(a|s) = eη(s)w(s)R c t (s,a)∑
a′ e η(s)w(s)Rct−1(s,a
′) =
eη ′(s)Rct (s,a)∑
a′ e η′(s)Rct−1(s,a
′) , (27)
where the new η′(s) is set to √
8 ln |A(s)|/[∆2(s)T ]. So, when µp,k is constant, NW-CFR is equivalent to CFR with Hedge when y(a|s; θt) is sufficiently close to Rat (s, a). Furthermore, since wl(s) = f µk p (s) = wh(s), the second term in (25) disappears, i.e.,
= |S|∆ √ 1
2T ln |A|. (28)
As a result, the exploitability bound of CFR with Hedge is recovered.

heading: C.3 CONTINUOUS-TIME DYNAMICS OF ACH
text: We illustrate the convergence dynamics of ACH in the game of Rock-Paper-Scissors, in comparison with other actor-critic methods (PPO/A2C, RPG, and NeuRD), in Figure 8.

heading: D EXPERIMENTAL RESULTS OF THE WEIGHTED CFR
text: As stated in Section 5, ACH is a practical implementation of the NW-CFR, which is a straightforward neural extension to the weighted CFR defined in Definition 1, together with wt(s) = fµtp (s) and Hedge. In order to investigate the behavior of weighted CFR, in this section, we instantiate multiple weighted CFR algorithms with different settings of the weight wt(s) by varying µp,t, since fµtp (s) depends only on µp,t. Note that the weighted CFR traverses the full game tree at every iteration and that µp,t is only used to calculate the state reaching probability fµtp (s). We test these algorithms on three small IIGs in OpenSpiel: Kuhn poker, Leduc poker, and Liar’s Dice.
As shown in Figure 9, the weighted CFR with wt(s) induced by a stationary µp,t (i.e., the uniform strategy) converges at the same pace with CFR(Hedge). As a result, Corollary 1 is verified on the three small benchmarks. Also, as Theorem 1 states, the exploitability of the weighted CFR is influenced by the range of wt(s) = fµtp (s). This is experimentally demonstrated in Figure 9 by setting µp,t to a mixed strategy between the current strategy πp,t and the uniform strategy. We can see that the weighted CFR still performs competitively with CFR(Hedge), when µp,t(s) = 0.5Uniform + 0.5πp,t(s).

heading: E ACH: A PRACTICAL IMPLEMENTATION OF NW-CFR
text: To address the practical issues mentioned in Section 5, we provide a practical and parallel implementation of NW-CFR, i.e., ACH, which employs a framework of decoupled acting and learning, similar to IMPALA (Espeholt et al., 2018). ACH maintains a policy net y(a|s; θ) and a value net V (s;ω), where θ and ω share a large portion of parameters (see Figure 7). Both players use the same θ and ω. We do not use an additional time-invariant behavioral policy for sampling actions. Instead, we use the current policy πt. As a result, we can use the same samples to train both the value net and the policy net. η(s) is incorporated into the learned target value in the policy net, so the policy π(a|s) is obtained by directly softmaxing on y(a|s; θ). The advantage A(s, a) is estimated by the GAE(λ) (Schulman et al., 2016), using sampled rewards and V (s;ω), for only sampled states and actions. The value and policy nets are updated as soon as a mini batch of samples is available. In other words, we update θ and ω once using a single mini batch at each iteration. As a result, the policy loss reduces to Lπ = η(s) y(a|s;θ)πold(a|s)A(a, s), where 1 πold(a|s) accounts for the fact that a was sampled using πold(a|s). ACH handles asynchronous training with the importance ratio clipping of PPO (Schulman et al., 2017). To avoid numerical issues, the mean is subtracted from the policy output, which is then clipped within a range. The pseudocode of ACH is given in Algorithm 2.
We employ an entropy loss to encourage exploration during training and hopefully the convergence of current strategy to a NE (Srinivasan et al., 2018). ACH updates θ and ω simultaneously, and the overall loss is:
LACH =− cη(s) y(a|s; θ) πold(a|s) A(a, s) + α 2 [V (s;ω)−G)]2 + β ∑ a π(a|s; θ) log π(a|s; θ). (29)
Theoretically, y(a|s′; θ) for non-sampled states s′ should also be trained with the target y(a|s′; θold). Yet, in ACH, we only update θ once using a single mini-batch at each iteration. Therefore, θ is equal to θold before the update. In other words, the policy loss for non-sampled states is 0 in ACH.
Algorithm 2: ACH Initialize the policy and critic parameters: θ and ω. Start multiple actor and learner threads in parallel. Actors: while true do
Fetch the latest model from the learners. Generate samples via self-play in the form: [a, s,A(s, a), G, πold(a|s)]. Send the samples to the replay buffer.
Learners: for t ∈ 1, 2, 3, ... do

heading: F THE EFFECT OF THE BEHAVIOR POLICY ON ACH IN FHP
text: As we noted in the paper, the behavior policy µp,t in ACH could be set to either the current policy πp,t or simply a uniform sampling policy. As Corollary 1 states, a tighter bound on the exploitability of the average policy of NW-CFR can be obtained, if µp,t is stationary over iterations. However, since we have decided to use the current policy (trained with an entropy regularization) for evaluation in ACH, the effect of the behavior policy is unclear from a theoretical perspective. Hence, we conduct an experiment to investigate this.
In Figure 10, we compare the exploitability of the current policy of ACH on FHP, by setting the behavior policy in ACH to either the current policy or a uniform sampling policy. From the comparison, it seems that the performance of the current policy of ACH is not sensitive to the choices of behavior policy. The reason might be that the additional entropy loss forces the current strategy to be stable and prone to a uniform random strategy. In other words, when using the current strategy as the behavior policy, the behavior policy tends to be stable. Another reason might be that the current policy instead of the average policy is evaluated.

heading: G ADDITIONAL RESULTS ON SMALL IIG BENCHMARKS IN OPENSPIEL
text: We further evaluate ACH and compare it with A2C, RPG, and NeuRD on three benchmarks from OpenSpiel: Kuhn poker, Leduc poker, and Liar’s Dice. All the experiments were run single-threaded
on a 2.24GHz CPU. We use the network architecture in OpenSpiel, which has a 128-neurons fullyconnected layer followed by ReLU and two separate linear layers for the policy and the state/action value. For A2C, RPG, and NeuRD, we use the default hyper-parameters in OpenSpiel. ACH shares most of the hyper-parameters with A2C. All the hyper-parameters are listed in the Appendix H.3.
The exploitability of an agent is exactly calculated using tools in OpenSpiel. For each method, we compute the exploitability of each agent every 1e5 training steps, the results of which are plotted in Figure 11. Clearly, ACH converges significantly faster and achieves a lower exploitability than other methods across the three benchmarks. There is still some gap between 0 and the exploitability ACH converges to. This may due to the neural network approximation error and the fact that we use the current strategy instead of the average strategy for the evaluation. A2C has the worst performance, since it is designed for single-agent environments. Moreover, the superiority of ACH is most significant on the Liar’s Dice benchmark, which is the most complex one of the three benchmarks.
As a complement, we present the head-to-head performance of A2C, RPG, NeuRD, and ACH on the three benchmarks in OpenSpiel: Kuhn poker, Leduc poker, and Liars Dice. As demonstrated in Table 4, the agent of ACH won all other agents across all the three benchmarks. The superior performance of ACH is most significant on the Liars Dice benchmark, which is the most complex one of the three benchmarks.

heading: H HYPER-PARAMETERS

heading: H.1 HYPER-PARAMETERS FOR THE 1-ON-1 MAHJONG EXPERIMENT
text: We used the Adam optimizer (Kingma & Ba, 2014) for all experiments on the 1-on-1 Mahjong benchmark. We performed a mild hyper-parameter search on PPO and used the best setting for the shared hyper-parameters of all methods (PPO, RPG, NeuRD, and ACH). For each setting in the hyper-parameter search, we conducted 3 independent runs with different random seeds. Table 5 gives an overview of hyper-parameters for each method. Also, we report the performance of current strategy, instead of the average strategy, for each method.

heading: H.2 HYPER-PARAMETERS FOR THE FHP EXPERIMENT
text: We used the Adam optimizer Kingma & Ba (2014) for all experiments on FHP. All the experiments were run multi-threaded and synchronously using 10 2.24GHz CPUs. We update the neural networks of ACH and other methods (A2C, RPG, and NeuRD) every 1000 episodes, with a batch consisting all the samples collected in the 1000 episodes. Since the average length of FHP is around 2, the batch size is roughly 2000. We performed a mild hyper-parameter search for ACH, A2C, RPG, and NeuRD, as shown in Table 6. Note that we do not need to clip the advantages in a synchronous method, so the ratio clip hyper-parameter is not needed. For FHP, we introduced a reward normalizer to normalize the rewards as the returns in FHP are in [−700, 700]. Besides, we found that A2C, RPG, and NeuRD are very sensitive to the entropy coefficient, and we had to use a larger entropy coefficient in these algorithms than ACH. For OS-DCFR and DREAM, we use the same hyper-parameters presented in Steinberger et al. (2020). All the hyper-parameters are given in Table 6.

heading: H.3 HYPER-PARAMETERS FOR THE EXPERIMENT ON OPENSPIEL
text: We used stochastic gradient descent with constant learning rate for all experiments on benchmarks from OpenSpiel. For A2C and RPG, we used the default implementations and hyper-parameters in OpenSpiel. NeuRD was originally implemented using counterfactual regrets in OpenSpiel. We re-implemented NeuRD using predicted advantages and set the shared hyper-parameters of NeuRD identical to those in RPG. All methods employ an entropy loss to encourage exploration during training and hopefully the convergence of current strategy to a NE. Also, we report the performance of current strategy, instead of the average strategy, for each method.
In OpenSpiel, the value parameters are updated separately and more frequently compared to the policy parameters for A2C, RPG, and NeuRD. Yet, the value loss and the policy loss are combined in ACH, and all parameters are updated simultaneously, as illustrated in Algorithm 2. Also note that, in the single-threaded OpenSpiel training environment, the actor and the learner run in sequence. As a result, π(a|s; θ) is always equal to πold(a|s) in Algorithm 2. We performed a mild hyper-parameter search for ACH, which is illustrated in Table 7. For each setting in the hyper-parameter search, we conducted 4 independent runs with different random seeds. The final hyper-parameters used for each method are listed in Table 8, with 3 additional hyper-parameters of ACH listed in the “Best” column in Table 7.

heading: I THE RELATIONSHIP BETWEEN ACH AND SUPHX
text: Recently, Suphx (Li et al., 2020b) has achieved stunning performance on Japanese Riichi Mahjong. The development of Suphx is enabled by a novel integration of existing supervised learning and RL methods in addition to some newly developed techniques. Three new techniques were introduced in Suphx: global reward prediction, oracle guiding, and run-time policy adaptation. The global reward prediction technique is to handle the multi-round game situation, which is irrelevant to our 1-on-1 Mahjong setting (only one round per game in our test setting). The oracle guiding technique decays the invisible feature during training, which is of independent interest in dealing with imperfectinformation. The run-time policy adaptation technique adapts the trained policy at test time, and this can be combined with ACH, which is a training algorithm. In summary, Suphx is more of a novel system than a new algorithm. For this reason, we did not implement and compare Suphx with ACH in our 1-on-1 Mahjong experiment. Nonetheless, the oracle guiding technique may be complementary to ACH in handling imperfect-information, and we will investigate this in our future work.

Review summaries:
The authors propose a new, non-tabular method for large, two player zero-sum games. The method is evaluated on some standard benchmark games (e.g. Leduc poker) as well as on large game of 1v1 Mahjong.

This paper presents Actor-Critic Hedge (ACH): an actor-critic method for approximating Nash equilibrium strategies in large extensive-form games. ACH is an extension of the CFR family of algorithms that uses deep learning, and is able to learn model-free by training on trajectories and not full game traversals or subgames, which is common in much of the related CFR literature. The technique is demonstrated in toy poker domains commonly used in the literature (Kuhn and Leduc poker), Liar’s Dice, and in 1-on-1 Mahjong. In Mahjong, the ACH agent is shown to defeat several human players, including a Mahjong champion. 

This paper presents ACH, a neural network policy-gradient method for approximating a Nash equilibrium in two-player zero-sum games. ACH is used to compute a strong agent for a two player variant of Mahjong, competitive with the strongest human players. It has a thorough experimental analysis, both in Mahjong and in smaller test environments. 

This paper proposes a method somewhat similar to Deep CFR, NeuRD and RPG, where a policy is trained to predict a weighted counterfactual regret. In small openspiel experiments the method seems to outperform NeuRD and RPG, but no comparisons are made to Deep CFR/DREAM/ARMAC. Impressive results against a top Mahjong player demonstrate that this method can scale to large games.