Dynamic Discounted Counterfactual Regret Minimization

We sincerely appreciate the reviewer for the positive recommendation of our work and the insightful feedback. Following are our responses to your concerns.

• How does the DDCFR technique compare to deep methods like Deep CFR when it comes to larger scale games?

Many thanks for your constructive comments. DeepCFR finds an approximate Nash equilibrium by combining a base CFR-type algorithm with deep neural network function approximation. For instance, the original DeepCFR paper [1] employs LinearCFR as the base CFR algorithm, which is a specific version of DCFR.

Based on these considerations, there are inherent differences in the underlying principles and objectives of DDCFR and DeepCFR. Specifically, DDCFR focuses on enhancing the performance of base CFR-type algorithms through dynamic discounting. In contrast, DeepCFR aims to use neural networks to approximate and generalize the behavior of base CFR-type algorithms. Consequently, it is not appropriate to directly compare these two approaches from our perspective.

We want to thank you again for your insightful comment, which has inspired us greatly. In particular, since our DDCFR is a strong CFR-type algorithm, it can also serve as a strong base algorithm for DeepCFR. DeepCFR, in turn, can utilize neural networks to approximate and generalize the behavior of DDCFR, thereby potentially improving its performance compared to using the original LinearCFR base algorithm. Since deep methods are not the focus of our paper, we consider this promising idea as an intriguing avenue for future research.

[1] Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret minimization. In International Conference on Machine Learning, pp. 793–802, 2019.

• How does DDCFR empirically scale to games with more players?

Thank you very much for your insightful question. Our work focuses on solving two-player zero-sum games, and we have not delved into the application of DDCFR in multiplayer games for the following reasons:

For two-player zero-sum games, CFR effectively computes strategies that converge to an approximate Nash equilibrium. A Nash equilibrium is useful in two-player zero-sum games since it ensures that the player maximizes its utility against a worst-case opponent, effectively avoiding losses. However, when applied to multiplayer games, CFR loses all theoretical guarantees. It is not guaranteed to converge to a Nash equilibrium, and playing a Nash equilibrium may not be wise in multiplayer games [1].

Nevertheless, CFR-type algorithms have the potential to generate strategies that empirically perform well in multiplayer games [2,3]. We believe that our DDCFR is a general framework that can enhance CFR's empirical performance in multiplayer games as well. We will explore this exciting direction in our future work.

[1] Noam Brown and Tuomas Sandholm. Superhuman AI for multiplayer poker. Science, 365(6456): 885–890, 2019.

[2] Nicholas Abou Risk and Duane Szafron. Using counterfactual regret minimization to create competitive multiplayer poker agents. In International Conference on Autonomous Agents and Multiagent Systems, pp. 159–166, 2010.

[3] Richard Gibson. Regret minimization in games and the development of champion multiplayer computer poker-playing agents. PhD thesis, University of Alberta, 2014.

• It would also have been nice to see running time comparisons in the experiments to properly verify the authors' claims about additional computational costs not causing major increases in running time.

Thank you very much for your constructive suggestion. We have added a table in Appendix D, which compares the running time between DCFR and DDCFR. The results show that the additional computation time incurred by DDCFR is negligible compared to the overall iteration time.

We sincerely appreciate the insightful feedback and your efforts in reviewing our paper. Following are our responses to your concerns.

• The paper could be better organized.

Thank you very much for your valuable suggestion. Section 2 of the current paper contains a significant number of formulas, potentially imposing a heavier reading burden on the audience. Following your advice, we have carefully restructured Section 2. In this revised version, we provide only intuitive descriptions of key concepts, such as counterfactual values and reach probabilities, in Section 2. We have moved the mathematically rigorous definitions of these terms to Appendix A, as well as the related terms relationship $g \subseteq h$ and player function $\mathcal{P}(h)$. Furthermore, We have simplified the definition of the range of utilities $\Delta$. We believe that this updated version will enhance the paper's accessibility for researchers in both the AGT and RL communities.

• There are some overloaded notations that make the paper harder to parse.

Thank you very much for pointing out the issue with overloaded notation making certain parts of the paper ambiguous. Using unique symbols eliminates confusion and improves readability.

Following your suggestion, we have made the following modifications.

1. We use $\hat{a}$ to denote the action of the RL agent and to distinguish it from the action $a$ in the game tree.
2. We use $\hat{R}^G$ to denote the reward function in MDP and to distinguish it from the cumulative regret $R$ in CFR.
3. We use $\delta$ to denote the noise standard deviation in ES and to distinguish it from the strategy $\sigma$ in the game.
4. We use $N$ to denote the population size in ES and to distinguish it from the state transition $P^G$ in MDP.
5. We uniformly use $t$ to denote one iteration and $T$ to denote the total number of iterations.

• For the experiments, it would be nice if the authors could provide the wall-clock times for DDCFR.

Thank you very much for your constructive suggestion. To further support claim in Section 3.4, we have added a table in Appendix D, which compares the wall-clock time between DCFR and DDCFR. The results show that the additional computation time incurred by DDCFR is negligible compared to the overall iteration time.

