Thank you very much for your acknowledgment and response, and for making our manuscript better!

Two-Player Zero-Sum Game

We focus on two-player zero-sum game because this is one of the most popular and important games. For instance, Go, Chess, StarCraft, Dark Chess, and Stratego all fall into this class.

Moreover, [1][2] showed that computing Nash equilibria in two-player general-sum matrix games is PPAD-hard. Therefore, for games beyond two-player zero-sum, computing Nash equilibrium is generally intractable. Moreover, it is still unclear what the suitable solution concept is for superhuman agents in games beyond two-player zero-sum, due to the equilibrium selection issue [11].

How Equation 4.3 is derived

Thank you very much for pointing out the typo. We updated it in the latest version.

Equation 4.3 is derived from the three-point identity of Bregman divergence. Its formal proof is in Appendix E (line 1193-1205 are its formal statement, we use the big O notion in the main text for simplicity).

Basically, to prove Equation 4.3, we need to use the three-point identity first (Lemma E.2.). Then, by telescoping and bounding the additional terms given by Lemma E.2. individually, we will get Equation 4.3.

Experiments

Thank you very much for pointing this out. In the latest revision, as pointed out by Reviewer ggwY, the algorithms seem not converge in Liar's Dice. Therefore, we run ten times as many iterations in Figure 1 of the latest revision. Now QFR outperforms BOMD in all games but is still inferior to BFTRL in Liar's Dice. The reason may be Liar's Dice is too easy since it can be solved within 50 iterations with full-information feedback (see Figure 2 in Appendix H).

$d(h|s)$

$d(h|s)$ is the probability of reaching node $h$ conditioned on reaching infoset $s$. In other words, we can also write it as $d(h|s):=Pr(h|s)=\frac{Pr(h) Pr(s|h)}{Pr(s)}$ by Bayes' Theorem. Moreover, $Pr(s|h)=1$ given that node $h$ is in infoset $s$. Therefore, $d(h|s)$ is proportional to $Pr(h)$, which is $\mu_c(h) \mu_1^{\pi_1}(\sigma_1(h)) \mu_2^{\pi_2}(\sigma_2(h))$.

