Actor-Critic Policy Optimization in a Large-Scale Imperfect-Information Game
Authors: Haobo Fu
Weiming Liu
Shuang Wu
Yijia Wang
Tao Yang
Kai Li
Junliang Xing
Bin Li
Bo Ma
QIANG FU
Yang Wei
Venue: ICLR 2022 Poster (2022)
Keywords: Policy Optimization
Nash Equilibrium
Mahjong AI

Abstract: The deep policy gradient method has demonstrated promising results in many large-scale games, where the agent learns purely from its own experience. Yet, policy gradient methods with self-play suffer convergence problems to a Nash Equilibrium (NE) in multi-agent 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 regret. This modification is achieved by approximating the regret via a deep neural network and minimizing the regret via generating self-play policies 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.

Published as a conference paper at ICLR 2022
ACTOR-CRITIC POLICY OPTIMIZATION IN A LARGE- SCALE IMPERFECT-INFORRATIIO GAME
Haobo Fu, "Weiming Liu," 2' Shuang Wu, Yijia Wang. 3" Tao Yang." Kai Li,4 45 Junliang Xing, Bin Li, Bo Ma. Qiang Fu, and Wei Yang!
Tencent AT Lab, Shenzhen, China University Science and Technology of China, Hefei, China Peking University, Beijing, China
Institute Automation, Chinese Academy of Sciences, Beijing, China 5 School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing, China
ABSTRACT
The deep policy gradient method has demonstrated promising results in many large- scale games, where the agent learns purely from its own experience. Yet, policy gradient methods with self-play suffer convergence problems to a Nash Equilibrium (NE) in multi-agent situations. Counterfactual regret minimization (CFR) has a convergence guarantee to a NE in 2-player zero-sum games, but it usually needs domain -seaiiic 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 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 regret. This modification is achieved by approximating the regret via deep neural network and minimizing the regret via generating self-play policies using Hedge. ACH is theoretically justified is derived from 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-ar methods. Also, the agent obtained by ACH defeats human champion 1-on-1 Mahjong.
INTRODUCTION
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, 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 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 with self-play have no convergence guarantee optimal solutions in competitive ImperfecttIIfformaii 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 Markovian. However, learning becomes non-so -tatttaioonary and non-Markovian when multiple agents learn simultaneously in competitive environment.
An optimal solution to 2-player zero-sum IIG usually refers to Nash Equilibrium (NE), where no player could improve by unilaterally deviating to a different policy. Tremendous progress in computing NE solutions has been made by family of tabular methods: Counterfactual regret
"Equal contribution. Correspondence to: Haobo Fu cenoboffu@teneen..cm
Work done while intersship Tencent AI Lab, Shenzhen, China.

---

Published as a conference paper at ICLR 2022
minimization (CFR) (Zinkevich et al., 2008). CFR is 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- 2-player zero-sum IIGs. A perfect game model is required in CFR to sample many if not all actions from a state. To handle large-scale IIGs with CFR, abstractions (applied to either the action space or the state space) usually employed to reduce the game to manageable size (Moravčík et al., 2017; Brown & Sandholm, 2018; 2019)'. However, abstractions are domain specific ( (Waugh et al., 2009; Johanson al., 2013; Ganzfried & Sandholm, 2014). More importantly, some large-scale IIGs are inherently difficult to be abstracted, such as the game of Mahjong (Li et al., 2020b).
In this paper, we investigate a large-scale IIG, i.e., 2-player (1-on-1) zero-sum Mahjong, whose information set size and game length are much larger than poker". Li et al. (2020b) has recently de- veloped a strong 4-player Mahjong agent based on supervised learning and traditional Reinforcement Learning (RL). In comparison, we study 1-on-1 Mahjong from a game-theoretic perspective, i.e., aiming for a NE, We are interested in methods using only trajectory samples to learn, as it is infeasible to consistently sample multiple actions for each state in large-scale IIGs with long episodes. We employ deep neural networks to generalize across states, since the state abstraction in I-on-I Mahjong is inherently difficult, explained in the Appendix A.2. We make the following contributions.
Inheriting the scalability of deep RL methods and the convergence property of CFR, we develop new actor-critic algorithm, named Actor-Critic Hedge (ACH), for approaching a NE large-scale 2-player zero-sum IIGs. ACH employs deep neural network to approximate type of weighted cumulative counterfactual regret. In the meantime, ACH minimizes the regret via generating self- self-play policies using Hedge (Freund & Schapire, 1997).
We introduce Neural-based Weighted CFR (NW-CFR), of which ACH is practical implementa- tion. We prove that the exploitability of the average policy in NW-CFR decreases at the rate of
(/2) under certain conditions, where T denotes the number of iterations in NW-CFR.
To facilitate research on large-scale 2-player zero-sum IIGs, we propose a 1-on-1 Mahjong bench- mark. The corresponding game enjoys large population in online games.
We build 1-on-1 Mahjong agent, named JueJong, based on ACH. In initial evaluation against human players including a Mahjong champion", JueJong demonstrates superior performance.
2 NOTATIONS AND BACKGROUND
2.1 IMPERFECT- INNEEECCTINFORMATIONN GAMES AND NASH EQUILIBRIUM
An IIG is usually described in an extensive- game tree. A node (history) h E H. in the tree represents all information of the current situation. For each history h. there is a player p E P or chance player that should act at h. Define P: 7 + (C) When P(h) P, the player P(h) has to take an action a E A(h), and A(h) is the set of legal actions in h. The chance player is responsible for taking actions for random events. The set of terminal nodes is denoted by Z. For each player P E P. there is a payoff function defined on the set of terminal nodes, Up Z - R. In this paper, we focus on 2-player zero-sum games, where P {0, and (2 + (1)=) 0 for each E Z.
For either player p. the set of histories is partitioned into information sets (infosets). We denote the set of infosets for player p by Ip and an infoset in Ip by Ip. Two histories h, h' H are in the same infoset if and only if h and ' are indistinguishable from the perspective of player p. Hence, a player p's policy up is defined as a function that maps an infoset actions. We further define A(Tp)
probability distribution over legal A(h) and P(T,)) = P(h) for any h E Tp. A policy profile n is a tuple of policies (Tp: -pp). where म represents the player p's opponent policy. The expected payoff for player p under π is denoted by (T. π --p). We use A(I) to denote the range of payoff's reachable from history h in infoset I. Let A maxIeI,,PER ( fr((h denotes the joint probability of
reaching h under æ. f (h) is the contribution of player p to f (h), and (h) is the contribution of the opponent and chance: fz (h) f (h)ff (h). We focus on the perfect-recall setting, where each
DeepStack (Moravěík et al., 2017) employs sparse lookahead trees, much like the action abstraction.
Without specification, we mean Heads-up No-Limit Texas Hold' em in this paper.
Haihua Cheng is the Competition Mahjong champion of 2014 4 World Mahjong Master Tournament, 2018 Tencent Mahjong Tournament, and 2019 Tencent Mahjong Tournament.
2

---

Published as a conference paper at ICLR 2022
player recalls the sequence of their own infosets reached. We define (1p) 5 (h), wh E Ip and (m)(4p) = EneI, fh)(h). Hence, (Lp) =Ener, (h) fz (1, (Lp)
A best response BR(TTp) T-p is player p's policy that satisfies up up (BR(T=p)) TT maXx, up( Tp)). A NE is policy profile TT, where each player plays best response to the other: up(Tp; m-p) maxx, up( m-p) Vp E P. The exploitability of a player's pol- icy, denoted by e(Tp), measures the performance gap between Tp and NE policy mp. e(Rp) up( Tpp)) - (T BR(mp)). The exploitability of i is E( = [P] Epepe(TT))
2.2 REINFORCEMENT LEARNING AND POLICY GRADIENT METHODS
RL usually assumes a Markov decision process, where the agent selects an action og from the legal action set A(s:) in state 8; E S at each time step i. The agent then receives a reward r; from the environment and transitions to a new state 51+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 st (T) = E E 7
s) = E [G], with the discount factor 10,
Many methods in RL belong to policy gradient methods, in which the parameters @ of policy Ta is; O) are updated by performing gradient ascent directly on [= One early example the standard REINFORCE algorithm (Williams, 1992) that updates 0 in the direction V, log T (als; O)G, which is an unbiased estimate of Val
[M]T"[]] [G]. To further reduce the variance of the gradient, an action- independent baseline is often subtracted from G: Ve log T (alss; 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 A. Moreover, the value G (s) is replaced in A2C with the estimated advantage of action a in state A(s, a) Q(s, a) V(s). The Q value (ss, a) is usually estimated using sampled rewards and predicted values of future states. A2C updates the parameters 0 and w in a synchronous manner.
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; 8) T(als: 8)/T((a (a) s; fota). which results in r(a s; Ve log (Taas) A)s a) = Ver(a s; As. a). Furthermore. PPO con- strains the KL divergence between the learning policy xg and the old behavioral policy Toat by clipping the ratio to small interval around 1.0.
2.3 COUNTERFACTUAL REGRET MINIMIZATION
CFR is an iterative algorithm that minimizes the total regret of policy by minimizing the cumulative counterfactual regret in every state (infoset). The cumulative counterfactual regret of an action in state is defined as (5, a) Et (5 a). where [s a) denotes the instantancous counterfactual regret of action a in state s at iteration k. ri a) is equal to (s) (s, a) (as proven in Srinivasan et al. (2018)), where AT* a) is the advantage function of player p = Pss) at state s as defined in traditional RL. Intuitively, rf (s, a) represents how regretful the player p is that he does not select the action a in state s at iteration t. The term (s) = Σnes f=, is needed here reflect the fact that reaching state s is also controlled by the opponent -p and chance. To minimize the regret, a regret minimizer is utilized in each state at each iteration, generating a series of local policies Ti (s), ..... Te(s) (s). Once मe is obtained, rf a) generated by a game tree traversing using Te, and R8 (s, a) is updated accordingly: R (s, a) = 18, r))
For either player p. define the total regret as RT max, ΣT. (Up(=TT) x -pp)) Up (ppp T- -p..)). is proven in Zinkevich et al. (2008) that Rr < and (s) = max (s,-(s, a). As result, the total regret can be minimized by minimiz- ing the cumulative counterfactual regret at each state. Moreover, the average policy (r(ss)) = /EET f (s) for both players converges to NE if Rr for both players grows sub-ling sub-linearly with T (Zinkevich al., 2008). There are two commonly used regret minimizers: Regret Matching (RM) (Hart& & Mas-Coleil 2000) and Hedge (Cesa- Desa-BBianchi & Lugosi, 2006). In RM,
(R) where |:] = max(-.0
EisT f (F)))(()ss)/)))) (als)/E
"We use and infoset T, interchangeably in this paper.
3

---

