A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games

Thank you for reviewing our paper and providing valuable feedback. Our responses are as follows. We hope these responses address your concerns and that you will consider raising the score of this paper.

Regarding the computational complexity of the LookAhead module, we will explain it from both theoretical and experimental perspectives.

For experimental verification, please refer to Figure 9 on the last page of the appendix in the main paper. Here, we provide a detailed explanation of this figure. In our experiments, the time-consuming modules include meta-game solving, diversity-based strategy exploration, and non-diversity-based strategy exploration. Among them, the experimental code only differs in the last module between A-PSRO and other algorithms.

From Figure 9b and empirical analysis, it can be observed that the solving time of the meta-game with fictitious play is an exponential function of the population size. A-PSRO has the longest runtime, indicating that A-PSRO has the largest population size during training (additional experiments show that after 200 iterations, the population size of A-PSRO is more than twice that of other algorithms). Considering that in the pipeline improvement, the PSRO algorithm does not expand the population at every iteration but only adds new strategies when the existing ones converge (see Algorithm 2 for details), this demonstrates that A-PSRO's strategy exploration quickly improves the existing strategies in the population to optimal.

From Figure 9a, we can see that if only the LookAhead module is used (ours without diversity), the time spent on strategy exploration in A-PSRO increases almost linearly. From other algorithms (which perform diversity exploration with a certain probability), it can be observed that diversity exploration leads to a nonlinear increase in the time per iteration. This suggests that using the advantage function as an evaluation metric does not introduce more computational complexity compared to diversity metrics.

Next, we provide a theoretical explanation. Assume that payoff U is an [n, n] matrix, and population $P_i$ and $P_j$ are [p, n] matrixs. The current meta-equilibrium $\pi$ is an [n, 1] vector, and the update step size is d.

Taking the classic EC diversity metric in Equation (38) as an example:

$\operatorname{EC}(\mathcal{P}_i \mid \mathcal{P}_j) := \operatorname{Tr} (\mathbf{I}-(\mathcal{L}+\mathbf{I})^{-1})$

$\mathcal{L} = \mathcal{M}_i \mathcal{M}^T_i, \ \mathcal{M}_i = \mathcal{P}_i \times U_i \times \mathcal{P}_j$

Its computational complexity per iteration is $O(pn^2 + p^2n + p^3)$. Additionally, this process requires the exploration of every update directions in pure strategy space to get the one that maximizes diversity.Thus the actual computational complexity is $n \times O(pn^2 + p^2n + p^3) = O(pn^3 + p^2n^2 + p^3n)$.

For the LookAhead process, here is the computation process in our code. First, repeat $\pi$ into an [n, n] matrix $Q$, and then the LookAhead update direction can be obtained through

$min([Q \cdot (1-d)+I \cdot d] \times U \times I).argmax()$

This process has a computational complexity of $O(n^3)$, which is independent of the population size, consistent with the linear time growth observed in the experiments, and lower than the complexity of diversity-based exploration.

The above results are conclusions for zero-sum games. For general-sum games, we have already mentioned in the paper that exploring multiple oracles incurs higher computational costs. Simplifying this process is part of our future work.

Regarding the application of A-PSRO to sequential decision-making in extensive-form games, we discuss it from the following perspectives. First, if the game allows direct extraction of (major) pure strategies and can obtain an empirical normal-form game through simulation, then the A-PSRO algorithm proposed in this paper can be directly applied. In this case, the advantage function can be computed directly and will not introduce higher computational complexity compared to diversity exploration.

For the commonly used approach in PSRO, where RL is used to train the best response as a new strategy, we provide discussions in the "A-PSRO for Large-scale Games" section. For RL processes based on policy gradients, applying A-PSRO requires computing the gradient of a weighted sum of the reward $R$ and advantage $V$. In this case, the optimal response predictor mentioned in the paper is needed to simulate the possible optimal responses of opponents under different strategies $\pi$.

This indeed requires a large amount of data for training. However, given that using RL to compute the best response is already time-consuming, and that introducing the advantage function can bring sublinear deterministic improvements, we believe this trade-off is acceptable.

A typo appears in Theorem 4.1. Thanks for pointing it out.