Let $s(h)$ denote the infoset node $h$ belongs to, then $\mu_1^{\pi_1}(\sigma_1(h))=\prod_{(h'',a'')\sqsubseteq h: h''\in \mathcal{H}_1}\pi_1(a''|s(h''))=\mu_1^{\pi_1}(\sigma_1(h'))$ for any nodes $h,h'\in s$. Because the game is perfect-recall, the infosets of player 1 should be the same along the path from the root to any node $h\in s$. Otherwise, if $h,h'\in s$ has an infoset of player 1 differs along the path, then player 1 can differentiate $h,h'$ because he remembers perfectly how he comes from root to $h$ and $h’$, which conflicts with the definition of infoset.

Minor comments

Thank you for flagging the typos and making the new version better. Here are the answers to your questions in the "Minor:" section of your review.

• $\bar \pi_i^{(t)}$ is an auxiliary strategy in the optimistic updates of the algorithm. We define it in Line 14 of Algorithm 1 and explain it in line 274-277.
• $\alpha_s>0$ is the hyper-parameter in the local regularizer $\psi_s^{\Delta}$ at infoset $s$. The formal definition of $\psi_s^{\Delta}$ can be found in Equation C.1. of the latest revision. We add the introduction at the beginning of Appendix C in the latest revision. We include $\alpha_s$ in the regularizer for the generality of the results.

Expanded introductory description of the algorithm

Thank you very much for the advice. We add more descriptions about the algorithm in the latest revision.

Experiments

The exploitability is the left-hand-side of Equation 2.1, and we add the description in the latest revision.

In line 520-528, we have added more discussion about experiment results in the latest revision.

In Figure 1, since we only compare algorithms learning with trajectory rollouts, the sample complexity is the same for all algorithms listed, which is the height of the game tree per iteration.

Conclusions and completeness of the body

We added the conclusion in the latest revision.

(I) and (III) overlap

(I) and (III) differ from each other since there exist algorithms that can achieve (I) without (III) or achieve (III) without (I).

For instance, previous work such as outcome-sampling CFR [6], Balanced OMD [7], and Balanced FTRL [8], all achieve (I) without (III) since they need importance sampling to get an estimator of the counterfactual values.

Previous work based on external-sampling, such as external-sampling CFR [6] and Deep CFR [9], achieves (III) by sampling approximately the square root of the game tree size at each iteration.

We have briefly discussed it in line 86-96 in the original submission.

Questions

• We have clarified the wording around Equation (2.3).
• We keep the regularization coefficient $\tau$ unchanged in the experiments. All exploitability is computed in the original game without additional regularization (Equation 2.1). However, it is easy to anneal the regularization as [3].
• In practice, to control the variance, we need to train another value network to approximate the value function. For instance, Proximal Policy Optimization (PPO) [9], a practical variant of the policy gradient algorithms in RL, also deploys a value network to reduce the variance. In Figure 3 of the latest revision, the implementation of QFR is based on PPO, which utilized value function approximators during training.
• We call it policy gradient since it resembles some key properties of policy gradient algorithms such as REINFORCE. (i) learning with trajectory rollouts (ii) estimating the Q-value with the reward collected in the rollout.

Technical Novelty

The main technical novelty of this paper is in showing that Q-value-based iterations are sound in imperfect-information games. To get there, (i) we extended the dilated regularizer to bidilated regularizer, which can soundly avoid importance sampling while learning from trajectory rollouts.

(ii) We proposed a new learning rate schedule. More specifically, in our algorithm QFR, the learning rate is selected to increase from the top to the bottom of the game tree. The learning rate of each infoset is recursively set to be a constant multiple of its parent nodes.

Intuitively, this enables strategies at the bottom of the game tree, which are inherently easier to learn, to converge more quickly while keeping the parent utilities relatively stable. The fact that bottom strategies are easier to learn can be observed in Texas hold'em. At the end of the game, all public cards are revealed so that it would be easier to decide on the bet than at the beginning of the game.

Minor Issues

We fixed all minor issues mentioned in the response. Thank you very much for your suggestions!

Thank you very much for your advice on our paper!

Technical Novelty

The main technical novelty of this paper is in showing that Q-value-based iterations are sound in imperfect-information games. To get there, (i) we extended the dilated regularizer to bidilated regularizer, which can soundly avoid importance sampling while learning from trajectory rollouts.

(ii) We proposed a new learning rate schedule. More specifically, in our algorithm QFR, the learning rate is selected to increase from the top to the bottom of the game tree. The learning rate of each infoset is recursively set to be a constant multiple of its parent nodes.

Intuitively, this enables strategies at the bottom of the game tree, which are inherently easier to learn, to converge more quickly while keeping the parent utilities relatively stable. The fact that bottom strategies are easier to learn can be observed in Texas hold'em. At the end of the game, all public cards are revealed so that it would be easier to decide on the bet than at the beginning of the game.

Significance of Avoiding Importance Sampling

The most critical issue of importance sampling is that it will cause numerical instability in training targets. Because the denominator is the probability of reaching an infoset, it can be as small as $\frac{1}{\text{game size}}$. Therefore, the feedback (an unbiased estimator of the counterfactual value) fed into the neural network can be as large as the game size. For instance, in Stratego, it can be over $10^{200}$ [5].

To illustrate this, in Figure 3 of the latest revision we present the comparison between importance sampling and no importance sampling when the strategies are approximated by neural networks. We can see from the figure that when using importance sampling, the neural network does not converge. Please also refer to the response to Reviewer ggwY for details.

Importance of Trajectory Rollouts

Trajectory rollout is one of the standard components in learning in large games because of its per-iteration sampling efficiency. In each iteration, the number of infosets visited per iteration in trajectory rollouts is bounded by the game tree depth, which is typically the logarithm of the game tree size. However, the number of infosets visited by external sampling per iteration is approximately the square root of the game tree size.

For instance, in Stratego, trajectory rollouts only need to visit approximately $4\cdot 10^3$ [5] infosets while it is more than $10^{200}$ infosets when using external sampling.

We added some motivation in the latest revision about this on line 85-92.

Thank you very much for your comments and acknowledgement!

Additional Regularization

You are correct: regularization speeds up convergence at the cost of converging to biased solutions. The exploitability (Equation 2.1) of the regularized Nash equilibrium in the original game is $O(\tau)$ (the proof can be found in Lemma D.1. of [3], we have added the link to it in the latest revision on line 330-333), where $\tau$ is the coefficient controlling the scale of regularization.

Additional regularization is popular in modern literature on solving games (e.g., [3] [4] [14] [15]), because intuitively it is often more valuable to moving fast in the right direction than to hit an exact target, especially in large games. To get the best of both worlds, two approaches have been proposed, each of which can be applied as an afterthought. One possibility, employed by R-NaD [14] and APMD [15], is to use "slingshotting": the regularization term is updated periodically to "recenter" around later iterates. Another possibility is to simply anneal the regularization, as done in [3].

Showing the advantage of QFR

Thank you very much for your comment.

We did an ablation study on importance sampling with the neural network approximated strategy in Leduc Poker, which is a standard benchmark for deep reinforcement learning in games [12][13]. As shown in Figure 3 in the latest revision, the gradient norm blows up when we do importance sampling and thus the network generally learns nothing even though gradient clipping is applied (the right plot shows the gradient before clipping). Therefore, with importance sampling, deep reinforcement learning does not work even in a small game, the Leduc Poker, which proves the necessity of property (III).

Additionally, property (I) guarantees efficient sampling (in contrast to external-sampling and full-information, see also the response to Reviewer msNB) and (II) guarantees lower approximation error or storage consumption, which has been extensively discussed in previous work [3][4].

On Figure 1

Thank you for your advice! We run experiments in Figure 1 (algorithms with sampling feedback) for ten times as many iterations as the original version and the result is shown in Figure 1 of the new version. We can see that now QFR outperforms outcome-sampling CFR / CFR+, MMD, and BOMD in all games. It is only inferior to BFTRL in Liar's Dice by a small margin (QFR 0.174 v.s. BFTRL 0.167 in exploitability). The reason may be Liar's Dice is too easy since it can be solved within 50 iterations with full-information feedback (see Figure 2 in Appendix H).