• Theorem 1 requires the action space to be discretized, yet this is not stated explicitly (also see the following section for question on boundedness of $\tau$)

Thank you very much for your comments. It seems that there may be a slight misunderstanding regarding Theorem 1. Please allow us to provide a more detailed explanation.

First of all, Theorem 1 supports a continuous action space, as along as actions are within a certain range. For example, in every iteration $t$, $\beta\_t$ can take on any real value between -5 and 0. By the way, our DDCFR also adopts a continuous action space design. The ablation studies in Section 4.3 demonstrate that the continuous action space design outperforms the discrete action space design.

On the other hand, the algorithm still converges even when $\tau \rightarrow \infty$. As $\tau\rightarrow \infty$, DDCFR never adjusts the hyperparameters and always uses the initial discount rate as you mentioned. In other words, $\forall t \le T, \alpha\_t=\alpha\_1, \beta\_t=\beta\_1, \gamma\_t=\gamma\_1$. As long as $\alpha\_1, \beta\_1, \gamma\_1$ are within the range specified by Theorem 1, it still satisfies the requirement of Theorem 1. Therefore, the algorithm still converges at the rate provided in Theorem 1.

In fact, we can view DCFR as a special case in this setting, where $\alpha\_1=1.5, \beta\_1=0, \gamma\_1=2, \tau\_1=\infty$. This specific configuration meets the requirements of Theorem 1.

In summary, Theorem 1 indicates that numerous discounting schemes converge in theory as long as the discounting weights in each iteration are within a certain range. The primary contribution of our DDCFR is the discovery of a dynamic and automatically learned scheme.

• It appears that experiments are only run once, yet multiple runs are required to demonstrate that the proposed approach convincingly outperform DCFR, and the figures in the paper are not due to luck alone.

Thank you very much for your comments. We want to emphasize that there is NO randomness throughout the iteration process of DDCFR when using the learned discounting policy on the testing games. Specifically, DDCFR always initializes with the uniform random average strategy, and the policy network consistently produces the same fixed action when inputs are determined. Put simply, each run of DDCFR with the learned model consistently generates the same exploitability curve.

We use ES to learn the discounting policy, and we select one of the best performing policy on the training games for testing. In response to your concerns, we independently ran the ES training process 5 times and tested the performance of the resulting 5 discounting policies. In Appendix F of the revised paper, we have added figures to show the average performance of DDCFR. The results show that DDCFR is still superior to other baselines. This proves that the superiority of DDCFR is not due to luck.

• Does it make sense to consider a bandit-based approach for optimizing the discount rates?

As far as we know, in a typical bandit scenario, there is usually a single state with multiple available actions. However, in our setting, the agent takes actions across multiple states, ranging from $s\_1$ to $s\_T$. The optimal action varies from one state to another. Therefore, based on our understanding, the bandit-based approach is less suitable for our scenario.

Dear reviewer, thank you very much for reviewing our response and updating the score. We genuinely appreciate your meticulous reading and insightful comments.

• I think it might be useful to consider clarifying that $|A|$ does not mean the cardinality of a finite set, which seems to be a more commonly used definition in RL.

Thank you very much for your good suggestion. We have incorporated the clarification in section 2.1 of the revised paper: With a slight abuse of the cardinality notation $|\cdot|$, we use $\vert\mathcal{A}\vert$ to denote the maximum number of actions within each information set, i.e., $\vert\mathcal{A}\vert = \max\_{I\in\mathcal{I}}\vert \mathcal{A}(I) \vert$.

• Same for emphasizing that runs in the experiment section are deterministic as opposed to stochastic, which again is more common in RL.

Thank you very much for this suggestion. We have also clarified this in section 4.2 of the revised paper: It is worth noting that, unlike agent performance testing in RL, which usually requires multiple runs due to the randomness in the environment, the iteration process of DDCFR is deterministic (Appendix F). Therefore, we only need to test it once in each game.

 

Thank you once again for your invaluable contributions to our work.

• The comparison with RL algorithms could be explored a bit more.

Thank you very much for the insightful feedback. When formulating CFR's iteration process as an MDP, applying RL to optimize the discounting policy seems to be the most natural and straightforward approach. However, we found that achieving meaningful results using RL (e.g., PPO) is challenging and exhibits significant instability.

In fact, multitask learning is an important issue in our setting. The training games are diverse in size with different converge speed, balancing the learning across different task in multi-task RL is difficult and requires extensive hyperparameter tuning. By the way, it seems like that explicitly conditioning the policy on game IDs may not generalize well to unseen testing games.

Given these challenges, our current approach opts for the simple, scalable and robust ES to optimize the policy. Exploring more advanced multitask RL algorithms and automatic hyperparameter tuning techniques to optimize the policy more efficiently is a promising direction for future work.

• Is equation 4 wrongly formatted.

Thank you very much for your thorough review. In the revised paper, we have made corrections to Equation 4, ensuring that the parentheses and symbols are correctly formatted. We have also diligently reviewed and adjusted the remaining formulas to ensure consistency.

• Add the default DCFR parameters as a constant line in the plots in Figure 4.