Thank you for reviewing our paper and providing valuable feedback. Our responses and modifications are as follows. We hope these responses address your concerns and that you will consider raising the score of this paper.

Regarding the deterministic convergence rate, the explanation is as follows. The convergence of the PSRO algorithm depends on both the strategy exploration process and the meta-game solving process. Our improvement only addresses the strategy exploration process, and we have proven its convergence properties.

We believe you might have misinterpreted the figure in the paper. For Transitive games, the best-performing algorithm is A-PSRO without diversity (not with diversity), which indicates that the algorithm using only LookAhead performs the best.

In fact, we analyze the effects of both in the main paper and the supplementary materials. For games that mainly exhibit transitivity, the LookAhead module can converge very quickly to the equilibrium without relying on diversity exploration. This can be viewed as an optimisation process in a convex function with a significant gradient, where rapid convergence can be achieved by directly using the gradient pointing to a local maximum. Games with strong cyclic dimensions can be viewed as convex functions without significant gradient. Although the LookAhead module can converge to the equilibrium, the convergence may be slow in the early stage. Diversity exploration, which is akin to a stochastic optimization process, may directly update the strategy to a region very close to the equilibrium. Experimental results also show that the combination of both methods yields the best performance.

Regarding the computational complexity of A-PSRO, please refer to our response to Reviewer ayi4.

Regarding the code, the explanation is as follows. Due to insufficient time for code refinement, there may be some redundancy issues. We will make the necessary modifications in the future.

About the esential references not discussed, thank you for pointing this out, and we will add the missing references.

Regarding experiments on A-PSRO in more real-world games, we provide the following explanation. Our initial experiments primarily referenced DPP-PSRO and UDF-PSRO. These two works only conducted experiments on the normal-form games as presented in ”Real World Games Look Like Spinning Tops”. These experimental environments consist mainly of normal-form games consisting of pure strategies extracted from extensive-form games, which serve as empirical games that can model the interactions of the agents in the game. In fact, these experimental environments include many real-world extensive-form games (such as Kuhn Poker, Starcraft, etc.).

Given that reviewers have raised concerns about this, we recently conducted experiments in Leduc Poker, which is commonly used for evaluating PSRO algorithms, following the approach of PSD-PSRO. The application of A-PSRO in this game primarily requires approximating the computation of the advantage function, as detailed in the A-PSRO for Large Scale Games section.

The current experimental results of exploitability are:

PSD-PSRO: $4 \times 10^{-1}$, A-PSRO: $3 \times 10^{-1}$.

Due to time constraints, A-PSRO has not been fully fine-tuned. We believe that further improvements in the code could yield better results. If this comparison is necessary, we will add it to the main paper.

Thank you for reviewing our paper and providing valuable feedback. We appreciate your recognition of our work. Our responses and modifications are as follows. We hope these responses address your concerns.

Due to page limitations in the main text, we have placed the algorithmic details of A-PSRO in the appendix. If the final version allows for additional pages, we will move the main algorithm into the main text. Thank you for your suggestion.

Regarding the computational complexity and scalability of A-PSRO, we have addressed this issue in our response to other reviewers. In general, A-PSRO has lower computational complexity compared to diversity-based exploration methods.

Regarding the relationship between A-PSRO and the CFR algorithm, we have also considered this question. As far as we know, CFR is mainly applied to imperfect information games. In fact, how to compute the advantage in imperfect information games is an issue we are currently considering.

For imperfect information games, our idea is to approximate the advantage of different strategies for each information set. For a given strategy, we can use Monte Carlo simulations to obtain rewards under different samplings and opponent strategies. Then, for each sample, we select the strongest opponent and apply a weighting to simulate the advantage function. The main challenge is that this leads to a large computational complexity, and we are considering using methods such as Transformer to improve efficiency.

Regarding the comparison with the PSD-PSRO algorithm in Figure 6, it is worth noting that this experiment was conducted in an environment with three agents. PSD-PSRO, as mentioned in its notation section, is primarily designed for two-player zero-sum games and has not been optimized for multi-agent scenarios. As a result, it shows higher exploitability in this case. For A-PSRO, we designed a method to approximate the advantage function in multi-agent systems, resulting in better performance.