Published as a conference paper at ICLR 2022
player selects an action with probability in proportion to its positive cumulative counterfactual regret. In Hedge, the policy (++1(a is decided according to:
(s.))
(at1(a Ea ("("))
(1)
If the player plays according to Hedge in state and n(s) = v 8log ((s)( Rg -
(s)) v [og(([(s)))TT7 (Cesa-Bianchi & Lugosi, 2006). In other words, the total regret grows sub-linearly with T, and therefore the average policy Tr (a|s) for both players converges to a NE.
THE MOTIVATION OF ACTOR-CRITIC HEDGE
In this section, we motivate ACH by introducing new neural-based CFR algorithm, NW-CFR, which employs neural network 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) used approximate the expectation of the sum of sampled advantages RV (s, a) == EEΣ A (s, a)]. ATM (s, a) set to A (s, a) if is visited at iteration & (given that only one trajectory is sampled at each iteration) and 0 otherwise. As result, the expectation E[AĀ* (s, a)] depends on both the advantage A (8, a) and the sampling policy μr at iteration k.
At the beginning of iteration I, suppose RG_ (s. a)) is well approximated by the output yalss; s;; 0z-1) of the policy net, parameterized as 0--1 in NW-CFR. The policy म, for iteration is first obtained via Hedge, i.e., softmaxing on (())y(aa) s;; 0,-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
then sampled into a buffer B. via self-play using the policy profile ne (Tp.:: -pp.t). Those samples in B, are used to train the action value net,
parameterized as w, by minimizing the squared loss: 1 {[Q(s, w; - GJ3, where G is the sampled return. A Afterwards, another M trajectories are sampled into buffer B, via self-play using another sampling policy profile f4: = (pp.e, -pp.). We use an additional behavioral policy My,t for the player p for more flexibility in the convergence (more details are provided in the next section). The policy is then optimized according to the loss function L E.ES L,, (5), where
M Ea 0) ly(a|s; 0c-1) + M i= 1l Il (s, if E... (s) - (v(alss 8) [b(aass; 0c11) + +0]2
(2)
otherwise,
where T; is the ith sampled trajectory in B,,. The next iteration of NW-CFR begins after the policy training finishes. The pseudocode of NW-CFR given in Algorithm 1. Note that we present NW-CFR from the perspective of player p. and the same procedure applies to the player -p. NW-CFR runs concurrently for both players and synchronizes at the beginning of each iteration.
A potential benefit of training the sampled advantage over the sampled instantaneous coun- terfactual regret (as done Brown et al. (2019), Li et al. (2020a), and Steinberger et al. (2020)) is that the variance of the sampled advantage could be much lower. As rf((s,) a) 1 A (s, a) (Srinivasan et al., 2018), the sampled instantancous counterfactual regret Ff a) is ff
(s)AA*( (s, = [ff. (s)] (s, where f%,* (s) is the probability of reaching considering only the contribution of pp,A- The larger variance (due to [ffx())) (s)] of 7% (s.a) a) may have negative influence on the performance when function approximation is used with only trajectory samples. This influence is magnified in large- scale games, as [f/* (s)] becomes large.
4 THEORETICAL PROPERTIES OF NW-CFR
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 R2 (8, a). which is type of weighted cumulative counterfactual regret. We then define 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 proven accordingly.
We can rewrite the NW-CFR policy loss (in Equation 2) at iteration t as Cs = Eses E. (v(asss) M
[y[a]ss; (((a)s;0,1)) + M Dem ser, A (x, 2) In other words, the target of y(a|s; 0) at iteration & is
4

---

Published as a conference paper at ICLR 2022
Algorithm 1: Neural-based Weighted CFR
Function Neurall 1 -based We Whith CFR (p. 7, M, w): wi <- w, 00 <- 0.
for 1 <- to do
# Obtain the policy: Ne + Softmax(((()ydddss...)))
# Train the action value net:
Reset B, 4- D.
for i 6 1 to M do
B, U, Train the loss B, (210(1, a;) G]²}
L Ti
Wt < w
# Train the policy net:
Reset B + 0.
for i < 1 to M do
L T~ SellPlay(Hp..: -pp.), B5 +- Bx UT:
Estimate (s, a), Va A(s), Vs E B as a;) E. m. (b)s))((ss bru)). Sum aggregate advantage A (F.(ss)) a) in B by state s. Train 8 on the loss E (s)}, where (s) defined in Equation
0: t- 0. # Save Be to policy buffer.
0(a(s;00-1) + 3/ EM A whose expectation is
Ere, m.k))
Σ
M BETE, (s,
E (a mdde
Σ A () (s, a).
Also, Ere ) SET, A** a) 1 (s) (s, (s, a), where fft (s) (s) ) is the reach- A
ing probability of state 8 at iteration k: Therefore, (s, a) = Ei=r (4 (s) ( (s, a). Since (s, = (6) (s, (Srinivasan et al., 2), have R8 E (s)r
As result, Re (s, multiples each instantaneous counterfactual regret with f (s). Without loss of generality, we define new family of CFR algorithms, weighted CFR, below. Afterwards, we present Theorem 1.
be viewed a type of weighted cumulative counterfactual regret that
Definition Weighted CFR follows the same procedure as the original CFR (Zinkevich al., 2008), except that the instantaneous counterfactual regret ri(s, a) is weighted by some weight we (s).. (s) > O and Ei= (x(ss) = Do. The original CFR is a type of weighted CFR with wr(s) = 1.0.
Theorem 1. NW-CFR is equivalent to a type of weighted CFR with Hedge when we(s) = ff' > O. given that enough trajectories are sampled and y(a|s; 0.) sufficiently close to R7 (s, a). Further, if ns(s) = /8In |As)) [[wn, (3) and wx(s) = 1 (8) E [wr(s), we (s)] C (0, 1], 1....,T, T, the average policy of the corresponding weighted CFR with Hedge and equivalently NW-CFR with (als))) ΣT [ (s)s(( (s), Vp P. has exploitability after T iterations, where
wh(s) (s) ws(s)
x S
In |n|
+
(3)
2T
wh(s)
SES
In Theorem we proved that the exploitability of NW-CFR bounded by Equation when yaass; (s; 0.) is sufficiently close to a). There are two terms in the bound. The first term converges to zero at the rate of O(2-1/2), and the second term is 0(1), which is weighted by the sum of the normalized range of the weights Eves (s) wy (s)) wn (s). However, it is possible to reduce the second term to an arbitrarily small value via tightening the range of fl. (s), which experimentally demonstrated in the Appendix D.
GGiven Jp.t at each iteration, could ohtain मp using the techniques introduced in Steinberger (2019).
5

---

Published as a conference paper at ICLR 2022
Corollary 1. If the behavioral policy for each player E P is constant across iterations, and f (s) > 0,Vs E S, t > 0, NW-CFR is equivalent to CFR with Hedge when y(a|s; 0t) is sufficiently close to (s.
As shown in Corollary 1, when the behavioral policy Mp.t for each player p E P is ic., wh (s) = ff)()) = (s), Vs E S,t > O, the second term of e in Equation 3 vanishes, and CFR with Hedge is recovered. All the proof' are given in the Appendix C.
5 ACH: A PRACTICAL IMPLEMENTATION OF NW-CFR
When applying NW-CFR to large-scale problems, two practical issues need to be addressed:
The average policy. Theorem 1 and Corollary state the convergence property of the average policy in NW-CER. Yet, as pointed out in Srinivasan et al. 22. Hennes et al. (2020), and Perolat 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; 0+) a biased estimation of Rf(s, (s. a). Yet, collecting non- con-sadledd 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 balance between theoretical soundness and practical efficiency. we provide practical implementation of NW-CFR, which is ACH. ACH adapts NW-CFR by training the current policy with entropy regularization 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 al., 2018)), trains the network with mini-batches, and handles asynchronous training with the importance ratio clipping of PPO. The behavior policy Mp.t is set to Tp.t 6 in ACH. More details of ACH are presented in the Appendix E.
RELATED WORK
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 number of hand-crafted features to approximate the regret. Deep CFR (Brown et al., 2019) is similar to regression CFR but employs neural network to approximate the regret. 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 regret 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 history-based critie, 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.
'In preliminary experiment presented in the Appendix F, we find that the performance of the current policy in ACH (trained with an entropy regularization) not sensitive the choice of pt.t-

---

Published as a conference paper at ICLR 2022
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 RPG minimizes a loss that is an upper bound on the regret after threshold, and the correspond- ing policy gradient is (s)
ACH.
-Ea VolQ(s, 0; w)) Es ((bls;))((s b; w]]+ However, RPG requires an 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,
well stud- ied model in evolutionary game theory (Gatti et al., 2013). The policy gradient in NeuRD is Vg NeuRD (s) = L. [oy(als; (). a; w) E. : ((ss))(ss. b; w)]. where y(a|s; f) 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 is 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.
7 EXPERIMENTAL STUDIES
We firstly introduce a I-on-1 Mahjong benchmark, on which we compare ACH with related state- of-the-art methods of similar computation complexity: PPO, RPG, and NeuRD. Since our goal is to approximate NE, the standard and default performance metric, exploitability. is employed. We approximate a lower bound on the exploitability of an agent 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 I 1-on-1 Mahjong. As complement, head-to-head performance of different methods on I-on-I 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 non-trivia poker game, i.e., heads-up Flop Hold' em Poker (FHP) (Brown et al., 2019) are presented. 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) given in the Appendix G. Note that results are reported for the current policy (of ACH, PPO, RPG, and NeuRD) and the average policy (of OS-DCFR and DREAM) respectively.
7.1 A 2-PLAYER ZERO-SUM SUM MAHJONG BENCHMARK
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 2-player zero-sum Mahjong benchmark, 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 in the Appendix A.I. 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 (the effects are explained the Appendix A.3), 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 1 Mahjong is around 10a1, compared to 10a 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.
7.2 RESULTS ON OUR 1-ON-1 MAHIONG BENCHMARK
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 PPO and shared the best setting for all methods. The advantage value is estimated by the Generalized Advantage Estimator (GAE(A)) (Schulman et al., 2016) for all methods. An overview of the paraee-rs 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 best response against each agent. The agent of
7

---

Published as a conference paper at ICLR 2022
Average Scores Losz
Average Scores Won
2-
6-
-2
P10 IP2
B75
Training Steps
Training Steps
(a) Approximate Lower Bound Exploitability
(b) Head-to-Head performance
Figure 1: (a): The training curves of the best response against each agent. Lower is better. (b): The training curves of each agent. The performance of an agent is evaluated by the average scores the agent wins against common rule-based agent. Higher is better. We report the mean solid curves and the range of the average scores across 5 independent runs as shaded regions.
each method selected at the le6th training step. Note that the agent fixed as a part of the 1-on-1 Mahjong environment when training the best response. We train the best response using PPO with the same aperrpaaameters that were used to train the PPO agent with self self-play. During the training of the best response, we evaluate the best response every 500 training steps using 10, 000 head-to-heal plays against each agent. According to the average scores each agent loses to its best response in Figure I(a), we may conclude that ACH is significantly more difficult to exploit than other methods in the large-scale l-on- 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 common rule-based agent' using 10, 000 head-to-hedd 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 Table 1, where all the agents are selected at the le6th training step. The agent of ACH wins all other agents by significant margin.
PPO
RPG
NeuRD
RPG
-0.21 + 0.05
NeuRD
-0.03 + 0.02
0.04
E 0.10
ACH
0.39 0.02
0.66
0.05
0.41
0.07
Table I: Mean (+: standard deviation) of the average winning scores of the row agents against the column agents. The statistics are estimated by independent runs (resulting different agents for each method). In each run, the average winning scores obtained via 10, 000 head-to-head plays.
Human Evaluation. We evaluate the agent, selected the le6th training step. of ACH against human players. First, the agent, named JueJong, roughly evaluated by playing over 7, 700 games against 157 practiced Mahjong players, where JucJong
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 the first 120 games but all plateau above O afterwards. More importantly, 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 p-value of 0.19 under one-tailed t-test. Hence, may conclude that Haihua Cheng failed to exploit JueJong effectively within 1, 000 games.
The rule-based agent is implemented such that it selects the action Hu, Ting, Kong, Chow, and Pong in descending priority whenever available and discards the tile that has the fewest neighbours.
8

---

Published as a conference paper at ICLR 2022
30
playeri playert playard
12
Has
Average Scores
Average Scores
10:
-6
120
160
200
200
400
600
800
1000
Number of Games
Number of Games
(a) Against practiced Mahjong players.
(b) Against the Mahjong champion.
Figure 2: Performance of JueJong against human players.
de ECFR GREAM
ABC
Exploitabiitty
ap1
Exploitability
Exploitability
227
05 DCEC DREAM
20
30
105
1041
Episodes
300
Samples consumed
Episodes
Figure 3: The exploitability on FHP, with the x-axis being the number of episodes generated (left and right) and the number of samples consumed (middle). We report the mean as solid curves and the range as shaded regions across independent runs. OS-DCFR and DREAM were run once as their performances are relatively stable, according to Brown et al. (2019) and Steinberger et al. (2020).
7.3 RESULTS ON THE FHP BENCHMARK
We further evaluate ACH and compare it with OS-DCFR, DREAM, A2C*, RPG, and NeuRD FHP. FHP is a simplified Heads-up Limit Texas Hold' em (HULH), which includes only the first two the four bettings in HULH. It is medium-sizee game with over 10 nodes and 10 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, follow the in the number of chips per game, where a big blind is 100 chips. All the hyper-parameet and the running enviromment are described in the Appendix H.2.
presented in Steinberger er al. (2020). The exploitability is measured
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 training 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 training complexity (A2C, RPG, and NeuRD), ACH converges significantly faster and achieves a lower exploitability.
CONCLUSIONS
In this paper, we investigated the problem of adapting policy gradient methods in deep RL to tackle large-scale IIG, i.c., 1-on-1 Mahjong. To this end, we developed new model-free actor-critic algorithm, i.e., ACH, for approximating a NE in large-scale IIGs. ACH memory and computation efficient, it uses only trajectory samples at the current iteration and requires computation of best response. ACH is theoretically justified as it is derived from a new neural-based CFR, i.e., NW-CFR, of which proved the convergence 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, 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. *PPO replaced with A2C in synchronous training environment.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
We thank the Mahjong champion Haihua Cheng for his efforts in this work. We appreciate the support from Tencent Mahjong (https: /mwgiamgaaanna/////aa/aaa.aa/aaa aq...qq....... com). We are grateful Tencent AI Arena (https: /aaaaeeaa. tencent. com) for providing the powerful computing capability to the experiments on 1-on-1 Mahjong.
REPRODUCIBILITY STATEMENT
The experiments on 1-on-1 Mahjong were run 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 code of the platform is not released currently but is planned be open sourced in the near future. The code of the 1-on-1 Mahjong benchmark is available at https: : //gi thub. com/ yata0 /Mah ong. The code of ACH is available at https: ///g thub. com Li twe i ng/ ACH_pokers All the theoretical results are presented in the main text, with all the proofs given in the Appendix C.
for all the experiments are listed in the Appendix H. All the
REFERENCES
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Christopher Hesse, and et al. Dota 2 with large scale deep reinforcement learning. CoRR, abs/1912.066800, 2019.
Noam Brown and Tuomas Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885-890, 2019.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International Conference on Machine Learning (ICML), pp. 793-802, 2019.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Trevor Davis, Martin Schmid, and Michael Bowling. Low-variance and zero-variame baselines for extensive-form games. In International Conference Machine Learning, pp. 2392-2401. PMLR, 2020.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning (ICML), volume 80, pp. 1406-1415, 2018.
Yoav Freund and Robert E Schapire. A decision-theorrtic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 1591):119-133 1997.
Sam Ganzfried and Tuomas Sandholm. Potential-aware imperfect-recall abstraction with earth mover's distance in imperfecttinffrmaaiie games. In Twenty-Eightt AAAI Conference on Artificial Intelligence, 2014.
Nicola Gatti, Fabio Panozzo, and Marcello Restelli. Efficient evolutionary dynamics with extensive- form games. In AAAI Conference on Artificial Intelligence, 2013.
Audrunas Gruslys, Marc Lanctot, Rémi Munos, Finbarr Timbers, Martin Schmid, Julien Pérolat, Dustin Morrill, Vinícius Flores Zambaldi, sean-Baptiste Lespiau, John Schultz, Mohammad Ghesh- laghi Azar, Michael Bowling, and Karl Tuyls. The advantage regret-matching actor-critic. CoRR, abs/2008. 12234, 2020.
Sergiu Hart and Andreu Mas-Colel A simple adaptive procedure leading to correlated equilibrium. Econometrica, 6875): 2000.
10

---

Published as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. CoRR, abs/1603.01121, 2016.
Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei, Rémi Munos, Julien Perolat, Mare Lanctot, Audrunas Gruslys, Jean-Baptiste Lespiau, Paavo Parmas, Edgar Dućñez-Guzmán, et al. Neural replicator dynamics: Multiagent learning via hedging policy gradients. In International Joint Conference Autonomous Agents and Multi-agent Systems (AAMAS), pp. 492-501, 2020.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML., pp- 448 448-456, 2015.
Michael Johanson, Neil Burch, Richard Valenzano, and Michael Bowling. Evaluating state-space abstractions extensive- games. Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, pp. 271 271-278, 2013.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint /4/2.6981 2014.
Mare Lanctot, Kevin Waugh, Martin Zinkevich, and Michael H. Bowling. Monte carlo sampling for regret minimization in extensive games. In Yoshua Bengio. Dale Schuurmans, John D. Lafferty, Christopher K. Williams, and Aron Culotta (eds.), Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pp. 1078-1086. Curran Associates, Inc., 2009.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In Advances Neural Information Processing Systems (NeurIPS), pp. 42034 2017.
Marc Lanctot, Edward Lockhart, Jean-Baptiste Lespiau, Vinícius Flores Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei. and et al. Openspiel: A framework for reinforcement learning in games. CoRR, abs/ abs//900..oo 09445, 2019.
Hui Li, Kailiang Hu, Shaohua Zhang, Yuan Qi, and Le Song. Double neural counterfactual regret minimization. In International Conference on Learning Representations (ICLR), 2020a.
Junjie Li, Sotetsu Koyamada, Qiwei Ye, Guoqing Liu, Chao Wang, Ruihan Yang. Li Zhao, Tao Qin, Tie-Yan Liu, and Hsiao-Wuce Hon. Suphx: Mastering mahjong with deep reinforcement learning. CoRR, abs/2003. 13590, 2020b.
Edward Lockhart, Mare Lanctot, Julien Pérolat, Jean-Baptise Lespiau, Dustin Morrill, Finbarr Timbers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by exploitability descent. In International Joint Conference on Artificial Intelligence (IJCAI), pp. 464-470, 2019.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning (ICML), pp. 1928-1937, 2016.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-57) 2017.
Julien Perolat, Remi Munos, dean-Baptiee Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pp. 8525-8535. PMLR, 2021.

---

Published as a conference paper at ICLR 2022
Martin Schmid, Neil Burch, Mare Lanctot, Matej Moraveik, Rudolf Kadlec, and Michael Bowling. Variance reduction in monte carlo counterfactual regret minimization (vr-meefr) for extensive form games using baselines. In Proceedings of the AAAI Conference Artificial Intelligence. volume 33, pp. 2157-2164, 2019.
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In International Confer- ence on Learning Representations, (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, Abs//177.00647, 2017.
Sriram Srinivasan, Mare Lanctot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environments. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3422-3435, 2018.
Eric Steinberger. Single deep counterfactual regret minimization. arXiv preprint vrXiv:1901.076:0 2019.
Eric Steinberger, Adam Lerer, and Noam Brown. DREAM: deep regret minimization with advantage baselines and model-free learning. CoRR,
2020.
Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour. Policy gradi- ent methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1057-1063, 1999.
Finbarr Timbers, Edward Lockhart, Martin Schmid, Mare Lanetot, and Michael Bowling. Approxi- mate exploitability: Learning a best response in large games. CoRR, abs/2004.09677, 2020.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre, Trevor Cai, and et al. John P. Agapiou and. Grandmaster level in StarCraft II using multi- aulti-agent reinforcement learning. Nature, 575(7782): 350-354, 2019.
Kevin Waugh, Martin Zinkevich, Michael Johanson, Morgan Kan, David Schnizlein, and Michael Bowling. A practical use of imperfect recall. In Eighth symposium on abstraction, reformulation, and approximation, 2009.
Kevin Waugh, Dustin Morrill, James Andrew Bagnell, and Michael H. Bowling. Solving games with functional regret estimation. In AAAI Conference Artificial Intelligence, pp. 2138-2145 2015.
Ronald J Williams. Simple statistical gradient algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4):229-255 256, 1992.
Deheng Ye, Guibin Chen, Wen Zhang, Sheng Chen, Bo Yuan. Bo Liu, Jia Chen, Zhao Liu, Fuhao Qiu, Hongsheng Yu, Yinyuting Yin, Bei Shi, Liang Wang, Tengfei Shi, Qiang Fu, Wei Yang, Lanxiao Huang, and Wei Liu. Towards playing full MOBA games with deep reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1729-17366 2008
12

---

Published as a conference paper at ICLR 2022
A INTRODUCTION OF THE 1-ON-1 MAHJONG BENCHMARK
Mahjong tile-based game that played world wide with many regional variations, such as Japanese Riichi Mahjong and Competition Mahjong. Like poker, Mahjong is IIG and is full of strategy, chance, and calculation. In this paper, we investigate a I-on-1 Mahjong game, whose information set size is much larger than poker, shown in Figure 4. The game rules of 1-on-1 Mahjong are similar to Competition Mahjong. The corresponding game, "2-player Mahjong Master", played by humans in Tencent mobile games (https: /mm jiang. qq com).
Information Set Size
4-Player Mahjong
10
1v1 Mahjong
10
Heads- Up
HULH
No-Limit Hold'em
10a
10
10T4
20
62
Information Set Count
Figure 4: The game complexity of Heads-up Limit Texas Hold' (HULH), Heads-up No-Limit Texas Hold' em, 1-on-1 Mabjong, and 4-Player Mahjong.
A.I
THE GAME RULES
Category
Name
Type
Copy
Count
Simples
Characters
36
Honors
Winds
16
Honors
Dragons
12
Bonus
Flowers
Bonus
Seasons
1
Figure 5: A list all tiles in the 1-on-1 Mahjong game.
There are 24 unique tiles and 72 tiles in total in the 1-on-I 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 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 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 tile from the deck wall, there 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, full description of which is listed in Table 2.
where the
13

---

Published as a conference paper at ICLR 2022
Type Discard
Description
#Action
Discard one of the tiles in the hand.
16
Make a meld of 3 identical tiles by seizing the opponent's 's latest discarded tile.
Pong
16
Make meld of 4 identical tiles when they are in the hand, and the Concealed-Kong is not revealed to the opponent.
Concealed-Kol Kong
16
Make a meld of 4 identical tiles by seizing the opponent's 's latest discarded tile.
Kong
16
Make meld of 4 identical tiles by
Add-Kong
16
adding a tile to his own exposed Pong.
Make meld of 3 character tiles in row by seizing the opponent's 's latest discarded tile. Give up the action of Pong, Chow, or Kong, and draw tile from the deck wall.
Chow
21
Draw
When there is only one tile away from a legal hand, the player
Ting
declare Ting.
Form a legal hand by drawing a tile or seizing the opponent's ' latest discarded tile. The Hu action ends the game.
Hu
Give up the action Hu. Afterwards, the player should select another legal action.
Pass-Hu
Table 2: Different actions in the 1-on-1 Mahjong game.
The goal of each player is to complete a legal hand prior to the opponent, by drawing tile or using the tile the opponent just discarded. A legal hand generally in the form of four melds and 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 Besides, a legal hand can belong to multiple categories, and the score of legal hand is the sum of points of corresponding categories. Legal hands with higher points are generally more difficult to form terms of either luck or strategy, and it critical for 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 tied. A flow chart the game is illustrated in Figure 6.
Category name Points
Pattern descriptions
Conflicts
Pure Double
Two identical sequences 3 character tiles.
Chow
Short Straight
hand with successive sequences.
Two Terminal
1
A hand with sequences 123 and 789.
Chows
Melded Kong
A hand with exposed quads.
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).
Edge Wait
A hand complction with the situation there is only one tile name to complete because you have the incomplete sequence lacking center (like 24 and 79).
Closed Wait
hand completion solely waiting on tile form pair.
Single Wait
Self Draw
A hand completion draw.
Whenever player draws flower season
Flower Tile
tile, this is counted as point.
10
Ready Hand
2
A hand that is one tile away from winning.
14

---

Published as a conference paper at ICLR 2022
11
Dragon Pung
2
A hand with a triplet or quad of dragon tile.
A hand without exposed melds and comple-
12
Concealed Hand
2
ted by seizing the discarded tile.
A hand with four sequences and a pair in characters.
13
All Chows
2
A hand with four same tiles, other than a melded quad.
Tile Hog
Two Concealed
15
2
hand with two concealed triplets or quads.
Pungs
16
Conccaled Kong
2
hand with a concealed quad.
A hand consisting of character 1, and
17
All Simples
2
honor tile.
A hand that includes terminals and honors in each meld, including the pair.
18
Outside Hand
4
Fully Concealed
A hand without exposed melds and comple- Self Draw
19
4
Hand
ted by drawing a tile.
Two Melded
20
4
A hand with two exposed quads.
Melded Kong
Kongs
Winning on a tile that is the last of its kind.
Last Tile
Three of other tiles on the table already revealed to all players.
Little Three
hand with two wind triplets or quads and wind pair.
22
Winds
23
All Pungs
6
A hand with four triplets quads.
hand consisting of character and honor tiles.
24
Half Flush
6
Two Dragon
A hand containing two dragon triplets or quads.
25
6
Dragon Pung
Pungs
Two Concealed
26
6
A hand containing two concealed quads.
Concealed Kong
Kongs
Every set in the hand must be completed with tiles discarded by other players.
27
Melded Hand
6
Single Wait
Out with
Hand completion with supplemental tile when you melding quad.
Self Draw
Replacement Tile
Winning off the tile that opponent adds a melded triplet(to create Kong).
Rob Kong
Last Tile
Tile
Winning off another player on the last tile (of the game).
30
8
Claim
Short Straight,
A hand with three sequences 123, 456 and 789 in characters.
31
Pure Straight
16
Two Terminal Chows
Three sequences in characters each shifted either one or two numbers up from the last, but not a combination both.
Pure Shifted
32
16
Chows
33
All Flowers
16
A player has or draws all flower tiles.
Flower Tiles
34
Full Flush
16
A hand consisting of only characters.
Three Concealed
Two Conccaled
16
A hand with three concealed quads or triplets.
Pungs
Pungs
Four Honour
24
hand with four honor triplets or quads.
All Pungs
Pungs
Big Three
Little Three Winds
37
24
hand with three winds be triplets quads.
Winds
15

---

Published as a conference paper at ICLR 2022
Concealed Hand,
Single Wait,
Seven Pairs
24
A hand with seven pairs.
Fully Concealed
Hand.
Pure Triple
Pure Double
24
hand with three identical sequences.
Chow
Chow
Pure Shifted
A hand with three number triplets quads with successive numbers.
Pure Triple
40
24
Pungs
Chow
Pure Shifted
Chows,
Four shifted number sequences, cach shifted either one or two numbers up from the last, but not combination both.
Short Straight,
Four Pure
41
32
Two Terminal
Shifted Chows
Chows,
Pure Double
Chow
Two Melded
Kongs, Melded
42
Three Kongs
32
A hand with three quad melds.
Kong, Two
Concealed Kongs,
Concealed Kong
All Terminals
A hand consisting of only terminal and honor tiles.
All Pungs,
43
32
and Honours
Outside Hand
Heavenly Ready
A hand that one tile away from winning at the beginning of the game.
Ready Hand
Hand
Pure Triple
Chow,
Tile Hog,
Pure Double
45
Quadruple Chow
48
A hand with four identical sequences.
Chow,
Two Terminal
Chow,
Pure Shifted
Pungs
Pure Shifted
Pungs,
Four Pure Shifted Pungs
A hand with four character triplets quads with successive numbers.
46
48
Pure Triple
Chow.
All Pungs
Seven Pairs,
Concealed Hand,
Four Winds
Seven pairs hand with four different wind pairs.
Single Wait,
Seven Pairs
Fully Conecaled
Hand
Seven Pairs,
Conccaled Hand,
Three Dragons
Seven pairs hand with three different dragon pairs.
48
48
Single Wait.
Seven Pairs
Fully Concealed
Hand
Big Three
Little Four Winds
hand with three winds triplets or quads, and the last wind be pair.
Winds,
64
Little Three
Winds
16

---

Published as a conference paper at ICLR 2022
Two Dragon
Little Three
A hand with two dragons be triplets or quads, and the last dragon be pair.
50
64
Pungs,
Dragons
Dragon Pung
All Terminals
And Honours,
All Pungs,
51
All Honours
64
A hand consisting of only honor tiles.
Four Honour
Pungs.
Outside Hand
Concealed Hand,
All Pungs,
Three Conccaled
Four Concealed Pungs
Pungs,
64
hand with four concealed triplets or quads.
Two Conccaled
Pungs.
Fully Concealed
Hand
All Chows,
Seven Pairs,
Full Flush,
Pure Terminal Chows
A hand with two Two Terminal Chows and
Pure Double
a pair of number character.
Chow,
Two Terminal
Chows
All Pungs,
Little Three
Winds,
Big Four Winds
A hand with triplets or quads of all four winds and an pair.
Big Three
Winds,
Four Honor
Pungs
Dragon Pung,
Big Three Dragons
A hand with triplets quads of all three dragons.
55
88
Two Dragon
Pungs
Full Flush,
Collecting number tiles 11 111455677899 without melding, and completing with any tile of characters.
Concealed Hand,
56
Nine Gates
88
Fully Concealed
Hand
Three Kongs,
Two Melded
Kongs,
Melded Kong,
57
Four Kongs
88
A hand with four quad melds.
Single Wait,
Concealed Kong.
Two Concealed
Kongs,
All Pungs
Seven Pairs,
Single Wait,
Seven Shifted
Seven pairs hand with successive numbers in characters.
Concealed Hand,
58
88
Pairs
Full Flush,
Fully Conccaled
Hand
17

---

Published as a conference paper at ICLR 2022
A hand consisting of character tiles of 6,
59
Upper Four
88
Seven Pairs
7, 8 or 9
A hand consisting of character tiles of 1,
60
Lower Four
88
Seven Pairs
2, 3 or 4
Seven Pairs,
Four Winds
Seven Pairs,
Three Dragons
Seven Pairs,
Big Seven Honours
Seven pairs hand with four different wind pairs and three different dragon pairs.
61
88
Outside Hand,
Single Wait,
Concealed Hand,
Fully Concealed Hand,
All Honours
The dealer draws winning hand the beginning of the game.
Self Draw, Concealed Hand
62
Heavenly Hand
88
A player completes a winning hand with the dealer's 's first discard and in most variants, provided the dealer does not draw a quad.
Self Draw,
63
Earthly Hand
88
Concealed Hand
A player completes a winning hand with the opponent player's first discard. And before that any action of Chow, Pong or Kong is not available.
Humanly Hand
88
Table The categories of legal hands in ascending order of corresponding points. The winning points of legal hand are obtained by summing the points of the matched categories reverse order while excluding the conflict categories.
A.2 THE STATE AND ACTION SPACE
The state space size of 1-on-1 Mahjong, shown the infoset count in Figure approximately 1074. Yet, the state space of l-on-1 Mahjong is not as easily abstracted as in poker. The primary reason is that single tile difference in the state could significantly impact the policy, e.g., making a legal hand illegal and vice versa. In contrast, states that have similar strength in poker could share common policy. For instance, the optimal preflop policy could very similar for "Ace-Fourr and "Ace-Thhee" in poker. Another reason is that state in 1-on-1 Mahjong is divided into different information groups, as demonstrated Figure 7()). 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 105 different actions in total, demonstrated in Table 2. The number of legal actions in state is relatively small compared to poker. Yet, the game length in 1-on-1 Mahjong is larger than that in poker. Players 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 1-on-1 Mahjong may vary more significantly than that in poker.
A.3 THE EFFECTS OF A LARGER INFOSET SIZE AND A LONGER GAME LENGTH
As shown in Figure 4, 1-on-1 Mahjong has larger infoset size than poker. The infoset size does not seem to have an influence on the convergence a tabular CFR (Zinkevich et al., 2008). However, when trajectory sampling and function approximation used together, the situation may be different. To be more specific, in a trajectory sampling algorithm. the variance of the sampled instantancous counterfactual value (regret) of larger infoset may tend be higher, which may have a large
18

---

Published as a conference paper at ICLR 2022
1-j
Pj selects legal action
yes
Hu?
Game starts
Is Chow
Deal cards for Po,
i=0
yes
Pong?
no
P; draws tile
Is Kong" no
P selects legal action
No tiles?
yes
Is Hu?
draws tile
no
yes
Concealed-Kong?
selects a legal action
yes
Hu? no
discards a tile
Is Concealed-Kong Add-Kong?
Game ends
no
Pr discards tile
Figure 6: flow chart of the 1-on-1 Mahjong game.
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 sample multiple actions in state very common in the literature. Yet, sampling multiple actions consistently game trees with long episodes is certainly prohibitive, the number of samples goes exponentially with the game length. 1-on-1 Mahjong has maximal game length about 40, which may be daunting for methods that try to sample multiple actions in state. In other words, 1-on-1 Mahjong may complementary poker in evaluating algorithms when only trajectory samples are allowed.
B THE MODEL DESIGN OF OUR 1-ON-1 MAHJONG AGENT JUEJONG
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 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 overview of the model design of JueJong.
19

---

Published as a conference paper at ICLR 2022
1tt
Kt Rird 1M
O
0
0
0
0
0
0
R7
Stage
Value net
Image Bae Restures
R asttuci bock
P1 ready action...
R Rssiinal back
Transiton
Policy
Region
Feature
Dim
Posidon
[2.1]
CIP
ready
Bullin
Las: action (2.155)
Figure 7: (a) The graphical user interface of 1-on-1 Mahjong with marked regions representing different groups of information, which are encoded in either image- like features or one-hot features. (b) The image-like feature encoding scheme. (c) The model architecture design.
The marked regions in Figure 7(a) summarize the information agent can observe. Regions 1 to 7 are encoded in image-like features, which represent the player's 's hand, the player's Chow, Pong, and Kong, the player's concealed-Kont Kongg, the player's Discard, the opponent's Chow, Pong, and Kong, the opponent's 's concealed- Kong, and the opponent's Discard respectively. A feature map, as shown in Figure 7(b), of height and width 17 is employed, where a or in the ith row and jth column means whether there are tiles of the jth type in the input set of tiles. Therefore, single or two successive convolutional layers with 3 x kernels efficiently derive row and column combinations. Note that, in Suphx (Li et al., 2020b), the feature maps are one-dimensional vectors, where 1 x 3 kernels are used. The black tile in Figure 7(b) is designed exclusively for Region 6 to indicate how many concealed- -ongg 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 concatenated in the channel dimension, and therefore the final image-like like features are in the shape of x 17 x 53 (h x w x c).
Regions 8 to 11 encoded in one-hot features, which represent the player's position (0 or 1), the is is_ready state of both players, and the bonus tiles of both players. Additionally, the last action (not shown as region in Figure 7(a)) for each player is encoded in one-hot feature vector 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 x 3. The transition layers are point- wise convolutions that scale the number of output channels to 64, 128, and 32, respectively for each stage. Subsequently. the transformed image-like features are reshaped to 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, apply batch normalization (loffe & Szegedy, 2015) and ReLU non-line non-linearity after all convolutional layers and fully-conmected layers.
C THEORETICAL PROPERTIES OF NW-CFR
C. PROOF FOR THEOREM
In order to prove Theorem first prove the following Lemma.
20

---

Published as a conference paper at ICLR 2022
Lemma 1. For weighted CFR, w((s [ur(s), un (s)], wi(s) 2 (s) S then
miX R (s, (w)(s)
A(s))A
max DEA(s)
a(s,a) -
(4)
(s)
ww (s)
Proof. First, for any state & E S and action a E A(s), we have
R2 (s, a) wr(s)r((ssa)
(s))))r((s.o)
Σ
(5)
krrE(e,)200
Warg (,,0)<00
Σ
(s.
So,
(s, (s) Σ (s) (wnl(s) wi(())
E
(s,
(6)
In other words,
Ry (s,
wh(s) wi(s) wh (8)
a)
Σ
(s,
wn(s)
k=1
Mong (s.a)20
So,
max R, (s,
(wn(s) (1())) wn
a()
max (
Wp (8)
Then we can prove the Theorem:
Proof. For NW-CFR, the policy at iteration / is generated according Hedge:
T1(8, En. _ (600)
(9)
where
R (s,a) Σ fom (s)r((s,a). k=1
(10)
Meanwhile, weighted CFR with Hedge generates policy at iteration according to
Tr(3, a) Ea ([) (8.00)
(11)
where
(8, Σ (x(3))
(12)
So, when (s) = 1 (s) w)(s) > 0 for any E S and l: >> O. NW-CFR and weighted CFR with Hedge generate 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
(T) = Σ
(s.0)
(13)
aE.A(s)
21

---

Published as a conference paper at ICLR 2022
We have
Si
In Σ (o(o) - In (A((s)
In
S
aEA((s)
2 In
max e (s,a) In [A(s) (E.A(s))
(14)
=1(s)
max Rg (8, a) In [ns))s)]. #EA(s)
Meanwhile, for each t = ,t...,t
EmEA(s) (l.l)
S
In
In
S
EoEA(o) e
(15)
= In
Σ aEA((s)
(M (elts)))esss
Since
2² a)
LE . SEX +
(16)
8
S $
S (78)) Σ ((( (s)
In
(17)
aEA((s)
Note that (8, { a) - EneA(s) (L So
Σ m((s:))u((0)(((ss)))= 0.
(18)
aEA(s)
Therefore,
S
())) Ei=1 wx())
In
S
(19)
5
8
So,
(s8) max R (s, - In|((s)) - (s) Ei= (2)
(00)
aEA(s)
i.c.,
max RT In|A(s) aEA(s)
(s)) El_ (
(21)
n(s)
8
According to Lemma 1,
In Ass)
A))) Et wf(ss
+ (wn(s) - ws
max (8 a) aEA((s)
(22)
71)) (S)) (s)
8wh (s)
W/.
When v7s) = 8ln [A(s) / [wN (8) (8)T] and w. wx)ss [10T)),, wn(s)] C (0, 10,11 I,...,T. T.
we have
In A
(wn(s) (s
(7 a) SV aEA(s)
max
2
(8)
(23)
(w) AT
<A
2 In [(s)|
(s)s)
According to Theorem 2 in Zinkevich et al. (2008), the total regret
Rr
Σ max aEA(s)
(s.a)++
T
+ (wn(s) w/ (s))s))1))
A
[A(ss)+++
(1(s))
(24)
.ES
T
w/ (s) wr
<|SIA
In |A|
AT
2
Wp. (s)
22

---

Published as a conference paper at ICLR 2022
As result, according the folk theorem in Zinkevich et al. (2008), the average policy has exploitability, where
R..T
wr
=
In A +
(25)
P
T
2T
(h(s)
PEP
SES
C.2 PROOF FOR COROLLARY
Proof. When the behavioral policy Pp.k of each player p iss constant across iterations Ak > the reaching probability fy (8) of any state E S is also constant. Assume 1 (s) = w(s), then,
P Σ (f) w(s) a)) R
(26)
In other words, R2 (s, a) is equal to the cumulative counterfactual regret scaled by a time-invariant weight w(s). Hence, the policy iteration is
(3(5))())A(((.a)
edd (s))))
T (a|s) = En ellow(asltt (s,aa)
(27)
Σn (s) 1(xa²))
where the new (s) is set to / (()) As a result, for constant jp.k. NW-CFR is equivalent to CFR with Hedge when y(als; 0%) is sufficiently close to R2 a). Furthermore, since wi(s) = ft' (s) = wo, (s), the second term Equation 25 vanishes, i.e.,
|S|Al In |A|.
(28)
As result, the exploitability bound of CFR with Hedge is recovered.
D EXPERIMENTAL RESULTS OF THE WEIGHTED CFR
As stated in Section 5, ACH is practical implementation of NW-CFR, which is straightforward neural extension to the weighted CFR defined Definition 1, together with wx(s) f/ (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 we (s(s) by varying Mp,t. since f/ (s) depends only on Hp.t- Note that the weighted CFR traverses the full game tree every iteration and that Pp.t is only used to calculate the state reaching probability f/ (s). We test these algorithms on three small IIGs in OpenSpiel: Kuhn poker, Ledue poker, and Liar's Dice.
CrRihldgel Curenus..) Cumuri6..)
cratreddel
Explitabitty
16-1
Exploitabbiit
Camanndus Cammaniiiaa)
Iity
Cur
Cun amiim
10m1
Current
Curnens
20
30-1
10.
Loo0 u25 iss0 ardo
1755
:250 1550 2r5a
Iterations
Itorations
Iterations
(a) Kuhn poker
(b) Ledue poker
(c) Liar's Dice
Figure 8: Exploitability of the weighted CFR with wy(s) = f (s) and CFR (i.e., the weighted CFR with (s) 1.0). The probability f/' (s) is determined by the behavior policy pp.c. The setting of Mp,t for each line is given in the legend, which "Uniform" means Pp.e(s) the uniform policy; "Current" means (s) (s); "Current(r)" means (s))(s) zUniform + (1 - (.)ss. Note that the exploitability is reported with regard to the average policy.
As shown in Figure 8, the weighted CFR with w, (s) induced by a stationary Hp.. (i.e., the uniform policy) converges the same pace with CFR(Hedge). As result, Corollary is verified on the three
23

---

Published as a conference paper at ICLR 2022
small benchmarks. Also, as Theorem I states, the exploitability of the weighted CFR is influenced by the range of wy(s) = (s). This is experimentally demonstrated in Figure 8 by setting Up. to mixed policy between the current policy Tp.t and the uniform policy. We can see that the weighted CFR still performs competitively with CFR(Hedge), when (p.((*) = 0.5Uniform + p.5m
E ACH: A PRACTICAL IMPLEMENTATION OF NW-CFR
To address the practical issues mentioned in Section we provide a practical and parallel implemen- tation of NW-CFR, i.e,, ACH, which employs framework of decoupled acting and learning, similar to IMPALA (Espeholt et al., 2018). ACH maintains a policy net y(a|s; 0) and a value net (s;:w), where 0 and w share large portion of parameters (see Figure 7). Both players use the same 9 and w. We do not use an additional time-invariant behavioral policy for sampling actions. Instead, we the current policy Te, i.e., pp,t TT,t Vp E P. As result, can the same samples train both the value net and the policy net. Also, n)(s) is incorporated into the learned target value in the policy net, so the policy π (a]s) obtained by directly softmaxing on y(a|s;
The advantage A(s,a) a) is estimated by GAE(A) (Schulman et al., 2016), using sampled rewards and (ss w), 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 result, the policy loss reduces to -. (s) m7(s) v(a s;0)
(ala(a)s) A(a, 8).
where [afa] accounts for the fact that the action a was sampled using (als))) ACH handles asynchronous training with the importance ratio clipping [1 1-& E, + a| of PPO (Schulman al., 2017). To avoid numerical issues, the mean V(. (s; is subtracted from the policy output, which is then clipped within a range [-1th 1 The pseudocode of ACH is given in Algorithm 2.
Algorithm 2: ACH
Initialize the policy and critic parameters: 0 and w. Start multiple actor and leamner threads in parallel.
Actors:
while true do
Fetch the latest model from the learners.
Generate samples via self-play in the form: [u, 8, A(s, a), G, (a)a(a)s)]-
Send the samples to the replay buffer.
Learners:
for / E 2, do
Fetch a mini-batch of samples from the replay buffer.
Leum = 0.
for each sample (a, s, A(s, a), G, Tota (a s)] E the mini-batch do
{f a(a s:0)
1 + (y((asss 8) - 0(11s;0) < 1d
if A(A a) 2 0, if A(s, a) < <.
(ala(als)
[f alaa s:P)
> 1 {] 7(- 1
Futa(o]s)
Crum += cn(ss) x(a)=:)) A(a, ((;(s - G) + و + (als;; 0) log (ags(());))
(als)
Update 0 and once using gradient on Lsum.
We employ an entropy loss to encourage exploration during training and hopefully the convergence of current policy NE (Srinivasan et al., 2018). ACH updates 0 and simultaneously, and the overall loss is:
0(als:0) 0) A(a,s) o [V(s:)) 20 + 3 Σ T(als; log ())
LACH = on(s) =n((s)
(29)
Tola(a)s)
Theoretically, y(a ss; ()) for nampled states s' should also be trained with the target y(a s'; fota). Yet. in ACH, we only update once using single mini-batch at each iteration. Therefore, & is equal to Ootd before the update. In other words, the policy loss for non-sampled states is 0 in ACH.
24

---

Published as a conference paper at ICLR 2022
ACH(Uniform) ACH(Curmnnt
10a
Exploitabliin
10º
Episodes
1e8
Figure 9: The exploitability of the current policy in ACH with different behavior policies on FHP. We report the mean as solid curves and the range as shaded regions across independent runs.
F THE EFFECT OF THE BEHAVIOR POLICY ON ACH IN FHP
As we noted in the paper, the behavior policy ppp. in ACH could be set to either the current policy Tp. simply a uniform sampling policy. As Corollary states, tighter bound the exploitability of the average policy of NW-CFR can be obtained, if /pp.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 theoretical perspective. Hence, we conduct an experiment to investigate this using FHP, which is a non-trivial poker benchmark but still has the property that the exact exploitability of an agent can be efficiently computed.
In Figure we compare the exploitability of the current policy ACH on FHP, by setting the behavior policy in ACH to either the current policy or uniform sampling policy. From the comparison, it seems that the performance of the current policy of ACH is not sensitive to the choice of behavior policy. One reason might be that the additional entropy loss forces the current policy to be stable and prone to a uniform random policy. Another reason might be that the current policy instead of the average policy is evaluated. We will investigate this in more depth in the future.
G ADDITIONAL RESULTS ON SMALL IIG BENCHMARKS IN OPENSPIEL
We further evaluate ACH and compare it with A2C, RPG, and NeuRD on three benchmarks from OpenSpiel: Kuhn poker, Ledue poker, and Liar's Dice. All the experiments were run dingle-threade on 2.24GHz CPU. We use the network architecture provided in OpenSpiel, which has a 128- neurons fully-connected 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-paramen parameters in OpenSpiel. ACH shares most of the Appendix H.3.
with A2C. All the hyper-parameters are listed in the
The exploitability of agent is exactly caleulated 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 10. Clearly, ACH converges significantly faster and achieves 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 policy instead of the average policy for the evaluation. As expected, A2C has the worst performance, since 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 of the three benchmarks.
As complement, also present the head-to-hee performance of A2C, RPG, NeuRD, and ACH on the three benchmarks in OpenSpiel. As demonstrated in Table 4, the agent of ACH won all other agents across the three benchmarks.
25

---

Published as a conference paper at ICLR 2022
Ac
2:1
ML
1.0
Expleitablliy
2.0
68
0.3
2-3
64
60
A6
10
02
0.4
3/3
00
42
64
Training Steps
Training Steps
Training Steps
(a) Kuhn poker
(h) Ledue poker
(c) Liar's Dice
Figure 10: The training curves of each agent on the three benchmarks from OpenSpiel. We report the mean solid curves and the range of the exploitability across 8 independent runs shaded regions. We notice that there exists some discrepancy between the NeuRD results on Kuhn poker and Ledue poker reported here and those reported in Hennes al. (2020) and Lanctot al. (2019). The reason might be due to NeuRD's sensitivity to running environments including hyper-parameters and random seeds.
Kuhn poker
Leduc poker
Liars Dice
A2C
RPG
NeuRD
A2C
RPG
NeuRD
A2C
RPG
NeuRD
RPG
-0.024=0.20
0.521+0.23
0.192+0,14
NeuRD
-0.0%6=0. 16
0.087=0.16 16
0.569 16
10.10800.17
40.226+0.05
-0.355+0.1 12
ACH
0.104:0.05
0.115=0.05
0.118=0.05
0,495
0.050+0.14 14 0.117H0.15
0.275:+005
0.122#0.05
0.407=0.06
Table Mean (+ standard deviation) of the average winning scores of the row agents against the column agents. The mean and the standard deviation are estimated by 8 independent runs. In each run, the average winning scores are obtained 10, 000 head-to-head plays. All the agents are selected at the 1e7th training step.
H HYPER-PARAMETERS
H.1 HYPER-PARAMETER FOR THE 1-ON-1 MAHJONG EXPERIMENT
We used the Adam optimizer (Kingma & Ba, 2014) for the experiments on the 1-on-1 Mahjong benchmark. We performed mild parameerr search on PPO and used the best setting for the shared hyper-parameters of all methods (PPO, RPG, NeuRD, and ACH). Table gives an overview of hyper-parameters for each method. Also, report the performance of the current policy, instead of the average policy, for each method.
Parameter
Range
Best
Shared
Ratio clip (E)
0.5
GAE (A)
0.95
Learning rate
1 2.5e-4)
2.5e-4
Discount factor (7)
0.995
Value loss coefficient (a)
0.5
Entropy coefficient (3)
(le-1, 1e-2)
le-2
Batch size
{4096, 8192]
8192
NeuRD
Logit threshold (1th)
6.0
ACH
Logit threshold (1th)
6.0
Hedge coefficient (n(s))
{1.0, 1e-1)
1.0
Table 5: The Syper-parameetrs used for the 1-on-1 Mahjong experiment.
26

---

Published as a conference paper at ICLR 2022
H.2 HYPER- PARAMETERS FOR THE FHP EXPERIMENT
We used the Adam optimizer (Kingma & Ba, 2014) for the experiments on FHP. All the experiments on FHP were run muuli-threader and synchronously using ten 2. 2.24GHz CPUs. We update the neural networks of ACH and other methods (A2C, RPG, and NeuRD) every 1000 episodes, with batch consisting all the samples collected within the latest 1000 episodes. Since the average game length of search for
FHP is around 2, the batch size is roughly 2000. We performed mild ACH, A2C, RPG, and NeuRD, as shown in Table Note that we do not need to clip the advantages in synchronous method, the ratio clip hyper-parameter is not needed. We multiply the rewards in FHP with a reward normalizer, as the rewards in FHP are in the range [-700, 700]. Besides, we found that A2C, RPG, and NeuRD are very sensitive the entropy coefficient, and had to use larger entropy coefficient in these algorithms than ACH. For OS-DCFR and DREAM, we use the same typer-parameters presented in Steinberger al. (2020). An overview of the hyper-parameters on FHP is given in Table 6. Note that we report the performance of the current policy for ACH, A2C, RPG, and NeuRD, while the average policy used for evaluation in OS-DCFR and DREAM.
Parameter
Range
Best
Shared
GAE (A)
0.95
Learning rate
(le-3, le-4)
le-4
Discount factor (7)
0.995
Value loss coefficient (a:)
2.0
Batch size
2 2000
Entropy coefficient (8)
{le-2, 3e-2, 5e-2)
5e-2
Reward normalizer
0.002
NeuRD
Logit threshold (1t))
12 4.0)
2.0
ACH
Logit threshold (1th)
(2.0, 4.0)
2.0
Entropy coefficient (8)
[le-2, 3e-2, 5e-2)
3e-2
Hedge coefficient (1)(s)
{1.0, 0.1)
1.0
Table 6: The hyper-parameters used for the FHP experiment.
H.3 HYPER-PARAMERR PARAMETERS FOR THE EXPERIMENT ON OPENSPIRI.
We used stochastic gradient descent with constant learning for all the experiments bench- marks from OpenSpiel. For A2C and RPG, we used the default implementations and hyper-parameters in OpenSpiel. NeuRD was originally implemented using the counterfactual regret 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 the current policy to NE. Also, we report the performance of the current policy, instead of the average policy, for each method.
Parameter
Range
Best
Learning rate
[1e-3, 5e-3)
le-3
Value loss coefficient (a)
{1.0, 2.0]
2.0
Hedge coefficient (77(s)
(1.0, 1c-1, 1c-2)
1.0
Table The hyper-parameter search ranges and best settings of ACH for the OpenSpiel experiment.
In the OpenSpiel implementations, 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 combined in ACH, and all parameters are updated simultaneously, as illustrated in Algorithm 2.
27

---

Published as a conference paper at ICLR 2022
Parameter
A2C
RPG
NeuRD
ACH
Batch size
64
64
64
Critic learning rate
le-4
le-2
le-2
Policy learning rate
le-4
le-2
le-2
# Critic updates per policy update
32
32
32
Entropy coefficient (5)
le-2
le-2
le-2
1e-2
Logit threshold (lth)
2.0
2.0
Table The hyper- sypereparammters used for the OpenSpiel experiment.
Also note that, in a single-threaded training environment, the actor and the learner run in sequence. As result, [a]ss; 0) is always identical to Tois(als) in ACH in Algorithm 2.
We performed a mild hyper-parameter search for ACH, which is illustrated in Table 7. The final syper-parameter used for each method are listed in Table with 3 additional parammtrrs of ACH listed in the "Best" column in Table 7.
1 THE RELATIONSHIP BETWEEN ACH AND SUPHX
Recently, Suphx (Li et al., 2020b) has achieved stunning performance on Japanese Riichi Mahjong. The development of Suphx is enabled by novel integration of existing supervised learning and RI. 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 1-on-1 Mahjong setting (only one round per game our test setting). The oracle guiding technique decays the invisible feature during training, which is of independent interest in dealing with imperfect- information. The run-time policy adaptation technique adapts the trained policy at test time, and this may be combined with ACH, which is training algorithm. In summary, Suphx is more of novel system than a new algorithm. For this reason, we did not implement and compare Suphx with ACH in our I-on-l Mahjong experiment. Nonetheless, the oracle guiding technique may be complementary to ACH in handling imperfectt-informatonn and we will investigate this in future work.
28


Reviews:
[{"review_id": "iaKDPetoNIb", "reviewer": "Reviewer_m118", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has a number of strong things to recommend it. The Mahjong results are impressive.  While there a couple of questions below regarding the experiments, in general the experimental design was thorough and reasonable metrics were used. There are, however, a few issues that stand out.\n\nA: \"In Theorem 1, we proved that the exploitability of ACH is bounded by when y(a|s; θ t ) is sufficiently close to R t a (s, a)\"\nTheorem 1 shows a bound on the average policy, which ACH says nothing about tracking. Adding some mechanism for computing an average policy is a non-trivial portion of many of the algorithms in the related work section, and the reason that they could possibly be considered \"memory intensive\" as noted. Without that, the average online regret experienced in selfplay by ACH might be sublinear, but the policy has no guarantee on exploitability.\n\nB: Algorithm 1 (or other text in the main body) does not include the additional entropy term used in the evaluation. As discussed in the cited work of Hennes et al. (and the work by Perolat et al. that it cites) this is a non-trivial detail in the context of selfplay convergence, and should be directly included in the discussion and pseudocode.\n\nC: There looks to be a mismatch in the experimental results for Kuhn poker and Leduc poker between NeuRD in this paper and in the Hennes et al. paper. Pulling results off of Figure 3 in this paper and Figure 6 of Hennes et al, for Kuhn poker it looks like ~0.2 at 1.5*10^6 iterations vs ~0.03 at 10^5 iterations. There is a smaller mismatch but still non-trivial difference in Leduc poker, with ~0.6 at 2*10^6 iterations vs ~0.4 at 3*10^5 iterations.\nSome differences are not necessarily unreasonable, given differences in batch size and other parameters: all algorithms tested in this paper might be expected to improve with more time spent tuning parameters. However, a non-trivial mis-tuning makes it hard to accept the claim that \"Clearly, ACH converges significantly faster and achieves a lower exploitability\".\n\n\nThere are a number of other smaller issues and questions.\n\n\"solve a large-scale two-player zero-sum imperfect-information game\"\nMahjong is not solved. This claim in the abstract and conclusion needs to be re-worked.\n\n\"An optimal solution to an IIG usually refers to a Nash Equilibrium (NE)\"\nThe scope of this statement should be narrowed, maybe something like  \"... optimal solution to a competitive IIG ...\". A NE in a cooperative game is usually uninteresting and can be arbitrarily bad with respect to shared utility. For example, a babbling equilibrium in communication games.\n\n\"information set size much larger than poker\"\nThe difference in size is mentioned a number times, including both the abstract and conclusion. This would seem to indicate the authors see it as an important quantity, but there is no corresponding detailed discussion of the effects. Why should the reader care about the size of an information set, rather than the number of information sets (corresponding to RL agent states) or possible histories (RL environment states)?\n\n\"We are interested in methods that are model-free, i.e., using only trajectory samples to learn, as it is often infeasible to sample multiple if not all actions for each state in large-scale IIGs.\"\nThe sentence should be modified so it is clear what state means here. State = agent state / information set? State = environment state / history / game state?\nAlso consider clarifying the motivation here. Why is the number of actions being sampled tied tied to being model-free? A model-free method certainly advances through an episode with a single action, although it might consider all actions. A model-based method can also operate on one or more sampled trajectories through a game, using the game knowledge as it considers all actions (e.g., Monte Carlo CFR methods). One suggestion would be eliminating the justification given in the text: it is reasonable to just be interested in methods that are model-free.\n\n\"Also, we employ deep neural networks to generalize across states without any abstraction, since the state or action abstraction in 1v1 Mahjong is not as straightforward as in Poker, which is explained in the Appendix.\"\nAs written, the statement implies that the authors would use state or action abstraction if they were able to do so. Is that true? If so, why? Function approximation would seem to be a more general mapping than a state aggregation. If that's not what the authors intend, consider rewriting to clarify. \n\n\"for approaching a NE in 2-player large-scale IIGs\"\n\"... 2-player zero-sum ...\"\n\n\"We build a 1v1 Mahjong bot, named JueJong, based on a novel neural architecture design and ACH\"\nConsider dropping \"a novel neural architecture design\". At some level, every NN architecture proposed for every instance of every problem is novel. If it's not significant enough to spend subtantial time discussing in the body of the text, it's not siginificant enough to make a claim of a novel architecture.\n\n\"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.\"\nConversely, RM is scale-invariant, and doesn't require parameter tuning the softmax temperature, which can have a large effect on the performance of Hedge. Was the choice of Hedge vs RM tested? If so, that would be useful information. If not, \"may be\" seems like a weak justification to switch away from common practice -- are there also other reasons, like ease of implementation in NN frameworks, or ease of theoretical arguments?\n\nHow is A^π_t(s,a) being computed? Q(s,a;ω) - π_t(s,.) Q^π_t(s,.;ω)? It would be helpful to state this explicitly, immediately before or after Equation 2 (or in it).\n\nL_π is a computationally intractable sum across all states and actions. Algorithm 1 shows an update sampling s from all states. How is s sampled here?\n\n\"Also, M trajectories are sampled according to µ k = (µ_p,k , π_−p,k) at each iteration to estimate E[Ã^π_k (s, a)].\"\nIs this a typo, or leftover text? k is no longer bound given that the prior paragraph is considering iteration t, and this seems to be the same definition as µ t. Or is this a third set of sampled trajectories used for estimating L_π? If so, don't we need a uniform sample across S given L_π is an unweighted sum across states and actions?\n\n\"As shown in Corollary 1, when the behavioral policy is time-invariant, i.e., w_h(s) = f_p^µ_t(s) = w_l(s), ∀s ∈ S, t > 0, the second term in  disappears, and CFR with Hedge is recovered.\"\nThe situations where the online learning policy for both learning players is stationary would seem to be limited in scope. Can the authors provide a non-degenerate example where this occurs?\n\n\"All the agents we evaluated below use the current policy instead of the average policy, as done in Srinivasan et al. (2018) and Hennes et al. (2020).\"\nRelated to issue B. Suggest re-wording this to something like \"the current policy with an entropy term to encourage convergence\". As is, the statement is technically correct, but feels like a mischaracterisation in spirit. Both papers, and especially Hennes et al., consider the dynamics of non-stationary policies, and are explicitly modifying the updates to use a single policy rather than just ignoring an averaging step. Most of the experiments in Hennes et al. -- figures 2 to 5? -- seem to be using an average policy.\n\n\"We train the best response using PPO with the same hyper-parameters that were used to train the PPO agent.\"\nThe static environment for the approximate best response might be qualitatively different than the non-stationary self-play environment, and require very different parameter choices. Can the authors provide the reader with any indication that the parameters used in all of the self play runs are also good choices for PPO-as-best-responder?\n\n\"According to the average scores each agent loses to its best response in Figure 1(a), we can conclude that ACH is significantly less exploitable than other methods in the large-scale 1v1 Mahjong environment.\"\nThis statement needs to be weakened slightly, given the approximate exploitability results are lower bounds on exploitability: we can certainly conclude that ACH is significantly harder to exploit, but not that it is less exploitable.\n\nIt is reasonable to skip comparisons against Suphx, given the slightly different domain, and a possibly non-general algorithm (not clear how it would be applied to Liars dice or the other small games?) However, as a method for generating a strong Mahjong agent, it seems worth mentioning Suphx within the related work section, rather than appearing in the final appendix.\n\n\n\"Poker\"\nThere are many variants of poker. Most attention in the literature has been on Texas hold'em poker. Also, the name of classic games like chess or poker are usually not capitalised, with a few exceptions like Go.\n\n\"in the Appendix\"\n\"in Appendix C\", \"in Appendix D\", ...  Help the reader out so they don't need to search the whole appendix.  Occurs multiple times in the paper.", "summary_of_the_paper": "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.\n", "summary_of_the_review": "Taking the core of this paper to be a general policy-gradient update rule for competitive imperfect information environments, with a demonstration of performance in a large game of interest to human players, there is the base of a strong submission. However, the additional theoretical analysis and empirical analysis of small games have a number of issues that do need to be corrected.\n\n\n------\nPost-discussion edit.\nThe authors have made numerous changes, and I have no remaining concerns with after the Nov 21 revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Vaeu1vWVrZ", "reviewer": "Reviewer_8wVT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "What I would like to see most in this paper is two things: more tabular analysis and experiments and better comparisons to existing methods. \n\nThis method is essentially doing regression on a weighted CFR. However, this weighted CFR is a new method (to my knowledge). What properties does it have compared to normal CFR? Can we run experiments with tabular weighted CFR and compare it to normal CFR? Why might we prefer weighted CFR to normal CFR? Answers to these questions would help answer other questions I have such as why didn’t the authors compare to Deep CFR/DREAM? The authors claim that they are not related because they are not a policy gradient method, but the proposed method isn’t really a policy gradient method either. In fact I find it closer to Deep CFR than to NeuRD/RPG, but I do see the similarities with those methods as well. \n\n\n", "summary_of_the_paper": "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. \n", "summary_of_the_review": "Overall I find the experiments against the top Mahjong player to be very compelling and am excited by this research direction. However, I think this paper skips some crucial steps in analyzing the tabular method that this is based on. If the authors are able to address this issue and explain why we would want to use this method vs. deep CFR/DREAM or compare to those methods then I would consider raising my score.   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "R88dBUMU52k", "reviewer": "Reviewer_Mmjs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Actor-Critic Policy Optimization in a Large-Scale Imperfect-Information Game \n\n\nPositive: \n\nI like that the paper uses 1v1 Mahjong, sounds like an interesting game that is not commonly used in the community. It is also great that the authors approximate exploitability in the large game using a RL method. Furthermore, the prior work is relatively well cited.\n\n\nMinor Issues:\n\n1) You are missing DeepStack in your introduction, where you list non-tabular methods for large imperfect information games.\n\n2) Corollary 1. Has little very unrealistic assumptions. The current policy is rarely stationary (if it was, often a simple policy gradient method would converge).\n\nMain Issues:\n\n\n1) My biggest issue with this paper is the proper comparison to prior work  (both in terms of experiments and comparing the methods).\n\n\nDeepCFR, Double Neural CFR are actually very similar algorithms. Authors state that “All the above methods are model-based in the sense that multiple if not all actions are sampled in a state. For this reason, we do not include these methods for comparison with ACH, which is model-free and uses only trajectory samples to learn.”. This is not true - that line of work builds on top of MCCFR and thus also allows for trajectory samples. The multi-action sampling was just a particular choice for the experiments in DeepCFR paper. \n\nConsider the following paragraph from the DeepCFR paper: “While almost any sampling scheme is acceptable so long as the samples are weighed properly, external sampling has the convenient property that it achieves both of our desired goals by assigning all samples in an iteration equal weight. Additionally, exploring all of a traverser’s actions helps reduce variance. However, external sampling may be impractical in games with extremely large branching factors, so a different sampling scheme, such as outcome sampling (Lanctot et al., 2009), may be desired in those cases.“\n\n\n2) While the presented theorems are for average policy, the presented algorithm and experiments only use average policy.\n\nThis makes the comparison even more unfair, as the prior methods were designed (and reported) using the average policy. Policy averaging in non-tabular settings is a necessary part of a non-tabular algorithm\n\n\n3) The reported baselines do not match the original publications, and the overall exploitability numbers are quite poor. Consider Leduc, where author’s implementation for both RPG and NeurRD result in exploitability 0.5. Looking at the corresponding publications, these methods are reported to converge to about 0.1.\n\nThe authors suggest that “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.”\n\nFirst, it is then unfair to report this as exploitability of those methods, as these methods did include a way to average the policy. Current policy has little meaning in these settings. Second, in the case of NeuRD - even the current policy should converge.\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "\nSummary & Suggestions\n\nTo summarize, I think the paper lacks proper comparison to prior methods and makes unsubstantiated claims about  “outperforms related state-of-the-art methods”. Not only are relevant related methods missing, but the ones included do not have the performance previously reported. The authors need to rework the experiments, and also properly compare prior work. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NsJFfb-DiJF", "reviewer": "Reviewer_SULh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found the paper to be clear, well organized, and easy to read. The proposed technique, ACH, looks like a good addition to the CFR family of algorithms, separated from Deep CFR in that it can run model-free from trajectories, instead of model-based and requiring subgames. The experiments against human players, and a human champion, in Mahjong is also a nice contribution.\n\nMy main concerns are in the evaluation: the lack of a nontrivial poker game to enable a comparison against much of the existing literature, the reliance on Approximate Best Response in Mahjong and treating it as an approximation of exploitability and not a lower bound on exploitability, and a lack of clarity surrounding the average policy in ACH. \n\nThe last point is particularly important: with very few exceptions, CFR algorithms such as ACH prove that the average strategy converges, and the current strategy largely does not. Theorem 1 proves that the average strategy converges, but the empirical results only measure the exploitability of the current strategy, and from the results presented the current strategy is very exploitable and thus not a good approximation of a Nash Equilibrium. I’ll expand on this point more below, but the presentation in the paper seems incomplete: the theoretical and empirical results are not reinforcing each other. The paper needs to either describe how to compute the average strategy and present empirical results of both the average and current strategies, or to describe why this is difficult (and a possible weakness in ACH) to justify why no average strategy results are presented.\n\n\nI’ll now expand on some broader points that highlight what I feel are weaknesses or missed opportunities in the paper and suggest changes, and then list some minor issues probably only of interest to the authors.\n\nBroader comments:\n\n - Average Strategies. Like I described above, the paper proves the convergence of the ACH average strategy, but only the ACH current strategy is presented in the empirical results. Why? In Sec 5, the authors note that this was also done in Srinivasan 2018 and Hennes 2020, and while I agree about Srinivasan, I do not about Hennes: they do present average strategy results (in their paper, Figs 3, 4, 5). Srinivasan notes that computing the average policy is complex and potentially difficult with function approximation, requiring large buffers to store past strategies.\n   - This paper has two weaknesses with respect to the average strategy. First, the empirical results do not show the exploitability of the average strategy, and so (as the authors note in Sec 5.3) we cannot separate ACH’s lack of convergence to 0 exploitability from being due to the current strategy, or due to the neural network approximation error. So, the theoretical contributions and the empirical contributions do not support each other. Second, the body of the text does not explain how the average strategy should be approximated or recovered efficiently, if one wanted to do so. This has been a challenge in related work, such as Deep CFR / Single Deep CFR. If computing or representing the average strategy is indeed a challenge in ACH as it was in Srinivasan 2018, and particularly if the authors had to give up on it and just use the current strategy instead, then the authors need to be more forthright in the text by describing the difficulty and possible solutions, instead of skipping over the issue by saying they follow the evaluation as Srinivasan and Hennes did. And if computing and storing the average strategy is actually easy for ACH, then the empirical results should definitely present it alongside the current strategy results.\n\n - The paper makes two contributions: presenting ACH as a game-solving algorithm, and presenting 1v1 Mahjong as a testbed game alongside poker (larger information set size, new humans to compete against, etc). However, the paper is less compelling than it could be because it uses Mahjong as the only non-trivial domain for ACH. Heads-Up Texas Hold’em has been the common testbed domain for CFR and related work for almost 15 years. If ACH was demonstrated on a large Hold’em game, ideally the well-studied HULH variant where exact best responses are efficiently computable (thus removing the need for Approximate BR), and then the Mahjong results were presented alongside this standard and large game, then the paper would be a much stronger demonstration of ACH. No-Limit Texas Hold’em would also work, but unfortunately would lose the benefit of exact BR computations. Smaller but still nontrivial poker games are also worth considering: Flop Hold’em, also called [2-round, 4-bet Hold’em], is another benchmark game that just consists of the first two rounds of Heads-up Limit Hold’em. It has 5 card poker hands and an information set size of 1326, making it nontrivial, and yet tabular CFR strategies can be computed on one machine in a day, and exact best responses can be computed in minutes. It would be a compelling testbed for deep RL algorithms like ACH.\n   - By focusing the nontrivial-environment empirical analysis of ACH on Mahjong, it unfortunately means that ACH is demonstrated on a game well outside the mainstream in this field, and it’s hard to compare ACH against prior work that has mostly shared a common testbed. The inclusion of Kuhn and Leduc poker are good as a demonstration that the technique is not faulty, but these are tiny, trivial games that can be solved using tabular CFR methods in under a second; Deep Learning approaches like ACH cannot show the benefit of generalization in them, as they could in a larger game like HULH or HUNLH or Flop Hold’em.\n\n   - I am sympathetic to the authors in that the main works they compare to, Srinivasan 2018 and Hennes 2020, also rely on only the tiny games of Kuhn and Leduc as their only poker environments. So I’m not insisting that a larger poker game is a necessary bar to cross for a paper in this area… but to me, it would certainly make the case stronger that ACH works in practice and is worth investigating, if it were demonstrated on a nontrivial poker game that has been used before, and I wish NeuRD and RPG had been similarly demonstrated.\n\n\n - The authors have missed some related work: Outcome Sampling CFR, from “Monte Carlo Sampling for Regret Minimization in Extensive Games”, Lanctot et al. Outcome Sampling CFR is a tabular method that learns only from sampled trajectories, as ACH does, instead of requiring full game traversals or sampled subgames as in other CFR variants. \n\n\n - When describing Timbers’ Approximate Best Response, the authors should make clear that it doesn’t really approximate an agent’s exploitability. Instead, it provides a *lower bound* on the agent’s exploitability, by creating an opponent that can demonstrably win at least X from the agent. However, the ABR opponent itself suffers from training time, suboptimality from its state representation (abstraction, neural net, etc), and so an exact best response could win more, and in prior work in the poker domain much much more, than an ABR opponent can. Thus, even if Fig 1a had ABR curves converging to 0, it would not be accurate to claim that the strategy was unexploitable and had converged to NE: we would lack evidence of exploitability, but that does not give evidence of lack of exploitability. Using ABR in place of BR makes sense as a fallback in games where BR cannot be tractably computed, but we need to be honest about its limitations. And ideally, the ABR results would themselves be supported by comparisons in smaller nontrivial environments, where an exact BR showed how much value an ABR was missing.\n\n\n - Fig 1a. This looks like a convergence graph of the approximate best response: the agent’s policy is fixed, and we’re plotting ABR’s utility against the agent improve over 1e6 steps of training. Is that correct? If so, I would suggest this is not the useful way to show an approximate exploitability graph. What we’re actually interested in is the *agent’s* convergence, similar to 1b, by running a new ABR evaluation every (say) 1e5 training steps, so that we can watch exploitability come down as the agents improve over training, and differentiate if some agents learn faster, slower but reach a lower asymptote, and so on. As you describe, lower exploitability would then be better. The current perspective for Fig 1a, following the ABR over training, may be confusing for the reader who expects the evaluation to focus on the agent. \n\n\n - The behavioral strategy, mu_t / mu_k. Throughout the paper, this behavioral strategy used for generating the trajectories was described by its properties (e.g., defn 1). After finishing my review, I tried to find where the paper actually states what mu_t *is* for the strategies computed for the empirical results. Specifically, most CFR algorithms are on-policy (e.g., mu_t is pi_t), and related model-free variants like Outcome Sampling CFR add some epsilon exploration to ensure that all actions are taken with nonzero probability. But Corollary 1 describes mu_p,t as being constant across iterations, which is unlike other CFR variants. So the question of “what is mu_t” is important for understanding the results: did the results use a time-invariant behavioral policy or a policy closer to pi_t? Is the actual mu_t strategy used in the experiments defined in the paper and I just didn’t find it during my post-review skim? Note, for example, that in Algorithm 1 it is not passed as an argument to the function ACH, nor is it described as being computed, like \\pi_t is on the 4th line. If mu_t is not described in the main text, then it should be. If it is defined and I have just missed it, then I apologize.\n\n - In the appendix and conclusion, the authors describe their work as solving 1v1 Mahjong (e.g., “we extend the actor-critic algorithm … to solve a large-scale two-player zero-sum imperfect information game, 1v1 Mahjong”). I understand the authors’ intent in describing this as “solving”, but the word “solve” has a strict technical meaning in game theory and they are only using the word informally. For example, “solving a game” means exactly computing an NE, and “essentially solving” a game means approximating a NE to a very small and exactly computed tolerance (e.g., exploitable for less than 0.001 big blinds/game, in the authors’ cited Bowling 2015 paper). In this paper, neither of these milestones is reached for Mahjong: the ACH policy is not an exact NE (so, not ‘solved’), Fig 1a shows that the ACH policy is still very exploitable by a best response (so, not ‘essentially solved’ as the exploitability value is not small), and even if Fig 1a showed convergence to a value near 0, the “exploitability” calculation itself is by Timbers’ Approximate Best Response, which only gives a lower bound on the true exploitability (i.e., an exact exploitability calculation could still show it to be very exploitable, even if ABR fails to exploit it). So, using “solved” here for Mahjong exaggerates the result, and in an unnecessary way for publication: computing a strong (even if exploitable, or of unknown true exploitability) strategy that is meant to approximate a NE, and that can beat human champions, is already a great achievement. \n\n\n - Throughout the paper, the authors frequently use “Poker” when they mean “Heads-up Texas Hold’em”. Poker is a family of related games, including HULH and HUNLH, Kuhn, and Leduc (mentioned in the paper) but also other games like 2-7 Triple Draw, Omaha, Stud, and so on. Statements like “The information set size…[is] 10^3 in Poker” are incorrect. 2-Player Texas Hold’em games do indeed have about 10^3 states in each information set, but Kuhn has 2, Leduc has 5, Heads-up Omaha has 270725, Heads-Up 2-7 Triple Draw has between 2598560 and 9.8*10^12 (depending on how opponent discards are counted), and so on. This is a smaller detail because the authors’ larger point, that 1v1 Mahjong has a larger informations set size *than any poker game* is still true. But other details about “Poker”, like “only two private cards are invisible in Poker”, are only true in the specific game of 1v1 Texas Hold’em Poker.\n\n\n - The authors make a distinction between the tabular CFR approach, where a game is abstracted and then the abstract game is solved to a tight tolerance, versus Deep Learning approaches which (as they phrase it) “generalize across states without any abstraction”. The authors should be clear: the neural net is itself a form of abstraction. The hope is that the neural net approach will be more accurate since the feature representation is learned instead of fixed. But it will still be lossy to some degree, as compared to a tabular CFR approach which truly does not do any abstraction, and claims of good generalization have to be demonstrated, not presumed.\n\n\n - Table 1. The caption describes 5 independent runs. Does this mean that each agent computation in each row/column was also run 5 times (demonstrating that learning is consistent), or was each agent computed once, and then 5 evaluations of 10k head-to-head games were played? If the latter, and the agents are not trained during evaluation (which I believe is true) then could you instead describe this as 50k independent games, and measure your standard deviation over a larger set? In poker, a technique called ‘duplicate poker’ is commonly used to reduce noise in these head-to-head evaluations, by playing each game twice and switching the agent positions. A similar technique might help for these Mahjong experiments.\n\n\nSmaller issues:\n - Intro. In the sentence about CFR typically using abstraction techniques, the authors cite Bowling 2015. But that’s an odd citation to use, since that paper describes how abstraction techniques were *not* used, in order to closely approximate a NE. For a description of how abstraction techniques *are* used, maybe try “Evaluating State-Space Abstractions in Extensive-Form Games”, AAMAS 2013, or “A Practical Use of Imperfect Recall”, SARA 2009 from that research group.\n - Intro. ‘current situation of the game’. Suggest ‘current state of the game’.\n - Intro. Suggest replacing ‘bot’ with ‘agent’ in a few spots, to use the standard term.\n - Intro. The authors describe CFR as model-based, but this is not true for all CFR methods; Outcome Sampling CFR (Lanctot et al, NeurIPS 2009) is model-free and, like the authors’ technique, only requires trajectories.\n - Intro. The second-last sentence on Page 1, “abstraction techniques are often manual and require expertise domain knowledge”, has not been true for 10-15 years. The dominant approach to abstraction is simply to use machine learning: namely, using a clustering algorithm like k-means to merge similar states into clusters, based on very simple heuristics that don’t require expert knowledge. See the ‘Evaluating State-Space Abstractions’ reference above, or ‘Potential-Aware Imperfect-Recall Abstraction with Earth Mover’s Distance in Imperfect Information Games’, Ganzfried and Sandholm, AAAI 2014.\n - Sec 2.1. Define ‘infosets’ as ‘information sets (infosets)’ before using the shorthand term.\n - Sec 2.1. This definition of perfect recall appears nonstandard. It defines PR as having the reach probabilities for all h \\in I as being the same under policy \\pi. The definition I’m familiar with avoids the dependence on any policy: two histories are in an information set if and only if their preceding states also shared the same information sets. This means that an agent never loses the ability to distinguish two histories, thus, perfect recall.\n - Sec 2.1. The authors describe exploitability as the difference between a Nash’s value and a BR’s value. However, a specific useful property of 2-player 0-sum games is that we can compute exploitability without knowing a NE policy, or the game value (the value of a NE in one position against an NE in the other position), because when we sum the BR’s value in each position, we would add and then subtract the same value. So in this setting, it really is just u_p(BR(-p), -p) + u_-p(BR(p), p).\n - Sec 2.1. The total exploitability of a strategy profile defined at the end of 2.1 is not quite what is standard in other papers. The equation given sums the exploitability in each position, but the standard is to then divide by the number of positions (i.e., /2) to return the average loss against a BR across both positions. This is a more natural value because exploitability is then bounded to the range [0, delta] where delta is the maximum loss in the game. For example, if I have 10 chips in poker, my exploitability is then in the range (0, 10). Without dividing by the number of positions, I could lose 10 in one position and 10 in the other position, giving an “exploitability” of 20 when I only have 10 chips. If you do prefer the un-normalized value, related work by Lanctot calls your value “NashConv”, which differs from exploitability by only this division by 2.\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "This is a promising paper: ACH seems like it might be a useful addition to the CFR family of game solving algorithms. My main concerns are in the evaluation. The games used are either trivial domains or, when nontrivial, are not shared by related work, so it’s difficult to compare ACH’s performance. The theoretical results prove the convergence of the ACH average policy (within NN approximation error, etc), but the empirical results only demonstrate the ACH current policy, which has no theoretical convergence guarantees, and does not converge in the experiments shown here. And unless I’ve missed it, the paper does not describe how the average strategy should be approximated by a NN, which has been a challenging topic in related techniques, so the explanation is incomplete. If, like Srinivasan 2018, the authors have decided that computing the average strategy is difficult and so they will only hope that the current strategy (approximately) converges, then they should be more forthright about that shortcoming in this paper.\n\nOverall, I’m landing on ‘marginally below the threshold’, but I’m open to clarification from the authors if I’ve misunderstood elements of the paper. If I have not misunderstood it, then I believe a future draft of this paper that included an empirical analysis of the average strategy, and addressed the smaller issues I noted, could be a strong paper. Including a nontrivial poker domain alongside the Mahjong results would be excellent.\n\nEDIT: Updated review based on Nov 22nd draft\nThank you to the authors for the discussion and for addressing the issues I noted in my review. Specifically:\n - The addition of FHP results, and with exact exploitability figures, is a great addition. The exploitability of roughly 9 chips/game, or 0.09 big blinds/game, is closer to Nash than I had expected.\n - The description of ABR as a lower bound instead of an approximation is clear and consistent.\n - The clarification that 'poker' refers to 'HUNLH' in the page 2 footnote helps, but statements throughout like 'only two private cards are invisible in poker' remain, and could probably be clarified as '...in Texas Hold'em poker' without risking the page limit. Still, it's better than it was.\n - The new section 5, that describes difficulty in using a neural net to represent the average policy and confirms that the presented ACH results use the current policy, is a good clarification.\n\nI've updated several of my scores (correctness 3->4, empirical 3->4, recommendation 5->8). If 7 had been an option I likely would have landed there. The missing piece of the average strategy (a weakness shared by the related work) is still an issue, and it feels like a stretch to describe ACH as 'theoretically justified' (for example, in the abstract) when only the average strategy has theoretical guarantees. But the issue is now acknowledged, and the empirical results in Mahjong and FHP are, to me, compelling enough to recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a Actor-Critic Hedge (ACH) method for 1-on-1 Mahjong. It is is an actor-critic method for approximating Nash equilibrium strategies in large extensive-form games. ACH extends the CFR family of algorithms that uses deep learning and model-free training (not using full game traversal). The propose ACH agent defeats several human players, including a Mahjong champion. This is impressive.

The reviewers and authors have extensive discussions and the authors managed to address most of the concerns from the reviewers. The overall opinions from the the reviewers favor acceptance. Below are some of the strength and weakness summarized from the reviewers:

Strength:
* Extensive experiments and impressive performance. 
* New policy based algorithm for competitive environments.
* Reviewers' questions are well addressed.

Weakness:
Lack of more tabular theoretical analysis. Need experiments to compare to existing methods. Theory and experiment does not match.
Decision: Accept (Poster)