Thank you for your suggestion to enhance Figure 4. We have updated the figure in the revised paper to include a constant line representing the default DCFR parameters, which helps readers more easily interpret the results and compare DDCFR's dynamic discounting scheme with DCFR's fixed scheme.

• What happens in the first 500 iterations of DDCFR? Why are those hidden?

Due to the rapid decline in exploitability in the early iterations of different CFR algorithms, their differences are primarily manifested in the later iterations. Consequently, for a better comparison of the algorithms, we focus on the later iterations.

For the sake of completeness, in Appendix E of the revised paper, we have added figures to include all iterations.

Thank you very much for your positive recommendation of our work and your insightful comments. Following are our responses to your concerns.

• Why the exploitability computation can be done in parallel.

We sincerely apologize for any confusion arising from our inaccurate description of "the exploitability calculation and the CFR iteration process are independent". In fact, what we are trying to convey is that the exploitability calculation of the average strategy at iteration $t-1$ and the instantaneous regrets calculation at iteration $t$ are independent. Allow us to provide a more detailed clarification.

On each iteration $t$, our DDCFR first recursively traverses the game tree using the strategy $\sigma^t$ to compute the instantaneous regret $r^t$. Then, DDCFR updates the cumulative regrets $R^t$, the average strategy $\bar{\sigma}^t$, and the new strategy $\sigma^{t+1}$ using the weights $(\alpha\_t,\beta\_t,\gamma\_t)$ generated by the discounting policy $\pi\_{\boldsymbol{\theta}}(s\_t)$. Specifically, $\alpha\_t,\beta\_t,\gamma\_t=\pi\_{\boldsymbol{\theta}}(s\_t)=\pi\_{\boldsymbol{\theta}}([\hat{t}, \hat{E}\_{t-1}^G])$, where $\hat{t}$ is the normalization of iteration $t$ and $\hat{E}\_{t-1}^G$ is the normalized exploitability of the average strategy $\bar{\sigma}^{t-1}$ at iteration $t-1$.

Calculating $\hat{E}\_{t-1}^G$ requires traversing the game tree using the average strategy $\bar{\sigma}^{t-1}$, which leads to additional time overhead under naive implementation. However, it's crucial to note that we can calculate $\hat{E}\_{t-1}^G$ and compute the instantaneous regret $r^t$ in parallel since these two processes depend on two different strategies, $\bar{\sigma}^{t-1}$ and $\sigma^t$, and each requires traversing the game tree once. Consequently, there is no additional wall-clock time overhead associated with the calculation of exploitability in our parallel implementation.

The only time overhead of our DDCFR is the policy inference time, i.e., calculating $\pi\_{\boldsymbol{\theta}}([\hat{t}, \hat{E}\_{t-1}^G])$. However, this cost is negligible compared to the overall iteration time. Please refer to appendix D for more details.

We genuinely appreciate your insightful comment, which has prompted us to refine the description in Section 3.4. Additionally, we have corrected the notation for normalized exploitability from $\hat{E}\_{t}^G$ to $\hat{E}\_{t-1}^G$ in Section 3.1 of the revised paper.

• The scalability of the proposed technique.

Our DDCFR algorithm is founded on the state-of-the-art DCFR algorithm. Consequently, the scope of application for our DDCFR is identical to that of DCFR. When scaling up to larger games, we can leverage numerous well-established techniques, such as decomposition [1] and subgame-solving [2,3], to mitigate problem complexity.

Taking inspiration from your valuable feedback, we plan to explore how to integrate the concept of dynamic discounting into decomposition and subgame-solving techniques to address larger-scale imperfect information games in the future.

[1] Neil Burch, Michael Johanson, and Michael Bowling. Solving imperfect information games using decomposition. In AAAI Conference on Artificial Intelligence, pp. 602–608, 2014.

[2] Noam Brown and Tuomas Sandholm. Safe and nested subgame solving for imperfect-information games. In Advances in Neural Information Processing Systems, pp. 689–699, 2017.

[3] Noam Brown, Tuomas Sandholm, and Brandon Amos. Depth-limited solving for imperfect-information games. In Advances in Neural Information Processing Systems, pp. 7674–7685, 2018.

Thank you very much for your constructive comments and acknowledgment of our efforts. Your previous feedback has been immensely helpful in improving our work's quality. Following are our responses to your concerns.

• The algorithms' numerical performances are depicted starting at 500 iterations. It would be nice to show the performance of the algorithms in early iterations.

Following your valuable suggestions, we have added figures to include all iterations in Appendix E of the revised paper.

• Could you note the actual amount of time required to training the policy in Section 3.4?

Thank you for your helpful suggestion. We should have explicitly stated the training time for the policy to provide key details of the overall approach.

Specifically, we trained the agent for 1000 epochs across 200 CPU cores, which took approximately 24 hours. Per your advice, We have added this information at the training details in the revised paper.

• I would suggest ordering "(i)", "(ii)", and "(iii)", in the same order you state them in Line 264.

Following your suggestion, we have unified the order in section 3.4 of the revised paper.