Thank you for your suggestion. We will provide a detailed explanation of the theoretical properties of the algorithm and how A-PSRO applies in different scenarios in separate sections of the main text. We will also add clarifications on in which scenarios A-PSRO is effective, where it may lead to higher computational complexity, and where its effectiveness remains uncertain.

We appreciate your recognition of our work, and we hope the above responses address your concerns. We hope you continue to support our paper.

Thank you for reviewing our paper and providing valuable feedback. Our responses and modifications are as follows. We hope these responses address your concerns and that you will consider raising the score of this paper.

We would like to emphasize that the motivation of this paper is the improvement of the strategy exploration process in the PSRO algorithm. Discussing this problem in the context of normal-form games is mainly because the properties of the advantage function and the convergence of the algorithm can be identified. We mentioned in our response to Reviewer DSTe that we were conducting experiments with Leduc Poker and plan to add the results to the main text.

The use of normal-form games in the title is primarily for the following reasons.

First, previous PSRO variants have typically improved the solution in zero-sum games, while we aim to demonstrate that A-PSRO can also improve the solution efficiency for general-sum games.

Additionally, the main reason for considering normal-form games comes from the paper "Real World Games Look Like Spinning Tops" [1]. For any extensive-form game, extracting all pure strategies can define a corresponding normal-form game (especially in fully observable scenarios). Further discussions in [1] indicate that pure strategies with a wide range of skills extracted from large-scale extensive-form games (such as StarCraft) can also define a normal-form game. This can be viewed as an empirical game containing the most frequent strategies in the original game. The strategies obtained by solving the empirical game are also important for many problems. There are several works about empirical games:

"Choosing samples to compute the heuristic strategy Nash equilibrium"

The primary experimental environment in this paper is based on [1], with some of the experiments coming from both complete extensive-form games and their simplified forms (such as AlphaStar, Go, and Kuhn Poker). In the paper [1], it is mentioned that applying population-based policy learning in these environments is the most effective, so we mainly compare the PSRO algorithm.

This experimental design is identical to previous diversity-based PSRO variants (such as DPP-PSRO and UDF-PSRO). Therefore, we believe the use of normal-form games is justified, as it emphasizes the inclusion of both zero-sum and general-sum games.

One of the contributions of this paper is that A-PSRO improves the reward of equilibrium in general-sum games. This is one reason why it is more preferable than traditional methods.

Regarding the comparison with non-PSRO algorithms, traditional algorithms generally perform inefficiently in the game environments presented in [1]. For example, the previous work "Open-ended Learning in Symmetric Zero-sum Games" compared Self-Play, and "Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games" compared Fictitious Play (regret minimization is primarily used for solving imperfect information games and will not be discussed here). Given that A-PSRO is almost identical to the PSRO framework except for strategy exploration, and that PSRO-based algorithms perform the best in the experimental environments of this paper, we believe this comparison is reasonable.

Since linear programming is not a learning-based approach to solving equilibria, we here mainly discuss Fictitious Play. As mentioned in our response to reviewer ayi4, the time spent on strategy exploration in the PSRO framework is small compared to the time spent on meta-game solving. Compared to running Fictitious Play directly in the original game, efficient exploration can solve equilibria in small populations. We found experimentally that the population size only needs to be less than 10% of the original game.Considering that the solution of the meta-game is of approximately exponential complexity, this process greatly improves efficiency.

On the populations obtained from A-PSRO exploration, Fictitious Play only requires about $10^3$ of iterations to reach $10^{-4}$ exploitability.In contrast, it takes about $10^4$ iterations or more directly using fictitious play.

Considering that none of the other PSRO algorithms compared to traditional methods in the environment used in this paper, we believe it is reasonable. We could add these comparisons, but we think they may perform inefficiently.

As for why we compare with Pipeline-PSRO, the idea of using multiple learners in Algorithm 2 has been applied in both DPP-PSRO and UDF-PSRO, significantly improving performance. Our experimental design and baselines are almost identical to those in these two papers, and this paper also uses multiple learners to update strategies simultaneously.

About the esential references not discussed, thank you for pointing this out, and we will add the missing references. We will also add error bounds in the two figures.

[1] Czarnecki et al. Real World Games Look Like Spinning Tops, NeurIPS 2020.