ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret
Authors: Stephen Marcus McAleer
Gabriele Farina
Marc Lanctot
Tuomas Sandholm
Venue: ICLR 2023 poster (2023)
Keywords: game theory
two-player zero-sum
CFR
Reinforcement learning

Abstract: Recent techniques for approximating Nash equilibria in very large games leverage neural networks to learn approximately optimal policies (strategies). One promis- ing line of research uses neural networks to approximate counterfactual regret minimization (CFR) or its modern variants. DREAM, the only current CFR-based neural method that is model free and therefore scalable to very large games, trains a neural network on an estimated regret target that can have extremely high variance due to an importance sampling term inherited from Monte Carlo CFR (MCCFR). In this paper we propose an unbiased model-free method that does not require any importance sampling. Our method, ESCHER, is principled and is guaranteed to converge to an approximate Nash equilibrium with high probability. We show that the variance of the estimated regret of ESCHER is orders of magnitude lower than DREAM and other baselines. We then show that ESCHER outperforms the prior state of the art—DREAM and neural fictitious self play (NFSP)—on a number of games and the difference becomes dramatic as game size increases. In the very large game of dark chess, ESCHER is able to beat DREAM and NFSP in a head-to-head competition over 90% of the time.

Published as a conference paper at ICLR 2023
ESCHER: ESCHEWING IMPORTANCE SAMPLING IN GAMES BY COMPUTING A HISTORY VALUE FUNCTION
TO ESTIMATE REGRET
Stephen McAleer Camegie Mellon University smcaleerécs, cmu. edu
Gabriele Farina Camneiie Mellon University gfarina@cs. cmu. edu
Marc Lanctot DeepMind lanct ot @deepmind. com
Tuomas Sandholm
Carnegie Mellon University Strategy Robot, Inc.
Optimized Markets, Inc. Strategic Machine, Inc. sandho lommlm@csss cs cmu. edu
ABSTRACT
Recent techniques for approximating Nash equilibria in very large games leverage neural networks learn approximately optimal policies (strategies). One promis- ing line of research uses neural networks to approximate counterfactual regret minimization (CFR) or its modern variants. DREAM, the only current CFR-based neural method that is model free and therefore scalable to very large games, trains a neural network on an estimated regret target that can have extremely high variance due to importance sampling term inherited from Monte Carlo CFR (MCCFR). In this paper we propose an unbiased model-free method that does not require any importance sampling. Our method, ESCHER, is principled and is guaranteed converge to an approximate Nash equilibrium with high probability. We show that the variance of the estimated regret of ESCHER is orders of magnitude lower than DREAM and other baselines. We then show that ESCHER outperforms the prior state of the art-DREAM and neural fictitious self play (NFSP)-on a number of games and the difference becomes dramatic as game size increases. In the very large game of dark chess, ESCHER is able beat DREAM and NFSP in a head-to-heaa competition over 90% of the time.
INTRODUCTION
core challenge in computational game theory is the problem of learning strategies that approximate Nash equilibrium in very large imperfect-information games such as Starcraft (Vinyals et al. 2019), dark chess (Zhang & Sandholm 202II. and Stratego (McAleer al., 2020 Perolat al. 2022) Due to the size of these games, tabular game-solving algorithms such as counterfactual regret minimization (CFR) are unable to produce such equilibrium strategies. To sidestep the issue, in the past stochastic methods such as Monte-Care CFR (MCCFR) have been proposed. These methods use computationally inexpensive unbiased estimators of the regret (i.e., utility gradient) of each player, trading off speed for convergence guarantees that hold with high probability rather than in the worst case. Several unbiased estimation techniques utility gradients are known. Some, such as external sampling, produce low-variance gradient estimates that are dense, and therefore are prohibitive in the settings mentioned above. Others, such as outcome sampling, produce high-variance variance estimates that sparse and can be computed given only the realization of play, and therefore more appropriate for massive games.
However, even outcome-sampling MCCFR is inapplicable in practice. First, since it is tabular method, can only update regret on information sets that it has seen during training. In very large games, only small fraction of all information sets will be seen during training. Therefore,

---

Published as a conference paper at ICLR 2023
generalization (via neural networks) is necessary. Second, to achieve unbiasedness of the utility gradient estimates, outcome-sampling MCCFR uses importance sampling (specificallyy, it divides the utility of each terminal state by reach probability, which is often tiny), leading to estimates with extremely large magnitudes and high variance. This drawhack is especially problematic when MCCFR is implemented using function approximation, as the high variance of the updates can cause instability of the neural network training.
Deep CFR (Brown et al., 2019) addresses the first shortcoming above by training neural network to estimate the regrets cumulated by outcome-sampling MCCFR, but is vulnerable to the second shortcoming, causing the neural network training procedure to be unstable. DREAM (Steinberger et al., (020)) improves on Deep CFR by partially addressing the second shortcoming by using a history-based value function as a baseline (Schmid et al.) 2019). This baseline greatly reduces the variance in the updates and is shown to have better performance than simply regressing on the MCCFR updates. However, DREAM still uses importance sampling to remain unbiased. So, while DREAM was shown to work in small artificial poker variants, it is still vulnerable to the high variance of the estimated counterfactual regret and indeed we demonstrate that in games with long horizons and/or large action spaces, this importance sampling term causes DREAM to fail.
In this paper, we introduce Eschewing importance Sampling by Computing a History value function to Estimate Regret (ESCHER). method that is unbiased, low variance, and does not use importance sampling. ESCHER is different from DREAM in two important ways, both of which we show are critical to achieving good performance. First, instead of using distory-dependens value function baseline, ESCHER uses one directly as an estimator of the counterfactual value. Second, ESCHER reach term. To remove
does not multiply estimated counterfactual values by an sypportance-weihheee the need to weight by the reach to the current information state, ESCHER samples actions from a fixed sampling policy that does not change from one iteration to the next. Since this distribution is static, our fixed sampling policy simply weights certain information sets more than others. When the fixed sampling policy close to the balanced policy (i.e., one where each leaf reached with equal probability), these weighting terms minimally affect overall convergence of ESCHER with high probability.
We find that ESCHER has orders of magnitude lower variance of its estimated regret. In experiments with a deep learning version of ESCHER on the large games of phantom tic tac toe, dark hex, and dark chess, we find that ESCHER outperforms NFSP and DREAM. and that the performance difference increases to be dramatic as the size of the game increases. Finally, we show through ablations that both differences between ESCHER and DREAM (removing the bootstrapped baseline and removing importance sampling) are necessary in order to get low variance and good performance on large games.
2 BACKGROUND
We consider extensive-form games with perfect recall (Osborne & Rubinstein 1994| Hansen et al.. 2004, Kovařík et al.. 2022). An extensive-form game progresses through sequence of player actions, and has a world state w E W at each step. In an N N-player game, AA = A x ... x AN is the space of joint actions for the players, Ai(w) S A; denotes the set of legal actions for player i E N = [I,...,,N N at world state w and a = (a),... (aN) E A denotes joint action. At each world state, after the players choose joint action, a transition function T(w, a) E AW determines the probability distribution of the next world state w'. Upon transition from world state w to w' via joint action a, player i makes an observation o; = (w('). In each world state w, player receives utility u, (w). The game ends when the players reach terminal world state. In this paper, we consider games that are guaranteed to end in a finite number of actions and that have zero utility at non-terminal world states.
A history is a sequence of actions and world states, denoted = (w",, aa, w², "," aa......''"............ w'), where w" is the known initial world state of the game. 24, and A.(h) are, respectively, the utility and set of legal actions for player i in the last world state of history h. An information set for player i, denoted by s,. is sequence of that player's observations and actions up until that time s(hh) = (af, of o/. a...... of). Define the set of all information sets for player to be I, The set of histories that correspond to an information set 8; is denoted H(s:) = (h (h))) si). and it is
2

---

Published as a conference paper at ICLR 2023
assumed that they all share the same set of legal actions (h)) = A,))). For simplicity we often drop the subscript i for an information set s when the player is implied.
A player's strategy ny is a function mapping from information set to probability distribution over actions. A strategy profile x is a tuple (TI....., ny). All players other than i are denoted -i, and their strategies are jointly denoted π- A strategy for history h is denoted πι (h) TT (h)) and π (h) is the corresponding strategy profile. When a strategy Ty is learned through reinforcement learning (RL), we refer the learned strategy as policy.
The expected value (EV) of (h) for player is the expected sum of future utilities for player in history h. when all players play strategy profile π. The EV for an information set 8; is denoted of (s:) and the EV for the entire game is denoted v4 (T). A two-player zero-sum game has 21 (TT) + U2 (T)= = 0
for all strategy profiles æ. The EV for an action in an information set is denoted v, (36, az). ). A Nash equilibrium (NE) is strategy profile such that, if all players played their NE strategy, no player could achieve higher EV by deviating from it. Formally, '' is a NE if (;(TT) = max=, 25 I m2,) for each player i.
The exploitability e(xx) of a strategy profile क is defined as e(TT) = EiEN maxx; (1 T-:). A best response (BR) strategy (T-;) for player to strategy æ-; strategy that maximally exploits --;; IBR; (TT_)) E arg maxx, 22 (T, T-)). An e-best response (e-BR) strategy (T for player to a strategy --; is a strategy that is at most e worse for player i than the best response: uy (BBR((T.) - 2 0 (BBR(TT)) T-4) c. An c-Nash equilibrium (c-NE) is strategy profile in which, for each player i, ny is an e-BR to -TІ
2.1 COUNTERFACTUAL REGRET MINIMIZATION (CFR)
In this section we review the counterfactual regret minimization (CFR) framework. All superhuman poker AIs have used advanced variants of the framework as part of their architectures (Bowling et al.) 2015; Brown& & Sandholm 2018 2019). CFR is also the basis of several reinforcement learning algorithms described in Section B We will leverage and extend the CFR framework in the rest of the paper. We will start by reviewing the framework.
Define (h) = IoER (a) to be the reach weight of joint policy π to reach history h, and z is a
terminal history. Define 17" 2h (h)
(=) be the reach weight of joint policy to reach terminal
history 2 from history h. Define Z to be the set of all terminal histories. Define Z(s) S Z to be
the set of terminal histories that can be reached from information state and define =[s] be the
unique history h E 8 that is a subset of 2. Define
0e (e( = Σ (h,
(1)
to be the expected value under n for player having reached h. Note that this value function takes as input the full-information history h and not information set. Define
()) = Σ [=,(=(s))m (<({)) z), = > [nI,(h)u((TT)))
(2)
=EZ(a)
hEs
to be the counterfactual value for player at state s under the joint strategy ग. Define the strategy i T to be a modified version of π where is played at information set and the counterfactual state-action value (πT 8, a) = (m 8). Similarly, define the history-action value ( h, a) = My (Th-sa: h). For any state strategy π, and action E A(s), one can define a local counterfactual regret for not switching to playing a at s as r (T, s, a) = of ( a) - of (TT, s). Counterfactual regret minimization (CFR) (Zinkevich et al. 2008a) is strategy iteration algorithm that produces sequence of policies: [TT, T2, .... ). Each policy T++1(s) is derived directly from a collection of cumulative regrets R,[(s, a) = Σi= (T, s, a), for all a E A(s) using bagret-matchigg (Hart& & Mas-Colell 2000). Total regret for player in the entire game is defined as R." max ; ΣE De (e(Tt,
w<< ). In two-player zero-sum games, the average policy tt(s)) = Dim n (e)me()) converges Σ 7.
to approximate Nash equilibrium at rate of ((TT) S O(1/VT).
3

---

Published as a conference paper at ICLR 2023
2.2 MONTE CARLO COUNTERFACTUAL REGRET MINIMIZATION (MCCFR)
In the standard CFR algorithm, the quantities required to produce new policies in Equations 1 and require full traversals of the game to compute exactly. Monte Carlo CFR (Lanctot al.] 2009) is stochastic version of CFR which instead estimates these quantities. In particular, MCCFR uses a sampling approach which specifies distribution over blocks Z, of terminal histories such that 2 Z, the set of terminal histories. Upon sampling a block a certain sampled counterfactual value ( j (defined in detail later in this section) is computed for all prefix histories that occur in Zj. Then, estimated regrets that ( j)] = (T, s), so MCCFR is an unbiased approximation CFR, and inherits its convergence properties albeit under probabilistic guarantee.
accumulated and new policies derived in CFR. The main result
Blocks are sampled via sampling policy स which is commonly a function of the players' joint policy т. Two sampling variants were defined in the original MCCFR paper: outcome sampling (OS-MCCFR) and external sampling (ES-MCCFR). External sampling samples only the opponent (and chance's) s) choices; hence, requires forward model of the game recursively traverse over all of the subtrees under the player's actions. Outcome sampling is the most extreme sampling variant where blocks consist of a single terminal history: it is the only model-free variant of MCCFR compliant with the standard reinforcement learning loop where the agent learns entirely from experience with the environment. The OS-MCCFR counterfactual value estimator when the opponent samples from their current policy as is commonly done is given as follows:
0g (TT, (])) "=="(=("]) =)),
nT (=[s), 2) T7th (z[8) T7th (=(8) (x(2)
17" (2)
The importance sampling term that is used satisfy the unbiasedness of the values have significant detrimental effect on the convergence rate Gibson et al.) (2012). Variance reduction techniques provide some empirical benefit (cchmid et al. (2019); Davis et al. (2019). but have not been evaluated on games with long trajectories where the importance corrections have their largest impact.
2.3 DEEP COUNTERFACTUAL REGRET MINIMIZATION
2019 Steinberger 2019 Li al. 2019) is method that uses neural networks to scale MCCFR to large games. Deep CFR performs external sampling MCCFR and trains and estimated cumulative regrets. The regret network is trained to approximate the cumulative regrets seen so far at that information state. The estimated counterfactual regrets are computed the same as in MCCFR, namely using outcome sampling or external sampling.
Deep CFR (Brown et al.
regret network (s, a|v² on replay buffer of information
2.4 DREAM
DREAM (Steinberger et al. 2020) builds Deep CFR and approximates OS-MCCFR with deep neu- ral networks. Like Deep CFR, it trains a regret network (s, al o/3b) on a replay buffer of information sets and estimated cumulative regrets. Additionally, in order to limit the high variance of OS-MCCFR, DREAM uses a learned history value function gi( f, al0) and uses it as a baseline (Schmid et al. 2019). While the baseline helps remove variance the estimation of future utility, in order remain unbiased DREAM must use importance sampling as in OS-MCCFR. We show empirically that variance of the DREAM estimator of the counterfactual value, although lower than OS-MCCFR, will often be quite high, even in small games and with an oracle history value function. This high variance estimator might make neural network training very difficult. contrast, ESCHER has no importance sampling term and instead directly uses the learned history value function (T(T, h al0) to estimate regrets.
3 ESCHER
In this section define proposed algorithm, ESCHER, where learned history value function (ę( ki() to estimate regret. This history value function a neural network trained on on-policy rollouts predict future reward. In theoretical analysis we model the learned history
4

---

Published as a conference paper at ICLR 2023
value function to be equal to the exact history value (T h) plus additional error. In our theoretical analysis we show that ESCHER is sound and converges to a Nash equilibrium with high probability.
As shown in Equation 3. the OS-MCCFR estimator can be seen as containing two separate terms. The first 1/17*1 1/nn"(((l (=[s)) term ensures that each information set is updated equally often in expectation. The second 17 (2 (=)n (=[s), 2) term is an unbiased estimator of the history value (,( =(s)) In DREAM, the second term gets updated by a bootstrapped baseline to reduce variance. But since the baseline is not perfect in practice, as we show in our ablations. this term still induces high variance, which prevents the regret network from learning effectively. The main idea behind ESCHER is to remove the first reach weighting term by ensuring that the sampling distribution for the update player remains fixed across iterations, and to replace the second term with history value function MT(T, [s]]))
Our method is built on Deep CFR. In particular, like Deep CFR, we traverse the game tree and add this experience into replay buffers. The first replay buffer stores information states and instantaneous regret estimates is used to train regret network Rgg (s, a) that is trained to estimate the cumulative regret at a given information set. This replay buffer is filled with information sets from trajectories gathered by following the sampling distribution in Equation 5 The regret network R, [s,s, alv) is reinitialized and trained from scratch on the entire replay buffer to estimate the average estimated counterfactual regret at every information set via regression. Since regret matching is scale invariant, the policy computed from average counterfactual regret is equivalent to the policy computed from total counterfactual regret. Similar to Deep CFR, each player's current policy T, is given by performing regret matching (described in Equation 7 on the output of the current regret network Ri(s, alp²
The second replay buffer stores histories and terminal utilities and is used to train the value network Uy to estimate the expected utility for both players when both players are at that history and play from their current policies. The value network Uy is reinitialized after every iteration, and trained by predicting future reward from on-policy trajectories. In particular, to avoid the issue that the regret-matching policy does not generally put strictly positive mass on all actions, the on-policy sampling is performed by sampling from a weighted mixture of 0.99 x the current policy and 0.01 x the uniformly-randont policy. Lastly, the third replay buffer stores information states and actions taken by the policy and uses that data to train an average policy network To that approximates the average policy across all iterations. It is this average policy that has no regret and converges to an approximate Nash equilibrium in self play.
Unlike Deep CFR and DREAM, which use the terminal utility and sampling probabilities from the current trajectory to estimate the value, in ESCHER the instantaneous regret estimates estimated using the current history value function (T( ht]0) alone. Since we only update regret on information states visited during the trajectory, our estimator is zero on all other information sets. Formally, define our estimator for the counterfactual regret as follows:
if E (()) { (1( =[>]a|0) - (e( =b]10)
(r (,Tz), =
0
otherwise
ESCHER samples from the opponent's 's current strategy when it is their turn but samples from a fixed strategy that roughly visits every information set equally likely when it is the update player's turn. As a result, the expected value of the history value is equal to the counterfactual value scaled by a term that weights certain information sets up or down based on the fixed sampling policy. Formally, define the fixed sampling policy 6,(s, a) to be any policy that remains constant across itcrations and puts positive probability on every action. This fixed sampling policy can be one of many distributions such as one that samples uniformly over available actions at every information set. In games with an equal number of actions at every information set, the uniform policy will sample all information sets at each level of the tree equally likely. An interesting open research direction is finding good fixed sampling policy. In this paper, our fixed sampling policy uniformly samples over actions, which is somewhat similar to the robust sampling technique introduced in ei al. (2019). When updating player i, we construct a joint fixed sampling policy 7 7'(s, a) to be
(bi(s,a) a)
if it's the update player i's turn
*(s a)
(5)
()) a)
otherwise
5

---

Published as a conference paper at ICLR 2023
Algorithm 1: ESCHER
Initialize history value function 9
Initialize policy Hy for both players
3 for = 1,... 7 do
4 Refill value replay buffer with on-policy data from
5 Retrain history value function on data from value replay buffer
6 Reinitialize regret networks Ry Rı
for update player i E {0, 1} do for P trajectories do
8
Get trajectory т using sampling distribution (Equation 5 for each state s E T do
10
for each action do
12
Estimate immediate cf-regret f( s, aa)z) = vi( =[s]a - u,( 2[s||0)
Add (s, (st, s)) to cumulative regret buffer
14
Add (s, a') a to average policy buffer where a' is action taken at state s
15
Train regret network R& on cumulative regret buffer
Train average policy network से on average policy buffer return average policy network 7
We use a fixed sampling policy because it allows us to remove any importance sampling in our estimator. Unlike Deep CFR and DREAM which must divide by the current player's reach probability to remain unbiased, our method does not use importance sampling but total average regret is still guaranteed converge zero. We describe our algorithm in Algorithm [ Highlighted in blue the differences between our algorithm and Deep CFR. Namely, we train history value function and use estimate counterfactual regret.
3.1 THEORETICAL RESULTS
In the following, assume that our learned value function 8; (T, hi(e) is equal to the exact value function (e( h). In the appendix we analyze the case where the learned value function inaccurate. If we sample from #' when updating player i, then the expected value of our counterfactual regret estimator is:
Egnti [f,( s/2)
Σ TF (z)
sEZ
Σ .cZ(s)
n" (s)o((m,,2(s)a) u, =[s])]
ΣΣ
(z) 2[s]a] (
hEs thh
Σn' nd (h)(v,(T, ha) ((TT
hes
n (s) Σ (h),(()(le(T,, ha) v;( h)]
hEs
(1)) 8, of( 8)] (T,
(6)
s. off (h') = (s) w(s) is the reach probability for reaching that infostate for player via the fixed sampling distribution. Unlike the estimator in Deep CFR and DREAM, our estimator has no importance sampling terms, and as a result has much lower variance. When all information sets are visited by the sampling distribution with equal probability, then ESCHER is perfectly unbiased. The correctness of our method established by the next theorem, whose proof can be found in Appendix A As shown in the proof, the regret of our method is bounded with high probability by a term that is inversely proportional to the minimum over information sets theory suggests that the balanced sampling distribution is the optimal
Where for h,
of wss). Therefore, sampling distribution, but in practice other sampling distributions might perform better. our experiments approximate the balanced distribution with uniform sampling over actions.

---

Published as a conference paper at ICLR 2023
Game
ESCHER (Ours)
Ablation
Ablation 2
DREAM
Phantom Tic-Tac- Toe
(2.6 + x00
(4.1 0.7
(1.4 0
(4.6 1.0) x10'
Dark Hex
(1.8 ( 0
(1.3 x19)
(3.1 = 1.7) x10*
(2.8 = 2.0) x
Dark Hex
(.1
(3.3 1.6)
(2.0 = x
(5.3 + 3.9) x10
Game
ESCHER (Ours)
Ablation
DREAM
OS-MCCFR
Leduc
(5.3 0.0) 10
(3.3 0.7)x10
(2.8 x.0)x102
(2.2 0.0)x
Battleship
(1.4 + x00
(
(1.2 = 0.0)
(2.4 0.0)
Liar's Dice
(9.0 + x11)
(7.8 - 0.9)
(4.0 = 0.8)
(1.2 = 0.1)
Table I: These results track the average variance of the regret estimator of each algorithm over all iterations. The top table shows results deep algorithms on large games. Ablation is ESCHER but with bootstrapped baseline, and ablation is ESCHER but with reach weighting. The bottom table shows tabular versions of the algorithms with oracle value functions on small games. Because ESCHER does not importance sampling, the variance of its estimator is orders of magnitude smaller than basclines. Colors scale with the ratio the minimum value in each row, according to the logarithmic color scale
10
100
1030
History value Boostrapped baseline
Importance sampling
Algorithm
function
ESCHER (Ours)
Ablation
/
Ablation 2
/
DREAM VR-MCCFR
/
Deep CFR / OS-MCCFR
X
Table 2: ESCHER is different from DREAM in two important ways. First, ESCHER does not use importance sampling (Lanctot al. 2009 Brown et al., [019 Steinberger al. 2020). Second, ESCHER does not estimate counterfactual values for sampled actions via a bootstrapped base- line (Schmid et al. 2019. Steinberger et 2020). Our ablations show that both improvements are necessary.
Theorem 1. Assume a fixed sampling policy that puts positive probability on every action. For any p E (0, 1), with probability least - p. the regret accumulated by each agent learning using the tabular algorithm ESCHER (Algorithm 2 is upper bounded by O(vT poly log(1/p) where the O(-) notation hides game came-dependent and sampling compling-policy--ee delieded constants.
In the appendix we extend the analysis to the case of approximate history value function, and give a bound with explicit dependence the magnitude of the approximation error.
4 RESULTS
We compare the variance of the counterfactual value estimates from ESCHER, DREAM, and ablations [ Variance is computed over the set of all counterfactual regret values estimated single iteration. The results in the table are the average of each iteration's 's variance over the first five iterations training. The top table shows results of deep algorithms on large games. A summary of the different ablations is given in Table From this experiment we can see that because ESCHER does not use importance sampling, the variance of its estimator is orders of magnitude smaller than baselines. Also, see that even ablation 1, which does not use importance sampling, has high variance. This is because when the history value function is not exact, the bootstrapping method recursively divides by the sampling probability on sampled actions. We see that this higher variance
7

---

Published as a conference paper at ICLR 2023
Phantom Tic-Tac-Toe
Dark Hcx
Dark Chess
100%
100%
100%
75%
75%
7.5%
Win
50%
50%
50%
ESCHER (Clus))
ESCHER (Ows)
ESCHER (Clus)
25%
DREAM
25%
DREAM
25%
DREAM
NFSP
NFSP
NESP
0%
0%
0%
2
0.5
1.0
Information sets touched x 10
Information sets touched x 10"
Information sets touchedx 10
Experiment: Playing against another baseline head-to-head
Phantom Tic-Tace Tic-Tac-Toe
Dark Hex
Dark Chess
100%
100%
100%
75%
75%
75%
Win %
50%
50%
50%
25%
ESCHER
25%
ESCHER
25%
ESCHER NESP
ESCHERR vs DREAM
ESCTTER vs DREAM
ESCHERR vs DREAM
0%
0%
0%
4
0.5
1.0
Information sets touched 10
Information sets tonched 10
Information sets touchedy 10
Figure 1: ESCHER is competitive with NFSP and DREAM in Phantom Tic-Tac-Toe. But the size of the game increases, ESCHER performs increasingly better than both DREAM and NFSP. In Dark Chess, ESCHER beats DREAM and NFSP in over 90% of the matches.
indeed leads to worse performance for DREAM and these ablations in Figure 2 Therefore, both improvements of ESCHER over DREAM are necessary.
We compare our method DREAM and NFSP, the most popular baselines that are also open-source, on the games of Phantom Tic Tac Toe (TTT), Dark Hex, and Dark Chess. Dark chess is popular game among humans under the name Fog of War Chess on the website chess. com, and has emerged as benchmark task (Zhang & Sandholm 2021). All of these games imperfect information versions of perfect-intee information games played on square boards. Phantom TTT played on 3 3 board while dark hex is played on a size 4 x board and dark hex 5 is played on a size 5 x 5 board. Because these games are large, we are not able to compare exact exploitability so instead we compare performance through head-to-head evaluation. Results shown in Figure I where the x axis tracks the number of information sets visited during training. We see that our method is competitive with DREAM and NFSP on Phantom TTT. On the larger game of Dark Hex ESCHER beats DREAM and NESP head to head and also scores higher against a random opponent. Moving to the largest game of Dark Chess, we see that ESCHER beats DREAM and NFSP head to head over 90% of the time and also is able to beat random opponent while DREAM and NFSP are no better than random.
similar in that they are both
5 DISCUSSION: LIMITATIONS AND FUTURE RESEARCH
Our method has number of ways can be improved. First, it requires two separate updates in one itcration. Perhaps the method could be more efficient if only on-policy data were used. Second, our method, like Deep CFR, DREAM, and NFSP, trains neural networks on large replay buffers of past experience. Unlike RL algorithms like DQN (Mnih et al. 2015), these replay buffers must record all data ever seen order to learn an average. This can be a problem when the amount of data required is much larger than the replay buffer memory. Third, we do not use various implementation details that help performance in Deep CFR such as weighting by the sum of the reach probabilities over all iterations. Finally, our method uses separate data train the value function. Our method could be made much more efficient by also using the data generated for training the policy to also train the value function.
8

---

Published as a conference paper at ICLR 2023
Phantom Tic-Tac-Toe
Durk Hex
Dark Hcx 5
100%
100%
100%
75%
75%
75%
Win
50%
50%
50%
ESCHER (Clus)
ESCHER (Ours)
ESCHER (Ours)
25%
Abiztion
25%
Ablation
25%
Ablution
Ablation 2
Ablation 2
Ablution
0%
0%
0%
2
3
Information sets touched x 10"
Information sets touched x 10"
Information sets touched x 10
Ablation experiment: Playing against another ablation head-to-head
Phantom Tic-Tac-Toe
Dark Hex
Dark Hcx 5
100%
100%
100%
75%
75%
75%
Win %
50%
50%
50%
25%
ESCHER Ablution
25%
ESCHER Ablacc
25%
ESCHER
ESCHER ys Ablation 2
ESCHER vs Ablasion
ESCHERR vs Ablation
0%
0%
0%
2
3
Information sets touched 10
Information sets touched y 10
Information sets touched y00f 10
Figure 2: Ablation study on ESCHER. As summarized in Table 2 "Ablation 1" is ESCHER but with bootstrapped histu baseline, while "Ablation 2" is ESCHER but with reach weighting. Since ESCHER with a bootstrapped history-value baseline and reach weighting is equivalent to DREAM, these results show that both changes to DREAM are necessary for ESCHER to work in large games.
One direction of future research is finding optimal sampling distributions. In method we the uniform distribution over actions as our fixed sampling distribution, but this can be far from optimal. In principle any distribution that remains fixed will guarantee the method to converge with high probability. One possible direction would be to try to estimate the theoretically optimal balanced distribution. Other, less principled, methods such as using the average policy might work well in practice as well (Burch et al. 2012). Another direction is in connecting this work with the reinforcement learning literature. Similar to reinforcement learning, we learn Q value and a policy, and there are many techniques from reinforcement learning that are promising to try in this setting. For example, although we learned the value function simply through Monte- Carlo rollouts, one could use bootstrapping- based methods such TD-À (Sutton 1988) and expected SARSA (Rummery & Niranjan 1994). The policy might be able to be learned via some sort of policy gradient, similar to QPG (Srnniassan et al. 2018), NeuRD (Hennes et al. 2020 and F-FoReL (Perolat et al. 2021)
REFERENCES
Bowling, M., Burch, N., Johanson, M., and Tammelin, O. Heads-up limit hold' em poker is solved. 2015.
Science, (671111))
Brafman, R. I. and Temnenholtz, M. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213225 231, 2002.
Brown, N. and Sandholm, T. Libratus: The superhuman AI for no-limit poker. In IJCAI, pp. 2017a
Brown, N. and Sandholm, T. Safe and nested subgame solving for imperfect-informatton games. Advances in neural information processing systems, 30, 2017b.
Brown, N. and Sandholm, T. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374) 2018.

---

Published as a conference paper at ICLR 2023
Brown, N. and Sandholm, T. Superhuman Al for multiplayer poker. Science, 365(645)))88858888 2019.
Brown, N., Sandholm, T., and Amos, B. Depth-limited solving for imperfect-infforattio games.
Advances in neural information processing systems, 31, 2018.
Brown, N., Lerer, A., Gross, S., and Sandholm, T. Deep counterfactual regret minimization. In International Conference on Machine Learning, pp. 793-802, 2019.
Brown, N., Bakhtin, A., Lerer, A., and Gong, Q Combining deep reinforcement learning and search for imperfect-informatio games. Advances in Neural Information Processing Systems, 33: 17057-17069, 2020.
Burch, N., Lanctot, M., Szafron, D., and Gibson, R. Efficient monte carlo counterfactual regret minimization games with many player actions. Advances in neural information processing systems, 25, 2012.
Burch, N., Johanson, M., and Bowling, M. Solving imperfect information games using decomposition. In Twenty-eighth AAAI conference artificial intelligence, 2014.
Daskalakis, C., Foster, D. J., and Golowich, N. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
Davis, T., Schmid, M., and Bowling, M. Low-variance and zero-variance baselines for extensive-form games. CoRR, abs/1907. 906,09633, 2019. URL /LLL:ttp.//aaxii.orrgaab/////// /ttp///000/999003633333
Ding, D., Wei, C.-Y., Zhang, K., and Jovanović, M. R. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. arXiv preprint arXiv:2202.04122 2022.
Farina, G., Kroer, C., and Sandholm, T. Online convex optimization for sequential decision processes and extensive-form games. In AAAI Conference on Artificial Intelligence, 2019a.
Farina, G., Kroer, C., and Sandholm, Regret circuits: Composability of regret minimizers. In International Conference Machine Learning, 2019b.
Farina, G., Kroer, C., and Sandholm, T. Stochastic regret minimization extensive-form games, In International Conference Machine Learning, 2020.
Farina, G., Kroer, C., and Sandholm, T. Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent. 2021.
Feng, X., Slumbers, O., Yang, Y., Wan, Z., Liu, B., McAleer, S., Wen, Y., and Wang, J. Discover- ing multi-agent auto-curricula in two-player zero-sum games. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Fox, R., Mcaleer, S. M., Overman, W., and Panageas, I. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, pp. 4414 4425. PMLR, 2022.
Fu. H., Liu, W., Wu, S., Wang, Y., Yang, Li, Xing, J., Li. B., Ma, B., Fu, Q., and Wei, Y. Actor-critic policy optimization in a large-scale imperfect-information game. Proceedings of the Tenth International Conference on Learning Representations (ICLR), 2022.
Gibson, R., Lanctot, M., Burch, N., Szafron, D., and Bowling, M. Generalized sampling and variance in counterfactual regret minimization. In Proceedings of the Twenty-Sixth Conference Artificial Intelligence (AAAI-12). pp. 1355-1361, 2012.
Gordon, G. No-regret algorithms for online convex programs. 2007.
Gray, J.. Lerer, A., Bakhtin, A., and Brown, N. Human-leve performance no- no-press diplomacy via equilibrium search. In International Conference on Learning Representations, 2020.
10

---

Published as a conference paper at ICLR 2023
Gruslys, A., Lanctot, M., Munos, R., Timbers, F., Schmid, M., Perolat, J., Morrill, D., Zambaldi, V., Lespiau, J.-B., Schultz, J., et al. The advantage regret-matching actor-critic. arXiv preprint arXiv:2008.122 12234, 2020.
Hansen, E. A., Bernstein, D. S., and Zilberstein, S. Dynamic programming for partially observable stochastic games. Conference on Artificial Intelligence (AAAI), 2004.
Hart, S. and Mas-Colell, A. A simple adaptive procedure leading to correlated equilibrium. Econo- metrica, 68())1117711150 2000.
Heinrich, J. and Silver, D. Deep reinforcement learning from self-play in imperfect-information games. arXiv preprint arXiv:1603.01121, 2016.
Hennes, D., Morrill, D., Omidshafiei, S., Munos, R., Perolat, J., Lanctot, M., Gruslys, A., Lespiau, J.-B., Parmas, P., Duéñezz-Gzzmán E.,, et al. Neural replicator dynamics: Multiagent learning via hedging policy gradients. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 492-501, 2020.
Jin, C., Liu, Q., Wang, Y., and Yu, T. V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint 0rXiv:2110.14555. 2021.
Kovařík, V., Schmid, M., Burch, N., Bowling. M., and Lisý, V. Rethinking formal models of partially observable multiagent decision making. Artificial Intelligence, 003:103645, 2022.
Lanctot, M., Waugh, K., Zinkevich, M., and Bowling, M. Monte carlo sampling for regret minimiza- tion in extensive games. In Advances in neural information processing systems, pp. 1078-1086, 2009.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems (NeurIPS), 2017.
T. A unified
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv: 010.19998..9335 2019.
Lanier, J., McAleer, S., Baldi, P., and Fox, R. Feasible adversarial robust reinforcement learning for underspecified environments. arXiv preprint arXiv:2207.09597. 2022.
Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2 1:w.x:2006009999) 2021.
Li, H., Hu, K., Zhang, S.,, Qi, Y., and Song, L. Double neural counterfactual regret minimization. In International Conference on Learning Representations, 2019.
Li, Koyamada, S., Ye, Q., Liu, G., Wang, C., Yang, R., Zhao, L., Qin, T., Liu, T.-Y,, and Hon, H.-W. Suphx: Mastering mahjong with deep reinforcement learning. arXiv preprint arXiv:2003. 200.:200...3900 2020.
Liang, E., Liaw, R., Nishihara, R., Moritz, P., Fox, R., Goldberg, K., Gonzalez, J., Jordan, M., and Stoica, I. Rllib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning, pp. 3053-3062, 2018.
Liu, W., Li, B., and Togelius, J. Model-free neural counterfactual regret minimization with bootstrap learning. IEEE Transactions on Games, 2022.
McAleer, S., Lanier, J., Fox, R., and Baldi, P. Pipeline PSRO: A scalable approach for finding approximate Nash equilibria in large games. In Advances in Neural Information Processing Systems, 2020.
McAleer, S., Lanier, J., Baldi, P., and Fox, R. XDO: A double oracle algorithm for extensive-form games. Advances in Neural Information Processing Systems (NewrIPS), 2021.
McAleer. S., Wang, K., Lanctot, M., Lanier, J., Baldi, P., and Fox, R. Anytime optimal psro for two-player zero-sum games. arXiv preprint arXiv:2201.07700 2022.

---

Published as a conference paper at ICLR 2023
Mguni, D. H., Wu, Y., Du, Y., Yang. Y., Wang, Z., Li, M., Wen, Y., Jennings, J., and Wang, Learning in nonzero-sum stochastic games with potentials. International Conference on Machine Learning, pp. 7688-7699. PMLR, 2021.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Ried- miller, M., Fidjeland, A. K.. Ostrovski, G., et al. Human-level control through deep reinforcement 2015.
learning. Nature, 51 518(7540):529-555
Moravcik, M., Schmid, M., Ha, K., Hladik, M., and Gaukrodger, S. Refining subgames in large imperfect information games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Moravčík, M., Schmid, M., Burch, N., Lisy, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356(6337):508-513 2017.
Morimoto, and Doya, K. Robust reinforcement learning. Neural computation, 17(2):335-359, 2005.
Moritz, P., Nishihara, R., Wang. S., Tumanov, A., Liaw, R., Liang, E., Elibol, M., Yang, Z., Paul, W., Jordan, M. I. et al. Ray: A distributed framework for emerging {AI} applications. In 13th { USENIX) Symposium on Operating Systems Design and Implementation ({OSDI) 18), pp. 561-571 2018.
Muller, Omidshafiei, S., Rowland, M., Tuyls, K., Perolat, J., Liu, S., Hennes, D., Marris, L.. Lanctot, M., Hughes, E., et al. A generalized training approach for multiagent learning. In International Conference on Learning Representations, 2019.
Osborne, M. J. and Rubinstein, A. A Course in Game Theory. MIT Press, 1994.
Perolat, J., Piot, B., and Pietquin, O. Actor-critic fictitious play in simultaneous move multistage games. In International Conference on Artificial Intelligence and Statistics, pp. 919-928. PMLR, 2018.
Perolat, J., Munos, R., Lespiau, J.-B., Omidshafiei, S., Rowland, M., Ortega, P., Burch, N., Anthony, T., Balduzzi, D., De Vylder, B., al. From Poincaré recurrence convergence imperfect information games: Finding equilibrium via regularization. In International Conference Machine Learning, pp. 8525-8535. PMLR, 2021.
Perolat, J., de Vylder, B., Hennes, D., Tarassov, E., Strub, F,, de Boer, V., Muller, P., Connor, T., Burch, N., Anthony, T., et al. Mastering the game of stratego with model-free multiagent reinforcement learning. arXiv preprint arXiv: 15378, 2022.
Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. Robust adversarial reinforcement learning. In International Conference Machine Learning, pp. 2817-2826. PMLR, 2017.
Rummery, G. A. and Niranjan, M. On-line Q-learning using connectionisl systems, volume 37.
Citeseer, 1994.
Schmid, M., Burch, N., Lanctot, M., Moravcik, M., Kadlec, R., and Bowling, M. Variance reduction in monte carlo counterfactual regret minimization (VR-MCCFR) for extensive form games using baselines. Proceedings of the The Thirty- Third AAAI Conference on Artificial Intelligncce 2019.
Schmid. M., Moravcik, M., Burch, N., Kadlec, R., Davidson, J., Waugh, K., Bard, N., Timbers, F., Lanctot, M., Holland, Z., et al. Player of games. arXiv preprint arXiv:21 2021.
Serrino, J., Kleiman Kleiman-Weiner, M.. Parkes, D. C., and Tenenbaum, J. Finding friend and foe in multi-agent games. Advances in Neural Information Processing Systems, 32, 2019.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T.. Baker, L., Lai, M., Bolton, A., et al. Mastering the game go without human knowledge. nature, 550 (7676):354-359 2017.
12

---

Published as a conference paper at ICLR 2023
Srinivasan, S., Lanctot, M., Zambaldi, V., Pérolat, J., Tuyls, K., Munos, R., and Bowling, M. Actor- critic policy optimization in partially observable multiagent environments. Advances in neural information processing systems, 31, 2018.
Steinberger, E. Single deep counterfactual regret minimization. arXiv preprint 1rX1v11901.06621, 2019.
Steinberger, E., Lerer, A., and Brown, N. DREAM: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006. 10410, 2020.
Sutton, R. S. Learning to predict by the methods temporal differences. Machine learning, 3(1): 44, 1988.
Tessler, C.,, Efroni, Y., and Mannor, S. Action robust reinforcement learning and applications in continuous control. In International Conference on Machine Learning, pp. 6215-6224. PMLR, 2019.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782) 2019.
Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. Online reinforcement learning in stochastic games. Advances in Neural Information Processing Systems, 30, 2017.
Wurman, R., Barrett, S., Kawamoto, K., MacGlashan, J.. Subramanian, K., Walsh, T. Capo- bianco, R., Devlic, A., Eckert, F,, Fuchs, F., et al. Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 602(7896):223- 228, 2022.
Xie, Q.. Chen, Y., Wang, Z., and Yang. Z. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference learning theory, pp. 3674-3682. PMLR, 2020.
Zha, D., Xie, J., Ma, W., Zhang, S., Lian, X., Hu, X., and Liu, J. Douzero: Mastering doudizhu with self-play deep reinforcement learning. In International Conference Machine Learning, pp- 12333-12344. PMLR, 2021.
Zhang, B. and Sandholm, T. Subgame solving without common knowledge. Advances in Neural Information Processing Systems, 34, 2021.
Zhang, R., Ren, Z., and Li, N. Gradient play in stochastic games: stationary points, convergence, and sample complexity. arXiv preprint arXiv:2106. 00198, 2021.
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems (NeurIPS). 2008a.
Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C. Regret minimization in games with incomplete information. Advances in Neural Information Processing Systems (NeurIPS), 2008b.
13

---

Published as a conference paper at ICLR 2023
A PROOFS
A. KNOWN RESULTS ABOUT REGRET MATCHING (RM)
In this section, we recall the definition and the regret bound of the Regret Matching (RM) regret minimization algorithm for probability simplices. In the interest of keeping the paper as self-contained as possible, we propose proof for the result. For deeper treatment of RM, we invite the reader to consult the works of Hart& & Mas-Colell (2000); Gordon 2007);; Farina et al. (2021).
We start by recalling the definition of RM. Let be of discrete actions and ((A) the simplex of probability distributions over A. Regret Matching operates by keeping a tally R of the regret accumulated up to each time t. compared to always selecting each action a, and picks the next distribution according to
ma (0, x' (a(a)= = En'es max Rd
Ewee max R >
otherwise.
|A]
Upon observing the utility vector g¹ E R2, the tally of the regret for each action is updated correspondingly
R = R², gaaa)) - Ed((d)a'
(8)
a'En
(at time t 0, R. = 0 for all a E A).
Proposition 1. Let M > O, and let ge be an arbitrary (possibly adversarially picked) sequence of utility vectors with lg' (a)l M for all E A received RM. The regret
T
Rd
max R max
Eg'(a)
ΣΣ El
o (a))at(a))
1=1
accumulated up to any time T by RM satisfies
R" S S
Proof. The proof hinges the following observation. Fix any time
If Eo'E max (0, R S O, then Ry 0 for all a' E A, and so trivially
Σ max R.) g'(a)) g''da'aa''a))) O.
aEA
a'EA
On the other hand, if Ea'es max(0, R. > then
max (0, R
x'(0) Eo'E max Ry
and so
Σ aeA
max Rt
(a()) - Σ Ddl(a)aa(aa))
d'EA
(I laEd
max (0, Rdd (3)
mmxx(0, Re)
Σ
(aa))ataaa)
AaA
a'EA
0.
So, in either case, all times f,
Σ max R.)
(0(())- Σ g ((d))a(((a)
(9)
AEA
d'EA
14

---

Published as a conference paper at ICLR 2023
Now, observe that for all 2
max (0, 22 v Σ
RR
++ min (0, R2))²
REA
aEA
Σ
Rd min (2) g'(a)) E
- ((((a)aaaaa))
(from
aEA
d'EA
max (0, Ryg (a) 100--ggaaa g'(a))a'
2
Σ max 12g2+
g((a) Σ (''(d'aaaa)")))
a'EA
+ Σ
max Rd (g(a))
Σ g'(a))a'(a))
aEA
d'EA
Σ max (0, 3² + g'(a) - [g((a')a((a))
-'a
(from 9
aEA
a'EA
$ Σ max R |A|
where the last inequality follows from the fact that by assumption each utility has absolute value at most M, that is, (gg(()) S M. Using the fact that R222 = 0 for all E A, the previous recursive inequality leads to
Σ max R, A
VT (1,2....}
From the previous inequality we finally conclude that
Rd max max (0, R² S V
Σ
max RT s M VIATT,
aEA
oEA
we wanted show.
A.2 ANALYSIS ESCHER
We start by recalling a central theorem connecting regret to counterfactual regret (see, egg., Zinkevich al. (2008b): Farina al. (0119 a)).
Proposition 2. Fix any player i, and let
T
R = max Eri( max Σ s, - ( ,
BEA, 1m1
AEA, [-1
be the counterfactual regret accumulated up to time T by the regret minimizer local at each informa- tion set Then, the regret
R : max 3.
Σ ( 2s o1( m"))
accumulated by the policies on the overall game tree satisfies
R Σ maxtRRT,0 03.
We can use modification of the argument by Farina et al. (2020) to bound the degradation of regret due to the use an estimator of the counterfactual regrets. However, our analysis requires some modifications compared to that of Farina al. (2020), in that ESCHER introduces estimation at the level of counterfactuals, while the latter paper introduces estimation at the level the game utilities.
15

---

Published as a conference paper at ICLR 2023
Algorithm 2: Tabular ESCHER with Oracle Value Function
for = I...., T do
for update player i (0, do Sample trajectory using sampling distribution #' (Equation 5 for each state E do
4
for each action do Estimate immediate regret vector r((T, 8, a|=) - go (m, =|b], - U 2[o])
6
Update total estimated regret of action at infostate
its,, a) = RRss a) f(T, a/2)
Update (s, a) via regret matching (Equation 7 total estimated regret
return average policy /
Theorem 1. Assume fixed sampling policy that puts positive probability every action. For any p E (0, 1), with probability at least - the regret accumulated by each agent learning using the tabular algorithm ESCHER (Algorithm 2 is upper bounded by O(vT polly log(1/p) where the O(.) notation hides game-dependent and campling-policy-eeeee
constants.
Proof. As shown in Section 3 for any information set the counterfactual regret estimators (T,,, 8, alh) are unbiased up a iimeinndeeendent multiplicative factor; specifically,
Ex [fx(T, 8, a a/h)] = ((,)):(T,,8.))
for all actions available to player at world states in Hence, for each a E A, we can construct the martingale difference sequences
X == w(s)rr((T' ,8,0) ,, s,a))).
Clearly, X is bounded, with [Xg] upper bounded by (twice) the range D of payoff's of player i. Hence, from the Azuma-Hoeffiie inequality, we obtain that the regret R accumulated by the local policies produced by ESCHER with respect to the correct counterfactuals satisfies, for all p (0,
P
Σ Lt=1
x S 2D
2T log
2 1 - P.
p
Using union bound on the actions, therefore write
P
max
x S 2D
27 log
21 P.
p
t=1
The left-hand side in the probability can be expanded as follows:
T
T
T
max
x
max
w(s)
ra(T" r
8, - Σ s,ar)
fa s,alh)
max w(s)
Σ
(T( s,a)
max
Σ Ci
2 R D IA.
where the last inequality follows from the fact that the regret cumulated by regret matching (which is run on the regret estimates f:) is upper bounded by D DAA.TT (see Proposition Hence, we can write
[Ag
P w(s)R² -VVIA,T S 2D
27 log
2 1 -
D VIAIT
2D
AAal p
P R
w(s) V
2T log
21-p.
w(s)
16

---

Published as a conference paper at ICLR 2023
where in the second step used the hypothesis that w(s) > 0 for all Since the right-hand size inside of the probability is non-negation non-negative, we can further write
D w(s) VIA.TT+ w(s)
2D
| P,
P max 03 S
V
2T log
p
valid for every information set
Now, using the known analysis of CFR (Proposition 2). we obtain that the regret accumulated by the ESCHER iterates satisfies
R
Σ max R
Hence, using a union bound over all information sets & E S; of player i, we find that
DvIA
2D w(s)
|A.l|S.|
R
2 log
VT
1 p
w())
2 min w(s)
|Ag |A
R
2| log
VT
21-p.
P
for all p E (0, 1). Absorbing game-dependent and sampling-policy-depeee constants yields the statements.
We remark that when the exploration policy is chosen to be the exploration-balancee strategy (Farinal et al. 2020), then the minimum reach probability term 1/ min, w(s)) is upper bounded by the number of terminal states in the game, polynomial number in the game tree. When the exploration policy is set to be the uniform strategy, 1/ min, w(s) is a bounded parameter that depends on the game tree structure. some artificial games, such the centipede game, such a parameter is exponential in the game tree size. In most games with reasonably balanced structure, such parameter is polynomial the game tree size.
A.3 INCORPORATING FUNCTION APPROXIMATION ERRORS
We now adapt the correctness analysis above to keep into account errors in the approximation of the history value function by the deep neural network. We can model that error explicitly by modifying to incorporate a esstor--acioon-deenddeee error 8(h, a) as follows:
(m, 2[s]a) v(( z(8)) d(2()), if ((s)
P ( s, sT
otherwise.
Repeating the analysis of Section 3 we have
E Exnat [T, 8, a|2)] = ( 8, + w(s) Σ (1)(()(( a).
hEs
Propagating the term throughout the analysis, assuming that each error term is at most 0 in magnitude, we obtain that for each infostate and E 1),
(D+c)
2(D 2(D+ +e) V VTA.TT + w(s)
[A
P R
27 log
2 p.
w(s)
Again using the union bound across all infostates of player i, we obtain
2DD + s)S min, w(s) V
|
P
R
2|4, log
VT + S
> 1-p, p,
p
showing that errors in the function approximation cause additive regret overhead linear in
17

---

Published as a conference paper at ICLR 2023
B RELATED WORK
Superhuman performance in two-player games usually involves two components: the first focuses on finding a model-free blueprint strategy, which is the setting we focus on in this paper. The second component improves this blueprint online via model-based subgame solving and search (Burch et al.
2014 Moravcik et al.) 2 Brown et al.] 2018: 2020) [Brown& & Sandholm] 2017b) |Schmid et al.
2021 ). This combination of blueprint strategies with subgame solving has led to state-of the art
performance in Go (Silver et al. 2017). )) Poker (Brown & Sandholm, 2017a 2018 Moravčík et al.
2017). Diplomacy (Gray al. 2020). and The Resistance: Avalon (Serrino et al. (2019). Methods
that only use a blueprint have ac achieved state-of-the-arr performance on Starcraft ( (Vinyals et al. (019))
Gran Turismo (Wurman al. 2022). DouDizhu (Zha et al. 202T), Mahjohng (Li et al. 2020), and
Stratego (McAleer et al., [020] Perolat et al., 2022). Because ESCHER is method for finding
blueprint, it can be combined with subgame solving and complementary to these approaches. In
the rest of this section we focus other model-free methods for finding blueprints.
Deep CFR (Brown et al., 2019 Steinberger 2019) is general method that trains neural network on buffer of counterfactual values. However, Deep CFR uses external sampling, which may be impractical for games with a large branching factor, such as Stratego and Barrage Stratego. DREAM (Steinberger et al.] (0200) and ARMAC (Gruslys et al. 2020) model-free regret-based deep learning approaches. ReCFR (Liu et al. 2022) propose a bootstrap method for estimating cumulative regrets with neural networks that could potentially be combined with our method.
Neural Fictitious Self-Play (NFSP) (Heinrich & Silver 2016) approximates fictitious play by progres- sively training best response against average of all past opponent policies using reinforcement learning. The average policy converges to an approximate Nash equilibrium in two-player zero-sum games.
Policy Space Response Oracles (PSRO) (Lanctot et al. 2017 Muller et al. 2019 Feng et al. 2021 McAleer et al. (022)) are another promising method for approximately solving very large games. PSRO maintains a population of reinforcement learning policies and iteratively trains a best response to a mixture of the opponent's population. PSRO fundamentally different method than the previously described methods in that in certain games it can be much faster but in other games it can take exponentially long in the worst case. Neural Extensive Form Double Oracle (NXDO) (McAleer et al. 202T) combines PSRO with extensive-form game solvers, and could potentially be combined with our method.
There is an emerging literature connecting reinforcement learning to game theory. QPG (Srinivasan ct al. 2018) shows that state-conditioned Q-values are related to counterfactual values by a reach weighted term summed over all histories in an infostate and proposes actor-critic algorithm that empirically converges to a NE when the learning rate is annealed. NeuRD (Hennes et al. 2020). and F-FoRel. (Perolat et al. 2021) approximate replicator dynamics and follow the regularized leader, respectively, with policy gradients. Actor Critic Hedge (ACH) (Fu et al. 2022) is similar to NeuRI) but uses an information set based value function. All of these policy-gradient methods do have theory proving that they converge with high probability in extensive form games when sampling trajectories from the policy. In practice, they often perform worse than NFSP and DREAM on small games but remain promising approaches for scaling to large games (Perolat et al. 2022). Robust reinforcement learning (Morimoto & Doya [0055 Pinto et al.) 20177] Tessler et al. 2019 Lanier et al., 2022), seeks to train an RL policy to be robust against an adversarial environment. In future work we will look to apply ESCHER to this setting.
Markov games (or stochastic games) are extensive-form games where the world state information is shared among all players at each timestep, but players take simultancous actions. Recent literature has shown that reinforcement learning algorithms converge to Nash equilibrium in two-player zero-sum
Markov games (Brafman & Tennenholtz 20022; Wei et al. 2017; Perolat et al. 2018: Xie et al.
2020; Daskalakis et al. 2020[Jin et al. (0221) and in multi- platep general-sum Markov potential
games (Leonardos et al. 2021 Mggni et al. 2021 Fox et al. 2022 Zhang et al.
2021 Ding et al.
2022
18

---

Published as a conference paper at ICLR 2023
C ADDITIONAL EXPERIMENTAL RESULTS
C.I DESCRIPTION OF GAME INSTANCES
We use Openspiel (Lanctot et al. 2019) for all our games. Below we list the parameters used define each game in Openspiel.
Leduc (leduc poker) Parameters: ("players": 2
Battleship (battleship) Parameters: ("board_width)) 2, "board_height" 2,
"ship_sie sizes": "[2]",
valuesu "[2]", ", "num soum_shots": 3, False)
@allow_repeated_steee
Liar's Dice cilars_dice Parameters: None
Phantom Tic Tac Toe (phantom Parameters: None
Dark Hex (dark Parameters: { ("soard_size", 4)
Dark Hex 5 (dark.hex) Parameters: { ""board_size"; 5} Parameters: None
Dark Chess
C.2 TABULAR EXPERIMENTS
We compare tabular version of ESCHER with oracle value functions to tabular version of DREAM with oracle value functions and with OS-MCCFR, We run experiments on Ledue poker, Battleship, and Liar's dice, and use the implementations from OpenSpiel (Lanctot al. 2019). We see in Figure 3 on the top row that ESCHER remains competitive with DREAM and OS AS-MCCFR on these games. On the bottom row
plot the average variance of the regret estimators over all information sets visited over an iteration window for each of these algorithms. While DREAM does improve upon OS-MCCFR, it still has orders of magnitude higher variance than ESCHER. Although this does matter much in tabular experiments, we conjecture that high regret estimator variance makes neural network training unstable without prohibitively large buffer sizes.
Leduc Exploitability
Battleshhp Exploitabilitt
Dice Exploltability
10
1.5x
Exllobabiity
Explotabiiit
2 10F
1.3x
10
1.2x
ESCHER (Ours)
ESCHER (Ours)
101x100
ESCHER (Ours)
CREAM
MCCFR
13P
DREAM
OS-MCCTR
DREAM
13
10'
10"
30"
Iterations
horations
ttrations
(a) Leduc Exploitability
(b) Battleship Exploitability
(c) Liar's Dice Exploitability
Wegret Estirator Vanunce
Leduc Variance
Megrett Estrrattrr Vanunce
Battleship Variance
Rogret Estrmetor Vanarce
Liar's Dice Variance
302
20a
10:
FRCHFR (Curr)
10
30²
ESCHER (Durs)
DREAM
20¹
05 MCCFR
10
ESCHET, (Durs)
DREAM
30¹
25- RCCE
0S MCCER
lterations
Iterations
teratione
(d) Ledue Variance
(c) Battleship Variance
(f) Liar's Dice Variance
Figure 3: The tabular version of ESCHER with an oracle value function is competitive with the tabular version of DREAM with oracle value function and with OS-MCCFR in terms of exploitability (top row). The regret estimator in ESCHER has orders of magnitude lower variance than those of DREAM and OS-MCCFR (bottom row).
C.3 ADDITIONAL. ABLATIONS
In this section we describe two sets of experiments. In the first set experiments we ablate the exploration term for the sampling policy. The algorithm presented in the main paper corresponds to
19

---

Published as a conference paper at ICLR 2023
exploration equal 1, i.. the sampling policy always plays uniform. Alternatively, we could sample from only the current policy, which we call exploration of O. Lastly, we present results where we sample from mixture of 0.1 times the uniform policy and 0.9 times the current policy, which call exploration of 0.1. In the second set of experiments, we compare training the value function from scratch every iteration against not re-initializing the value function.
As shown the top row of F these preliminary results suggest that there not much difference in which sampling distribution we use. However, this is likely due the the games we evaluate on. We suspect that in games such as video games, sampling from a uniform distribution will perform worse than from the current policy, because uniform distribution will spend most of its time on bad actions. However, little is known theoretically about this on poloicc setting, and it is an interesting direction for future research. On the bottom row we see that there again isn't much difference between re-initializing the value function and keeping the same value function, but keeping the same value function performs slightly better. We suspect that using best practices from learning on-policy value functions in common single-agent actor-critic algorithms will improve performance.
Phantom TTT Rewards vs. Random
Dark llex Rewards vs. Random
Dark Chess Rewards vs. Random
1.0
1.0
1.9
Vin 3 Vs. Kandom
0.8
Win S VL. Random
0.8
Win 36 vs. Random
0.8
0.6
0.6
0.6
Explanation Explaration
Explur alien
Expluration
Explor ation
Exploration
Exploretion
Exploration
Exploretion
0.0
0.2
0.4
U.6
0.0
0.5
10
1.5
2.0
0.0
U.5 Information Touched
1.5
2.0
Informatior Sets Touched
267
Information Sets Touched
ln7
167
(a) Phantom TTT Exploration
(b) Dark Hex Exploration
(c) Dark Chess Exploration
Phantom TTT Rewards vs. Random
Da rk Hex Rewards vs. Random
Dark Chess Rewards vs. Randon
Vin No v.. Mandum
Win No vs. Mandam
Wi Bandem
0.4
0.4
0.4
0.2
Don't Roint Val. Fr.
0.2
Don't Rainit Val Fn.
0.2
Don't I Reinit Val Fn.
Beinit
Reinit
Reintt
0.0
4
0.0
0.0
0.5
1.
1.5
0.0
0.0
0.5
Lo
15
2.0
Information Sets Touched
1e6
Informat on Sets Touched
le7
Information Sets Touched
1e7
(d) Phantom TTT Reinitialize Value (e) Dark Hex 5 Reinitialize Value (I) Dark Chess Reinitialize Value Function
Function
Function
Figure 4: Sampling from a uniform strategy vs. sampling from the current policy or a mixture of the two does not seem to make large difference against a random opponent (top row). Not re-initializing the value function seems to perform slightly better than training from scratch every iteration (bottom row).
D HYPERPARAMETERS FOR DEEP EXPERIMENTS
For all deep experiments we first did hyperparameter search that starts with good hyperparameters for flop hold 'em poker. We report the final hyperparameters used for the deep experiments. As deseribed in the Dark Chess section, DREAM experiments dark chess used 500 batches for advantage and average training to not run out of memory. All experiments shown include two seeds, with error bars that correspond to standard error of the mean.
20

---

Published as a conference paper at ICLR 2023
D.1 ESCHER
Parameter
Value
n regret network traversals
1,000
n history value network traversals
1,000
batch size regret network
2048
batch size history value network
2048
train steps regret network train steps history value network
5,000
5,000
train steps average policy network
10,000
Table ESCHER and Ablations Hyperparameters for Phantom TTT, Dark Hex
Dark Hex
Parameter
Value
regret network traversals n history value network traversals
1,000
1,000
batch size regret network batch size history value network
2048
2048
train steps regret network train steps history value network train steps average policy network
500
500
10,000
Table 4: ESCHER and Ablations Hyperparameters for Variance Experiments
When computing the value function, we random noise to the current policy to induce coverage over all information sets. To do this we added 0.01 times a uniform distribution to the current policy and renormalized.
D.2 DREAM
We use the codebase from the original DREAM paper (Steinberger et al. 2020 with a wrapper
to integrate with Openspiel (Lanctot et al. 2019) and rllib (Liang et al. 2018). When otherwise specified, we use default parameters from the DREAM codebase.
Parameter
Value
n batches adv training n traversals per iter
4,000
1,000
n batches per iter baseline periodic restart
1,000
10
max las sync simultaneously
12
mini batch size adv max buffer size adv mini batch size avrg buffer size avrg batch size baseline batches avrg training
10,000
2,000,000
10,000
2,000,000
2048
4000
Table 5: DREAM Hyperparameters for Phantom TTT. Dark Hex 4, Dark Hex 5
D.3 NFSP
We use our own implementation of NESP that uses RLLib's (Liang et al. 2018 DQN implementation and outperforms the original paper's results on Ledue poker.
21

---

Published as a conference paper at ICLR 2023
Parameter
Value
circular buffer size
2c5
total rollout experience gathered each iter
1024 steps
learning rate
0.01
batch size
4096
TD-error loss type
MSE
target network update frequency
every 10,000 steps
RL learner params
DDQN
anticipatory param
0.1
avg policy reservoir buffer size avg policy learning starts after avg policy learning rate avg policy batch size avg policy optimizer
2e6
16,000 steps
0.1
4096
SGD
Table 6: NESP Hyperparameters for Phantom TTT, Dark Hex 4, Dark Hex 5
D.4 DARK CHESS
Hyperparameters are the same as in other deep experiments (described above), except DREAM experiments on dark chess used 500 batches for advantage and average training to not run out of memory. For these experiments only the current observation was passed in the network for each method. As result, but it is still a fair comparison. future work we plan on doing more engineering to include more information to the networks.
cannot expect these algorithms to learn strong strategy dark chess,
E CODE
We have open sourced code here: bttps://gitiie www.//aanhonnn-aa//BBe.... Our code is built on top of the OpenSpiel (Lanctot et al. 2019) and Ray (Moritz et al. 2018) frameworks, both of which are open source and available under the Apache-2.0 license.
22


Reviews:
[{"review_id": "gSMd9zPwyT", "reviewer": "Reviewer_FHV8", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper develops an algorithm, ESCHER, to reduce the variance of CFR with deep learning by avoiding importance sampling.", "summary_of_the_review": "The paper develops an algorithm, ESCHER, to reduce the variance of CFR with deep learning by avoiding importance sampling. The motivation looks sound to me but I need to be convinced how the remaining part hidden from oracle of value function can be addressed before recommending accept.", "strength_and_weaknesses": "The intuition looks pretty reasonable to me. However, I still have some questions regarding ESCHER before I can recommend accepting.\n1. In Section 3 it's claimed sampling using a fixed distribution (what I think is the $\\tilde{\\pi}$ here) can avoid importance sampling. Why this is the case? I don't think this claim is supported properly.\n2. In the last line of equation (6), $w(s)$ is defined via $\\pi'$ but I think it comes from the sampling strategy $\\tilde{\\pi}$ right? Why is the inconsistency here? Is this a typo or I have missed something important?\n3. It looks to me very obvious that if an oracle of value function is available, we never need to use importance sampling because we can compute the counterfactual regret directly. I don't think this makes any essential improvement, since we may still need important sampling to estimate these value functions from samples. How should this be handled? Actually, I think this is more important than the content discussed in detail in section 3, and the authors may want to explain more about that.\n4. I think it will be super helpful it the authors can give some intuition on why it's possible to avoid using importance sampling at all. Say for the strategic-form game, can we also avoid using importance sampling in Mento Carlo using the proposed approach? Or is there any certain character of  EFG such makes this possible?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "N06gKOEeev", "reviewer": "Reviewer_yTxH", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The authors study the approximation of  Nash equilibrium in very large extensive-form games with prefect recall. One line of research approximates with the use of neural networks the tabular algorithm: counterfactual regret minimization (CFR). One issue with these methods is that they train a neural network with targets that can have extremely high variance due to the use of importance sampling estimation (of the counterfactual regret). The authors propose the ESCHER algorithm a model-free method that does not require any importance sampling. They prove that the tabular version is guaranteed to converge to an approximate Nash equilibrium with high probability. Experimentally they show that both the tabular version and the deep version of ESCHER enjoy a smaller variance than several baselines such that Outcome Sampling MCCFR in the tabular case and NFSP and DREAM in the function-approximation case. Furthermore they show that ESCHER outperform NFSP and DREAM on three games: Phantom Tic-Tac-Toe, Dark Hex 5 and Dark Chess.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "*Strength\n\n- An importance sampling free algorithm for imperfect information games\n\n*Weaknesses\n\n- Lack of clarity.", "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": "39L2Rh37pY", "reviewer": "Reviewer_VgYx", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper proposes to learn a history-dependent value function and sample actions from a fixed sampling policy to replace the importance sampling and reduce variance.\n\nOverall, this paper is well-written and easy to follow, the reviewer is not very professional in the field of CFR, but still catches most of the content.\n\n*** The reviewer has reviewed this paper in neurips2022, since most of the concerns are addressed by the reply at that time, the reviewer would suggest acceptance at this time. \n\nThere are still some minor questions as follows. ", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strength:\n\n(1) This paper is well-written and easy to follow, the background part and related work are very detailed.\n\n(2) The authors give proof of the upper bound of ESCHER assuming a fixed sampling policy.\n\n(3) The additional Table 2 in this version clearly shows the differences between ESCHER and previous works \n\nWeaknesses:\n\n(1) ESCHER proposes a two-stage iteration, which may not be a good practice (also discussed in the Limitation part). The gap between the outer fixed sampling policy and the inner regret learning should be addressed experimentally or theoretically.\n\n(2) In the neurips2022 rebuttal, the authors also agreed that \"Yes, retraining a value function every iteration is slow, but that's not the main point of the paper\", therefore, it is expected to estimate the additional overheads for training the value function. And some of the results should be presented in another way. For example, the x-axis in Figure 3 is the number of iterations, which may guide the reader that ESCHER converges much faster than DREAM and OS-MCCFR, but the effort within an iteration should be noted.\n\n(3) The correlation between the high variance of the regret estimator and the low performance/winrate of the algorithm should be addressed. Since the algorithm may have a larger variance due to its unique settings and hyperparameters but can perform well in practice (e.g., proximal policy optimization), the authors are encouraged to give more evidence why ESCHER is better.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}]

Author rebuttal:

Decision: Accept: poster