A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Authors: Yudong Hu
Haoran Li
Congying Han
Tiande Guo
Bonan Li
Mingqiang Li
Venue: ICML 2025 poster (2025)
Keywords: PSRO
Game Theory
Nash Equilibrium
Primary area: theory->game_theory
TL;DR: We introduce the advantage metric to improve the PSRO framework for solving normal-form games.

Abstract: Solving the Nash equilibrium in normal-form games with large-scale strategy spaces presents significant challenges. Open-ended learning frameworks, such as PSRO and its variants, have emerged as effective solutions. However, these methods often lack an efficient metric for evaluating strategy improvement, which limits their effectiveness in approximating equilibria.
In this paper, we introduce a novel evaluative metric called Advantage, which possesses desirable properties inherently connected to the Nash equilibrium, ensuring that each strategy update approaches equilibrium. 
Building upon this, we propose the Advantage Policy Space Response Oracle (A-PSRO), an innovative unified open-ended learning framework applicable to both zero-sum and general-sum games. A-PSRO leverages the Advantage as a refined evaluation metric, leading to a consistent learning objective for agents in normal-form games. 
Experiments showcase that A-PSRO significantly reduces exploitability in zero-sum games and improves rewards in general-sum games, outperforming existing algorithms and validating its practical effectiveness.

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Yudong Hu Haoran Li! Congying Han
Tiande Guo
Minggiang Li? Bonan Li!
Abstract
games (Vinyals et al., 2019; Berner al., 2019). However, achieving equilibrium becomes increasingly challenging in large-scale games with complex strategy spaces (Hernandez- Leal et al., 2017). The development of a unified and efficient equilibrium solver remains a challenge.
Solving the Nash equilibrium in normal-form games with large-scale strategy spaces presents significant challenges. Open-ended learning frameworks, such as PSRO and its variants, have emerged effective solutions. However, these methods often lack efficient metric for evaluat- ing strategy improvement, which limits their ef- fectiveness in approximating equilibria. In this pa- per, we introduce novel evaluative metric called Advantage, which possesses desirable properties inherently connected the Nash equilibrium. ensuring that each strategy update approaches equilibrium. Building upon this, we propose the Advantage Policy Space Response Oracle (A- PSRO), an innovative unified open-ended learn- ing framework applicable to both zero-sum and general-sum games, A-PSRO leverages the Ad- vantage a refined evaluation metric, leading consistent learning objective for agents in normal-form games. Experiments showcase that A-PSRO significantly reduces exploitability in zero-sum games and improves rewards in general- sum games, outperforming existing algorithms and validating practical effectiveness.
The Policy Space Response Oracle (PSRO) offers an ef- ficient open-ended strategy learning framework (Lanctot et al., 2017). Due to its scalability, numerous subsequent works have developed various PSRO variants to enhance the efficiency of solving specific games. In zero-sum games, strategies that emphasize diversity have proven effective for learning Nash equilibrium (Balduzzi et al., 2019). Methods such as UDF-PSRO (Liu et al., 2021), UDM-PSRO (Liu et al., 2022) and PSD-PSRO (Yao al., 2023), which are based on diversity modeling, among the most efficient equilibrium solvers for large-scale zero-sum games. How- ever, while increasing diversity improves exploration effi- ciency, it often results in inefficient strategy improvement due to the lack of proper guidance. To address this issue, our work introduces novel approach by integrating the concept of Advantage as an independent evaluative metric for strate- gies. We establish a mathematical equivalence between advantage maximization and Nash equilibrium, thereby sup- porting the use of advantage a strategic learning objective within the PSRO framework.
In general-sume sun games, Nash equilibria consist of multiple joint strategies, each associated with different rewards (Fo- erster et al., 2018). This contrasts with symmetric zero-sum games, where the Minimax property ensures that all Nash equilibria yield identical rewards (Li et al., 2019). Previ- ous efforts to improve the PSRO algorithm in general-sum games have primarily focused on enhancing the efficiency of equilibrium solving (Zhang et al., 2021), often neglecting the differences in rewards between equilibria. However, recent research has highlighted that different objectives in strategy learning can lead to distinct equilibria (Willi et al., 2022). By adopting an appropriate objective, agents can achieve equilibrium strategies that also maximize rewards (Hu et al., 2022). In this work, we present a method to en- hance strategy rewards using the advantage function. This approach enables our algorithm to achieve higher rewards compared other PSRO methods.
1. Introduction
The Nash equilibrium in normal-form games, encompassing both zero-sum and general- scenarios, is fundamen- tal concept for modeling the behavior of rational, utility- maximizing agents. By approximating these equilibria, agents that outperform humans have been developed in var- ious domains, including chess (Silver et al., 2018), poker (Brown & Sandholm, 2019), and real-time strategy (RTS)
University of Chinese Academy of Sciences, Beijing, China "Information Science Academy, China Electronies Technology Group Corporation, Beijing, China. Correspondence to: Congying Han < hancy @ ucas.ac.cn..
Proceedings of the 4dnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Transitive Dimension
Nash Equilibrium
Transtike Gradient
Player Strategy
Cycllo Gosient
Strong
Medium Reward
High Reward NE
Unstable State
(Row Player)
Dimersion
Direction increase In rewardd (Colume Player)
Column Player Strategy
(a) Zero-sum game geometrical structure
(b) General-sum game geometrical structure
Figure 1. The geometrical structure examples of zero-sum games and general-sum games. Figure (a) shows the structure of a zero-sum game with both transitive and cyclic dimensions. The direction of the strategy gradient refers the expected updates for strategy that maximizes the reward. Figure (b) shows the structure of general-sum game with multiple equilibria. The independent learning process of the agents leads to the update of the strategy in the direction indicated by the arrow.
In summary, we introduce A-PSRO, an improved equilib- rium solver for large-scale normal-form games that lever- ages the Advantage function. In symmetric zero-sum games, the Advantage function exhibits favorable properties, en- abling agents to approach the Nash equilibrium deterministi- cally. By incorporating the Advantage function into existing diversity-basee approaches, we achieve significant improve- ments in learning Nash equilibrium strategies. general- sum games, although the Advantage function is non-convex, its local maxima correspond to equilibria with varying re- wards. By exploring strategies near the global optimum with the objective of maximizing the Advantage function, our algorithm converges to equilibria with higher rewards. We also provide methods for both exact and approximate computation of the Advantage function, allowing A-PSRO integrate seamlessly into existing PSRO frameworks.
where ps represents the probability of choosing action a, To clearly distinguish between different strategies, ot to denote the t-th strategy of player i.
The Nash equilibrium (NE) characterizes a stable state, where no agent can increase its reward by unilaterally al- tering its strategy. For the joint strategy (TI, , is an NE when Vi E {1,... ,"), T, is the best response (BR) the strategies of other agents: ViTi, U((T,, --1) s U; m=;) (U, denotes the expected reward of agent i, T-i represents the joint strategy except for agent i).
Exploitability is defined as the distance of joint strategy (T,, --) and the Nash Equilibrium:
{(,,,_1)) Σ maxx; UA(TE,T=N) (TK, -+]]--
We conducted experiments various games to evaluate our algorithm. In zero-sum games, the strategies derived using the A-PSRO algorithm are significantly closer to equilib- rium. In general-sum games, the A-PSRO algorithm enables agents to learn strategies that achieve globally optimal re- wards, avoiding entrapment in locally optimal equilibria. These results underscore the effectiveness of the A-PSRO algorithm as a unified framework for solving equilibrium.
If the exploitability of a joint strategy (T4, T-4) is 0, it Nash equilibrium.
2.1. Symmetric Zero-sum Games with Transitive Dimension and Cyclic Dimension
Symmetric zero-sum games with two players (i,j among the most studied game forms because their model is consistent with many real-world scenarios (Zhang & Sand- holm, 2022; Sokota et al., 2023). In such games, the joint strategy of the agents is (Tt, R))) with their rewards defined as (T R,) = -U, TT)) The symmetric property im- plies that both agents share the same strategy space 11, and it holds that (, x²) (, (m².m²) m)))
2. Related Work and Background
In this paper, we focus on normal-form games with finite dimensions, typically represented by three key elements denoted as (A, (A,A,))) 2f). Here, .V represents the players in the game, A denotes the action (pure strategy) space of the play- ers, and U refers to the utility function. In such games, agents generally adopt strategies rather than directly choosing actions a E A. π is defined as a probability dis- tribution over actions: π = (p1.P2.... .P.A)) Σp: = 1,
Previous studies have shown that the geometric structure of symmetric zero-sum games resembles a spinning top, con- sisting of both transitive and cyclic dimensions (illustrated in Figure 1(a)) (Czarnecki et al., 2020). The transitive dimen- sion characterizes the absolute strengths between strategies.
2

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
A game is considered transitive if there exists an evaluation function for the strength of strategy, denoted as f=( In strategic interactions, the strategy with a higher evaluation function always yields a higher reward.
The PSRO algorithm presents an effective approach solv- ing Nash equilibrium in games with large-scale strategy spaces. Inspired by the Double Oracle algorithm (McMa- han et al., 2003; Bošanský et al., 2016), PSRO estab- lishes a population to represent strategies for each agent. The initial strategy population is generated randomly as In each iteration, the empirical game matrix for agent is calculated as M, P: x U, x P-.. By adopting the fictitious play solve the Nash equilibrium of neta-game, with payment matrix of (M; can derive the meta-equilibrium for agents: (0,,0-)) 0-.). Then, agent i will search for a new strategy π. f++ usually the best response to the eetta-qqulibrium of the opponent BR(A-i).
(1() = -o(m))))(())))))))) -U;(,,
P. = ........ =.).
The cyclic dimension indicates the presence of mutual re- straint among strategies, similar to the dynamies observed in Rock-Scissor- Scissor-Paper (RSP). In a game with only cyclic dimension, for any strategy oे in the strategy space II, its expectation of reward when facing other strategies is 0:
we
J.en U3( d = O.
Improvements to the PSRO algorithm primarily involve incorporating new meta-game solvers or adopting diverse objectives to guide the generation of new strategies. Addi- tionally, there are open-ended algorithms that explore alter- native equilibrium concepts, such as the a-Rank equilibrium (a- PSRO) (Muller et al., 2020), the correlated equilibrium (JPSRO) (Marris et al., 2021) and coarse correlated equilib- rium (CCE) (Liu et al., 2024).
Real-world games typically exhibit both transitive and eyclic dimensions, making it impracticable to evaluate strategies directly using the aforementioned equations. Strategy up- dates based on gradients may become trapped in the cyclic dimensions, leading to slow convergence towards the Nash equilibrium the transitive dimensions.
In this paper, we focus on refining the process of strategy exploration of PSRO framework. Previous works have typi- cally enhanced strategy generation by increasing diversity. Several methods exist for measuring diversity, including Expected Cardinality (EC) (Perez-Nieves et al., 2021), Be- havioral Diversity Respones Diversity (RD) (Liu et al., 2021) and Policy Space Diversity (PSD) (Yao et al., 2023).
2.2. General-sum Games with Multiple Equilibria
Unlike zero-sum games, general-sum games typically fea- ture multiple Nash equilibria with varying rewards (Tang et al., 2021), as illustrated in Figure 1(b). Previous studies have often focused specific types of equilibria, such as Pareto-optimal equilibria (Sen et al., 2003), MENE (Maxi- mum Entropy Nash Equilibrium) (Balduzzi et al., 2018), and optimal PSNE (Pure Strategy Nash Equilibrium) (Nguyen et al., 2023).
3. From Exploitability to Advantage Function
We first consider symmetric zero-sum games, where both agents share the same strategy space II = { From the symmetry, we have the following property:
In the theory of learning in games, the update rule for each iteration determines the learned equilibrium. Recent studies have focused on improving equilibrium rewards while en- suring convergence to an equilibrium (Foerster et al., 2018; I Letcher et al., 2019). It has been demonstrated that provid- ing appropriate guidance to agents can effectively enhance the utility of the learning process (Hu et al., 2022).
Theorem 3.1. In symmetric zero-sum games, if the joint strategy (x/ xz) is Nash equilibrium, we have (m). x!) and (m,; mz) are both Nash equilibriums.
For strategy in a zero-sum game, its best response BR(TT) is usually a set containing many strategies. However, we have the following property:
2.3. Open-ended Learning Framework
Theorem 3.2. For any two-player game, when the strategy of another player is fixed (denoted as ny). there always exists pure strategy a E A which satisfies that a, E BR(TT). ) Particularly, in zero-sum games, U U2(T,, (1) is always the same for all n; E BR(TT).
Prior research has introduced various methods for solv- ing Nash equilibria, including WOLF (Win or Learn Fast) (Bowling& & Veloso, 2001) and AWESOME (Adapt When Everybody is Stationary, Otherwise Move to Equilibrium) (Conitzer & Sandholm, 2003). The most widely used algo- rithm is fictitious play, favored for its simplicity of execu- tion (Fudenberg& & Levine, 1995). There are also algorithms based on adaptive game playing (Freund & Schapire, 1999). It is worth noting that due to the complexity of general-sum game structures, these algorithms typically exhibit guaran- teed convergence only in zero-sum games.
Then we have:
E m3) = max;: U
+ maxay U,(T), -U,(()))
-U,(B((7)) n ()) UU) (R(x)) nA) -U,,(BR(T)) AA BR(T)) nA).
3

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
According to Theorem 3.1, the symmetry in most 2p0s games allows us to define the distance between single strategy and equilibrium, similar to the exploitability, If we consider (R(x))) as function of n., then the value of U((m), BR(=)) O A) is determined only by ...
the transitive dimension. For example, DPP-PSRO (Perez- Nieves al., 2021) incorporates Expected Cardinality (EC) as regularizer to generate new strategies. However, new strategies generated by diversity algorithms are stochastic, which means they cannot deterministically approach equi- librium.
Definition 3.3. In two-player zero-sum games, we define the advantage function as:
From Theorem 3.4, we can see that increasing the advan- tage of strategy will approach the Nash equilibrium. Since (m.) is convex, we design the A-PSRO to introduce advantage as the objective of strategy learning.
(TTT)) = (7),, df BR(TT) Ag--
From Theorem 3.2, we can that this definition makes sense because the selection of best response BR(x;) does not affect the value of V; Therefore, we also use (T,))=
For the population- strategy update approach in PSRO, we define Vi( (P)) = UT BR(T; PP)), where
UT( (T.)) Ay) to denote the advantage function. Theorem 3.4. In two-player zero-sum games,
BR(TT P2)) = , (T4,
Theorem 4.1. In symmetric zero-sum games, given the m;
population P. P, = { ".... Vτ, E Ps, we have (.(T)) Vi(0; P.). Here, 0, is the equilibrium of the mela-game corresponding to the population P..
E(T,, = -Vi( VV,
Vi(m)) is Lipschitz continuous about Ty, and (T,)) is convex function finctiiu about TT.
Note that (T(TT) I Vi(0,) does not always hold (example given in Supplementary Material). However, we have:
If the game is symmetric. VT,, Vi(T,) S O. The joint strategy (T:, x)) is Nash equilibrium if and only if Vi(TT)) = (,(m)) = O. In gumes with only transitive dimension, (T,))) (Tz) implies U,(Te, mT) > O.
Vat E P;, V,(T S ((,)), when hull(P,) = III
where hull(P.) is the convex hull of population. Theorem 4.1 indicates that the equilibrium of the meta-game approxi- mately maximizes the advantage of the current population.
From Theorem 3.4, we observe that the advantage function has a unique local and global maximum of in symmetric zero-sum games, indicating that the corresponding strategy is a Nash equilibrium. This finding suggests that improving the advantage of strategies guides the learning process to- wards convergence at the Nash equilibrium. Additionally, the advantage function can be computed within the pure strategy space A.
We aim to search for new strategy with deterministic increase in the advantage of population. We have the fol- lowing property of the advantage population iterations. Theorem 4.2. Given the meta-equilibrium strategy 0g if (.,) < O, there exists AT; A and 5 > 0 satisfying:
0O < d 8, V1 d) 0, + d Am,) > V,(0.).
Theorem 4.2 indicates that if the meta- reeta-equlibrimm 6, of the current population is not a Nash equilibrium, we can find a strategy closer to the Nash equilibrium in its neighborhood. Furthermore, according to optimization theory, since the ad- vantage function is convex, this strategy update guarantees to approach the Nash equilibrium at sublinear rate.
4. Advantage Policy Space Response Oracle
In this section, we introduce the A-PSRO framework and its theoretical properties for zero-sum and general-sum games.
4.1. A-PSRO for Symmetric Zero-sum Games
Next, we explain how to improve PSRO's strategy explo- ration process by using the advantage function as regular- ization term. A-PSRO differs from other algorithms only when adding new strategies क. _++1 to the current population P,, and we refer to this process as LA (LookAhead). Given step size d, the new strategy generated is:
In classic PSRO algorithms, new strategies added to the pop- are typically derived through best response, with the opponent strategy fixed as the meta- Nash strategy:
ulation II; = { .... )
++ E BR(O;), where (0,,0,) 0z) = NB(M;,
o/ ++1 (1 d) 0, + d AT,,
Best response-based updates may stagnate within cyclic di- mensions, causing the PSRO algorithm to converge slowly in non-transitive games. To address this, diversity strategy algorithms offer an improvement over the classic PSRO by increasing the probability of discovering novel strategies in
AT: argmax Vi((1 d) 0, + d. Ar).
For dinensionns zero-sum games, the advantage func- tion can be computed through matrix multiplication:
VA (m:) = MinayeA, 3, x U, x aj.

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
making its computational complexity comparable to that of the best response.
In general-sum games, the advantage function is non- convex, which means that strategy gradient algorithms only converge to local maxima. However, when computing the meta-equilibrium 03) within the population- based PSRO algorithm, we prove that there exists space in which strategy converges to the global optimum.
4.2. A-PSRO for Two-player General-sum Games
To the best of our knowledge, ensuring convergence in general-sum games remains challenging problem. Most algorithms can only converge within specific game struc- tures. However, since the advantage function is directly tied to the reward function, it can guide agents to learn strategies that achieve higher rewards. When multiple equilibria are learnable within a game, A-PSRO outperforms general algo- rithms by identifying equilibria with higher joint rewards.
Theorem 4.7. In two-player simplified games, the current population for agent is P. = { ........ ,T;)- Og is the global maximum point of the advantege V; hu)) Then there must exist a non-zero measure set D' hP.l(P.), which satisfies that if 8 is a local maximum point of the advantege Vi in D'' then V:(0)) (..).).
In a two-player general-sum game, action at is called dominated if Vπz E I1 there exists of E A, \ {a}}, J. xz) & U.(a my). It is usually assumed that domi- nated actions can be removed from the game. Therefore, we define the simplified game:
Theorems 4.6 and 4.7 establish that in general-sum games, there exists non-zero measure set near the optimal equilib- rium where the population of strategies converges towards that equilibrium. Strategies close to equilibria with optimal rewards tend to have higher advantage values due to the Lipschitz continuity of the advantage function.
Definition 4.3. We call a game a simplified game if there does not exist dominated pure strategy a; for any player i.
In A- A-PSRO, we adopt strategy exploration approach de- signed to increase the probability of discovering strategy with higher advantage:
For arbitrary general-sum game, a corresponding simplified game can be obtained by removing dominated actions.
T ++1 (1 - d) Og + ATi;
When extending Definition 3.3 to general-sum games, dif- ferent choices of BR(():) will lead to inconsistent advantage functions. Fortunately, in simplified games, we have the following property:
0, argmax Vi(O'), θ
U
O(P,, T.a).
(0,9))E
Here, d is the fixed step size, and the calculation of Am, is the same as zero-sum games. OPP; P, Ti.)) repre- sents the meta-cquilibrium obtained through a fictitious play oracle with (T,, Ty) as initial strategies.
Theorem 4.4. In two-player simplified games, VT for any d' E (R(m)) n,j and 48 > O, there always exists ni which satisfies | TTl < 8 and BR(T)) n A, = {a)]-
This theorem shows that for almost all strategies, their ad- vantage can be defined through unique best response. To maintain consistency, when multiple best responses from op- ponents exist, we select the one that maximizes the agent's own reward to define the advantage function:
4.3. A-PSRO for Large-scale Games
The PSRO framework has also been widely adopted for solving large-scale extensive-form games due to its compat- ibility with neural network-based implementations. Since this paper primarily focuses on the theoretical properties of the advantage function and its applications in normal-form games, related studies will be presented in future work. Re- garding the extension of A-PSRO to other scenarios such as sequential decision-making scenarios, we have conducted some theoretical analysis and experiments. Here, we present several feasible extensions.
Definition 4.5. In two-player simplified games, we define (Ta)) = maxa; U2(Ts; a,), where a₁ E BR((T)) A.A
This definition always makes sense. Similar to zero-sum games, the advantage function has the following properties in simplified general-sum games:
Theorem 4.6. In two-player simplified games,
Empirical Games Solver. The research (Czarnecki et al., 2020) indicates that pure strategies with a wide range of skills extracted from large-scale extensive-form games (such StarCraft) can also define normal-form game. The strategies obtained by solving the empirical game are also important for many problems. There are several works about empirical games such as (Walsh et al., 2004). The A-PSRO algorithm presented in this paper can be directly applied to efficiently solve the aforementioned empirical
Vi, (m))) is Lipschitz continuous.
We assume that the joint strategy (T)))T)) is Nash equilibrium. If (R())) ) n A, has the unique element, then (m,) a local maximum.
Under the same assumption, if (m),,²) and (n² (m],x are both NEs, then (T), xz) Pareto dominates ( x/)
if and only if (mrt) 2 Vx(2)) and V2{2)) 2 (T))))
5

---

We sample a set strategies based on the empirical game as a predefined best response set A. Then we pre-train best response predictor BR"(,,) with parameter y, which A- A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-forat Games
Exple tabeityy hare parn
Explicabiity tb game
Fish FIND
234
259
375
300
24
169
200
(a) AlphaStar
(b) Transitive game
Elo game noise=0.1
Eurboracilty Eis soene W
Explithh crbn--
OM FOO
POOD
18
10
230
100
325
154
200
25
150
(d) Elo game + noise=0.5
(c) Elo game noise= 1.0
(f) Simplified Go game
Figure 2. The exploitability of the joint strategy learned by agents in various zero-sum games is depicted. The reduction in exploitability through population iterations can serve an indicator of the effectiveness in approximating the Nash equilibrium.
Adhuntlgge strelogio Usc gamm
Adventage abrttogka Turntive
Apharttgge deppko pemz
-00
5.0
9-2
12
622
04
(a) AlphaStar
(b) Transitive game
(c) Elo game noise=1.0
(d) Simplified Go game
Figure 3. The advantage distribution of strategies, Lighter colored regions indicate strategies with higher advantage.
games. The solutions can serve as effective approximations of Nash equilibria for large-scale extensive-form games.
C 1f argmin, /rggmax,, UJ(TE, }.)
After training the predictor parameter y with cross entropy loss function BR (TT.) log BR BR"( 7), the approxi- mated advantage function V (mT) can be computed for each strategy m. using the predicted opponent's best response BR" (TT, 7). This allows to train the advantage predictor V. (m;, Y²) with MSE loss. Base on the advantage predictor, we can calculate Vx, (TTT.. with fixed 7 to generate the advantage regularization for strategy updating. We demon- strate through the following theorem that when the approx- imation satisfies certain conditions, can still effectively guarantee the global effectiveness of strategy exploration.
Neural Network Approximation. When PSRO is applied solving large-scale extensive-form games, it typically em- ploys RL methods such as policy gradient to explore strategies. To introduce regularization based on the advan- tage function, we need to design neural network approxima- tions of the advantage function.
can be implemented analogously to classification task. For any mi we generate the label as the first pure strategy maximizing the reward of ,; in its best response set:
Theorem 4.8. If ((.)) ((())-VV, V((T,) < V. (((T:)) the strategy generated by the A-PSRO exploration process will converge to equilibrium strategy with the sublinear convergence rate in symmetric zero-sum games.
BR
(m.)= BR**(FT)
(C1," .. A-11, Ct "41,"" ,CA,)))
6

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
1108 Kewart the
Join Rewart atvareed game
134
035
man
man
OL0
40-
PC 190
F5D-
Thiiing twatcte
Tharee
(a) SSaghhu
(b) Advanced-RSD
(c) Randomly Generated Games
Figure 4. The joint reward of the agent system in general-sum games. The Staghunt game and the RSP game repeated 10 times and averaged for plotting. Randomly generated games contain 100 games with the same reward distribution.
Atagriags of Vetittggie the wow.rreestttheeeett.e gan2
Atuyytagr aintroles reviurtty georoned gores
155
45
0.2
10
08
68
How antagy prnnears
Advanced-Staghumm
(b) Advanced-RSP
Randomly Generated Games
Figure 5. The advantage distribution of strategies in different two-player general-sum games.
Expansion in Multi-player Games. In n-player games (n 2), the advantage function cannot be defined by the best response. We define the advantage function as:
5. Experiment Results and Discussion
We evaluate the performance A-PSRO in multiple game environments. We select the oftte-of-thhaarr game solvers as baselines, including PSRO (Lanctot al., 2017), Pipeline- PSRO (P-PSRO) (McAleer et al., 2020), DPP-PSRE (Perez- Nieves et al., 2021), UDF-PSRO (Liu et al., 2021) and PSD-PSRO (Yao et al., 2023). To ensure a fair compari- son, all other components of the PSRO framework are kept unchanged, with strategy exploration being the only aspect that differs among the algorithms.
(T,,)) = max U1(T,, ((T)), ((T))) = O(II, T.).
((T)) joint strategy without player as the equilibrium of the (n pllyyer subgame when the strategy of player mi ((m;) is computed by an equilibrium oracle O.
In order to efficiently approximate the advantage function, we define the optimistic equilibrium oracle similar to (Basil- ico et al., 2020; Wang et al., 2022).
5.1. Experiments in Symmetric Zero-sum Games
In symmetric zero-sum games, we test A-PSRO with both Ahak and diversity modules on complex real-world games. The environment we chose for testing the normal- form games generalized used in the previous PSRO algo- rithms (Czarnecki et al., 2020; Liu et al., 2022).
((;T)) argmax, (I(TT,mT))) Th NE(U_+ m²)-
Here, NE(U-; nT) represents a Nash equilibrium of the subgame with n; fixed. We give an approximation of the optimistic equilibrium oracle by simplifying it to a two- player game. We view the other agents as single agent {-i) with action space A_,, and approximate advantage as
In Figure 2, we show the results in typical zero-sum games. Additional experiments are presented the Supplemen- tary Material. From Figure we can see that our method achieves a notable reduction in exploitability across all game environments, sometimes by several orders of magnitude, A-PSRO without diversity module outperforms A-PSRO in the Transitive game. The reason is that the diversity mod- ule is designed to navigate the constraints of non-transitive structure, and its impact is limited in games with strong tran-
(T.)) maxx UL(TT, T_; E BR(TT)) i.A...
Based on the above method, the calculation of the advantage function in multiplayer games can also be implemented with pre-trained predictor similar to the two-player setting.

---

A- A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
agenn Game
PST0
D/V
-510
0811
70
F530
0mh-1300
26-
UOT-250
Thanding Baratamm
(a) Exploitability of Zero-sum Games (b) Joint Reward General-sune Games
Figure 6. The exploitability of zero-sur sum multiagent games and joint reward of general-sum multiagent games. Each algorithm is tested in 4 randomly generated identically distributed game environments, and the averages are plotted.
sitive dimensions. The effectiveness of A-PSRO without the Ahea module has a significant decline in all the games, which indicates that our Ahok module greatly contributes to approximating Nash equilibria in all games.
of the algorithms in the aforementioned games. Figure 4 demonstrates that A-PSRO consistently learns the optimal equilibrium strategy, whereas other algorithms acquire dif- ferent equilibria and often stagnate in suboptimal equilibria.
Compared to diversity-buut based algorithms, A-PSRO exhibits higher exploitability during the early stages, primarily due to subgames failing to fully cover the entire strategy space. This observation underscores the importance of incorporat- ing diversity exploration into the learning process. When combined with diversity exploration, A-PSRO achieves a stable and rapid reduction in exploitability, even scenarios where other algorithms experience stagnation.
We further conduct experiments in randomly generated games, and the results are depicted in Figure 4(c). In our experiments, A-PSRO also attains the highest reward.
We depict the distribution of advantage in the aforemen- tioned games in Figure 5. It is evident from the figure that the advantage of general-sum games non-convex. Algo- rithms based on the strategy gradient are likely to converge to different equilibrium strategies from various initial points.
In Figure 3, show the distribution of advantages in differ- ent games. We use the non-linear dimensionality reduction method t-SNE (t-Distributed Stochastic Neighbor Embed- ding) (Van der Maaten & Hinton, 2008) to map the strate- gies into the unit matrix and maintain adjacency between strategies. In games with a strong transitive dimension (Al- phaStar, Transitive game), the advantage function exhibits rapid changes around the Nash equilibrium. Conversely, in games with strong cyclic dimension, when the advan- tage function changes slowly, the diversity module becomes crucial for the learning process of the Nash equilibrium.
In general-sum games, A-PSRO requires exploring multi- ple equilibrium oracles to identify higher-reward strategies. Compared to other algorithms, this inevitably leads to in- creased computational complexity. We will address this limitation the future work.
5.3. Experiments in Multi-player Games
For multi-player games, we test our method in both zero- sum and general-sum games. We randomly generated a series of identically distributed games test environments.
We also compare the running time of A-PSRO with other PSRO algorithms. The experimental results and settings are given in the Supplementary Material for detailed analysis.
Figure 6(a) illustrates the distance of the learned strategies from the Nash equilibrium for different algorithms in multi- player zero-sum games. As shown in the figure, A-PSRO effectively explores strategies with higher advantage and converges toward the Nash equilibrium, whereas other algo- rithms exhibit slower convergence.
5.2. Experiments in Two-player General-sum Games
is worth noting that the compared algorithms do not guar- antee convergence in all general-sum games. To ensure fair comparison, extended the zero-sum game structure to general-sum game with multiple equilibria and verified that all algorithms successfully converged to equilibrium under this setting. The detailed game structure is given in the Supplementary Material.
Figure 6(b) presents the joint rewards of the algorithms dur- ing the training process of multi-player general-sun ceneral-sum games. The results align with Figure 4(c), indicating that A-PSRO consistently learns the equilibrium strategy with the highest joint reward. The parameter setting and experimental details are given in the Supplementary Material.
In Figures 4(a) and 4(b), we present the training results
8

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Busit big sine dorerrrr
exploration leads to nonlinear increase in the time per iteration. This suggests that using the advantage function as evaluation metric does not introduce more computational complexity compared to diversity metrics.
From Figure 7(b) 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. Considering that in the pipeline improvement (McAleer et al., 2020), the PSRO algorithm does not expand the population at every iteration but only adds new strategies when the existing ones converge (see Algorithm 2 in appendix for details), this demonstrates that A-PSRO's s strategy exploration quickly improves the existing strategies in the population optimal.
(a) Strategy exploration time (b) Meta game solver time
Figure 7.
The running time of different algorithms. The left figure shows the cumulative time spent by different algorithms during a single strategy exploration given a meta-equilibrium. The right figure shows the cumulative time spent by different algorithms in solving the equilibrium of the meta-game
5.4. Comparison of Computational Complexity
In this section, we compare the computational complexity of A-PSRO and diversity- PSRO algorithms.
Comparison with Traditional Game Solver. The above results also demonstrate the advantages of population- based equilibrium solving algorithms over traditional approaches. Compared to exact solution algorithms such as linear pro- gramming, PSRO-type algorithms can obtain approximate solutions at lower computational cost. If we consider an exploitability level of 10 10-2 to be sufficiently close to equilib- rium, A-PSRO requires fewer than 50 iterations to achieve this, with a total runtime less than minute, which is signif- icantly lower than the time required for exact solutions.
Assume that the payoff U is [n, n| matrix, and population P. and Pj are np matrixs. The current metta-qqilibrium is an [m. 1] vector, and the update step size is d.
Taking the classic EC diversity metric as an example:
F.C (P: P2)) = Tr (I (I- (C I++
C C= M PXXXUXXX
M,
On the populations obtained from A-PSRO, fictitious Play only requires about 10x of iterations to reach exploitability 10-4, In contrast, it takes about 10 iterations directly using fictitious play. Since the process of solving meta-equilibria based on fictitious play is the most time-consuming com- ponent in the PSRO framework, A-PSRO accelerates the convergence speed of the PSRO framework toward Nash equilibria through efficient strategy exploration.
Its computational complexity is O(pn² + pun + )²). The strategy exploration process requires the exploration of each update directions in pure strategy space to get the one that maximizes diversity. Thus the actual computational com- plexity is O(pn² +yyn + p²) O(pn + +p2n² + )").
Regarding the computation of the advantage function, the following presents an implementation method we use in our code. First, repeat π and derive a [n, n) matrix Q, and then the Ahek update direction can be obtained through:
6. Conclusion
min([Q- - (1- - d) +I d] x U x argmmax))
In this paper, we introduce A-PSRO, a unified open-ended framework for learning equlibrium strategies. We propose the advantage function as evaluation metric for the strat- egy. The advantage function exhibits favorable properties, such as convexity and Lipschitz continuity. Leveraging the ad advantage function, A-PSRO effectively enhances the objec- tive of strategy exploration during population expansion. In zero-sum games, A-PSRO can deterministically approach Nash equilibrium strategies during iterations, significantly reducing the exploitability of learned strategies. Moreover, in general-sum games with multiple equilibria, A-PSRO maximizes rewards during the learning of Nash equilibria. Experimental results demonstrate the robust generalization capabilities of A-PSRO as an onen-ended framework in large-scale environments, highlighting its potential to ad- vance equilibrium theory in multiagent systems.
This process has a computational complexity of O(n²). which is independent of the population size, and lower than the complexity of diversity-basee exploration.
In our experiments, the time-consuming modules include meta meta-game solving, diversity- based strategy exploration, and non-diversity-baee strategy exploration. Among them, the experimental code only differs in the last module be- tween A-PSRO and other algorithms.
From Figure 7(a), we can see that if only the Lhok 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

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Acknowledgements
Conitzer, V. and Sandholm, T. AWESOME: A general mul- tiagent learning algorithm that converges in self-play and learns best response against stationary opponents. In Machine Learning. Proceedings of the Twentieth Interna- tional Conference, pp. 83-90, 2003.
This paper is supported by National Key R&D (Research and Development) Programe of China (202IYFA10004)) the National Natural Science Foundation of China
(No.12431012).
Czarnecki, W. M., Gidel, G., Tracey, B., Tuyls. K., Omid- shafiei, S., Balduzzi, D., and Jaderberg, M. Real world games look like spinning tops. In Proceedings of the 34th International Conference on Neural Information Process- ing Systems, volume 33, pp. 17443-17454, 2020.
Impact Statement
This paper presents work whose goal is to advance the field of PSRO framework for solving equlibrium strategy. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Foerster, J., Chen, R. Y., Al-Shedivat, M., Whiteson, S.,
Abbeel, P., and Mordatch, I. Learning with opponent- learning awareness. In Proceedings of the 17th Interna- tional Conference on Autonomous Agents and MultiAgent Systems, AAMAS '18, pp. 122-130, 2018.
References
Balduzzi, D., Tuyls, K., Perolat, J., and Graepel, T. Re- evaluating evaluation. In Proceedings of the 32nd Inter- national Conference on Neural Information Processing Systems, volume 31, pp. 3272-3283, 2018.
Freund, Y. and Schapire, R. E. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79-103, 1999.
Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnecki, W., Perolat, J., Jaderberg, M., and Graepel, T. Open-ended learning in symmetric zero-sum games. In Proceedings of the 36th International Conference Machine Learning, volume 97, pp. 434 443, 2019.
Fudenberg, D. and Levine, D. K. Consistency and cau- tious fictitious play, Journal of Economic Dynamics and Control, 1965-7):1065-1088 1995.
Hernandez-Leal, P., Kaisers, M., Baarslag, T., and de Cote, E. M. A survey of learning in multiagent environments: Dealing with non-stationarity. CORR, abs/1707.0915 2017. URL http://arxiv.orrg abs /bt//107..99
Basilico, N., Coniglio, S., Gatti, N., and Marchesi, A. Bilevel programming methods for computing single- weader-multi-followe equilibria in normal-form and poly- matrix games. EURO Journal Computational Opti- mization, 8(1):3-31, 2020..
Hu, Y., Han, C., Li, H., and Guo, Modeling opponent learning in multiagent repeated games. Applied Intelli- gence, (113):17794-17211 2022.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q. Hashme, S., Hesse, C., Józefowicz, R., Gray, S., Olsson, C., Pa- chocki, J., Petrov, M., de Oliveira Pinto, H. P., Raiman, J.. Salimans, T., Schlatter, J.. Schneider, J., Sidor, S., Sutskever, I., Tang, J., Wolski, F., and Zhang, S. Dota with large scale deep reinforcement learning. CoRR, abs/1912.06680,, 2019. URL http:://axxii abs/ abs/1912. 06680.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J. Silver, D., and Graepel, T. uni- fied game-theoretic approach multiagent reinforcement learning. In Proceedings of the 31st International Con- ference on Neural Information Processing Systems, pp. 2017.
Langley, P. Crafting papers machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Bowling, M. H. and Veloso, M. M. Rational and conver- gent learning in stochastic games. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pp. 1021-1026, 2001.
Letcher, A., Foerster, J. N., Balduzzi, D., Rocktäschel, T., and Whiteson, S. Stable opponent shaping in differen- tiable games. In 7th International Conference on Learn- ing Representations, pp. 1-20, 2019.
Bošanský, B., Lisý, V., Lanetot, M., Čermák, J., and Winands, M. H. Algorithms for computing strategies in two-player simultancous move games. Artificial Intel- ligence, 237:1 2016.
Li, S., Wu, Y., Cui, X., Dong, H., Fang, F., and Russell, S. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4213-4220, 2019.
Brown, N. and Sandholm, T. Superhuman ai for multiplayer poker. Science, 365(6456)::85- 890, 2019.
10

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Liu, S., Marris, L.,, Lanetot, M., Piliouras, G., Leibo, J. Z.,, and Heess, N. Neural population learning beyond sym- metric zero-sum games. In Proceedings of the 23rd Inter- national Conference on Autonomous Agents and Multia- gent Systems, AAMAS '24, pp. 1247-1255, Richland, SC, 2024, International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9798400704864.
Sen, S., Airiau, S., and Mukherjee, R. Towards a pareto- optimal solution in general-sum games. In Proceed- ings of the Second International Joint Conference on Au- tonomous Agents and Multiagent Systems. pp. 153-160) 2003.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M. Guez, A., Lanctot, M., Sifre, L.., Kumaran, D., Grae- pel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362 (6419))1140-11) 114,, 2018.
Liu, X., Jia, H., Wen, Y., Hu, Y., Chen, Y., Fan, C., HU, Z.,, and Yang. Y. Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. In Advances in Neural Information Processing Systems, volume 34, pp. 941-952, 2021.
Sokota, S., D'Orazio, R., Kolter, J. Z., Loizou, N., Lanctot, M., Mitliagkas, L,, Brown, N., and Kroer, C. A unified ap- proach to reinforcement learning, quantal response equi- libria, and two-player zero-sum games. In The Eleventh International Conference on Learning Representations, pp. 1-41, 2023.
Liu, Z., Yu, C.,, Yang. Y. sun, p.. Wu, Z., and Li, Y. A unified diversity measure for multiagent reinforcement learning. Advances in Neural Information Processing Systems, volume 35, pp. 10339-10352, 2022.
Marris, L., Muller, P., Lanctot, M., Tuyls, K., and Graepel, T. Multi-agent training beyond zero-sum with correlated equilibrium sota-solvers. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 7480-7491, 2021.
Tang. Z., Yu, C., Chen, B., Xu, H., Wang, X., Fang. F., Du, S. S., Wang, Y., and Wu, Y. Discovering diverse multi- agent strategic behavior via reward randomization. In International Conference on Learning Representations, 2021.
McAleer, S., Lanier, J., Fox, R., and Baldi, P. Pipeline psro: A scalable approach for finding approximate nash equilibria in large games. In Proceedings of the 34th Inter- national Conference on Neural Information Processing Systems, volume 33, pp. 20238-20244 2020.
Van der Maaten, and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 9(8))2579 2605, 2008
Vinyals, O.,, Babuschkin, I., Czarnecki, W. M., Mathieu, M.,
Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, I.., Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L., Gulcehre, C., Wang. Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T. Lillicrap, T. P., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. Grandmaster level in starcraft ii using multi- agent reinforcement learning. Nature, pp. 1-5, 2019.
McMahan, H. B., Gordon, G. J., and Blum, A. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the Twentieth International Conference on International Conference on Muchine Learning, pp. 536-543, 2003.
Muller, P., Omidshafiei, S., Rowland, M., Tuyls, K., Pérolat, J., Liu, S., Hennes, D., Marris, L., Lanetot, M., Hughes, E., Wang, Z., Lever, G., Heess, N., Graepel, T., and Munos. R. A generalized training approach for multiagent learning. In 8th International Conference on Learning Representations, pp. 1-35, 2020.
Walsh, W. E., Parkes, C.C and Das, R. Choosing samples compute heuristic-strategy nash equilibrium. In Faratin, P., Parkes, D. C., Rodríguez-Aguilar, J. A., and Walsh, W. E. (eds.), Agent-Mediated Electronic Commerce V. Designing Mechanisms and Systems, pp. 109-123, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978- 3-540 25947-3.
Nguyen, D., White, L.,, and Nguyen, H. Social optimum equilibrium selection for distributed multi-agent optimiza- tion, 2023. URL http:t::: //t::///raii http//axivvv.//// org/ abs//////////// 2307.. 13242.
Perez-Nieves, N., Yang, Y., Slumbers, O., Mguni, D. H., Wen, Y., and Wang, J. Modelling behavioural diversity for learning in open-ended games. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 15244, 18-24 24 Jul 2021.
Wang, K., Xu, I.., Perrault, A., Reiter, M. K., and Tambe, M. Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 2219-5227, 2022.

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Willi, T., Letcher, A. H., Treutlein, J., and Foerster, J. COLA: Consistent learning with opponent-leaming awareness. In Proceedings of the 39th International Con- ference on Machine Learning, volume 162, pp. 23804- 23831, 2022.
Yao, J., Liu, W., Fu, H., Yang, Y., McAleer, S., Fu, Q. and Yang. W. Policy space diversity for non-transitive games. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, pp- 67771-67793, Red Hook, NY, USA, 2023. Curran Asso- ciates Inc.
Zhang, B. H. and Sandholm, T. Team correlated equilibria in zero-sum extensive-form games via tree decomposi- tions. Proceedings of the AAAI Conference on Artificial Intelligence, 3655):5252-5259 Jun. 2022.
Zhang, Y., An, B., and Cerný, J. Computing ex ante coor- dinated team-maxmin equilibria in zero-sum multiplayer extensive- form games. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 35, pp. 5813- 5821, 2021.
12

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
A. Omitted Proofs
A.1. Proof of Theorem 3.1
Theorem. In symmetric zero-sum games, if the joint strategy (m) T3) is a Nash equilibrium, we have m3)) and (n, m3) are both Nash equilibriums.
Proof. From the definition, the joint strategy m3) is Nash equilibrium implies that the exploitability E(T,) m 0.
Then we will have:
{ { m3) m [ - U1( . x3)1 + max+; - 0.
(1)
This indicates that:
Max,;IUU(TT,, m3)) - (+ mf)1 = maxx; -
U, 0.
(2)
Then we prove that Ui(x), = Un( (T m3) 0. If the reward of agents are not all 0, since the game is zero-sum, we assume that:
U((m! Ug(T,)
(3)
Since the game is symmetric, we will have:
m3) UT nT)) = O.
(4)
This indicates that:
max (m) [ m²) (n (3)] #0.
(5)
which leads to contradiction. Therefore, prove that the rewards of both agents are 0.
From the equations above we have that (T! TT.) = Ug (T) n ) O. Since πř is a best response to T.. we can see that TT
is also a best response to .7. This indicates that (T] mT)) and (mī m²) are both Nash equilibriums.
A.2. Proof of Theorem 3.2
Theorem. For any two-player game, when the strategy of another player is fixed (denoted Ty), there always exists pure strategy O₃ A which satisfies that a, BR(T,). Particularly, in zero-sum games, (T TT)) is always the same for all T, E BR(T)).
Proof. We assume that there exists strategy Tद (PI..... PIAi) which is the best response of T.. Then have:
U( m3) = pi U.(ai, (a((aa,m)))) mj) + ... PlA S maxie(L,- M1 U,(a), mT),
(6)
which implies that a₁ E A is best response to Tj-
In zero-sum games, we assume that the strategy of the player is fixed as n.. Then we have:
BR n.) = argmax,, (TT,
We assume that for all nú E (R())), the reward of player j is Uy (TT nT) U If the game is zero-sum, the reward of player i is U,(T,, RT) 0 This implies that in zero-sum games, U,(TT,, Ty) is always the same for all ny E BR(x). O
A.3. Proof of Theorem 3.4
Theorem. In two-player sem games,
E[(T,, my) = - (V, + + (,(T)))
(i(T))) is Lipschitz continuous about ,i and VV(z;) a convex function about w;.
13

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
If the game symmetric, VT, (T,)) O. The joint strategy (m]: m)) is Nash equilibrium if and only if Vi(m))
V3 (m)) = In games with only transitive dimension, Vi(T.) D/ (T₃) implies (TT,,, my) >
Proof.
From the definition, we can easily find that {,;; mz) = (x) A1l
We define the domain of strategies which satisfies that Ps 2 0. Σ k= Pk 1, and |A] is the dimension of the action space
D (P1,P2, .PPAA)))))) -P()))}
A = {01,-.,, -14))
In order to prove that - (m,) (T) is convex function about Tú, we need to prove that for पो.प E D, and c E (0, 1), we have - [V((1 - c)m² + c f -11 - -=))((²)) - (x.)
We assume that Tæ- = (p)..... .P/A)) and .. = (pî ... .P(A)) Then we have:
[ - c)m + + U:((1 -c)= , ag E EEA EANBR[( c))² + ca
(1 e)U ao) + (T) ap)
(8)
2 (1 - c) ab) + dUi( (T) of E AnBR(T)) E {1,2}
= (1 c){{ (T,))
This implies that the inverse function of advantage function - Vi (T,) is convex about ,..
Then we prove that (T,T.) is Lipschitz continuous about ,.. We assume that म; = (p1, "P,))".))))))) .PIA)). T/. = = Am,
(p1 + Api. .......... PLAI + APlA)) which satisfies that Σ AAI k= App- = O, and aj E AABBR(T; + AT;), au E (R()).
V(Pi + Ap1.- ... PPAI + APIAI) VI(II... .PLAI) (PAI)) =Vi(T; + AT, o/) Uz(TT;: ao)
(9)
=(1 + (p (6) +.... (MA + Apqa))((((aa)))) P1Us(a1, -...-...11 P|A Ui (1n an)
=A,Ap1 + ........ A Ant + [U ab) ) Uf(T;; [o)]
where A., Am are constants.
Then we will prove that there exists M such that vg > 0, the following conclusion holds:
(Ue(Ts, d6) Ue(Ts no) 5M, when max|Apu S 5.
(10)
First we consider that de CAn (R(m:), this indicates that (U: d() U2(Ti, an)] Then we consider that a & An BR mT), which means that:
U2(T; an) > Us(TT, db)
(11)
iusiniotzcontinuuus We prove that U,(T; a) is Lipschitz continuous with respect to T.. VT, Vam we have:
LAI
LA
U.(m; + AT,, am) U,4,, am)
Σ (Pk + U, am)
pk U. (ak: am)
k=1
= A: am) + +... A am)
(12)
LA
SMM where max|App/ and M max a'EA
Σ Ul)a;;a)))
Since we considering games with finite dimension, M has consistent upper bounds. Then we have:
Um ao) + 8M 2 U. 2 U.( ob) 2 Ui(m; 06) - -5M.
(13)
Using Equation (12) twice results in (13). This indicates that 0 < UT(TT d6) - Ue( (a) S 28M. According to Equation (9), we have
(((1 + Apr. .PIAI + APpAi) - Vi(p, "M
.PLA)) I max; Aş - 1 + 28M
(14)
This means that (T,,) is Lipschitz continuous about N..
14

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
From Theorem we can easily find that if the game symmetric, (TTT)) 0. The joint strategy mp) Nash equilibrium if and only if (((m)) O.
In games with only transitive dimension, the best response is the same x for all strategies n;. Then we have:
{ m)) (1((m) ( E E m3))
(15)
So n is closer to the Nash equilibrium than x² in the transitive dimension, which means that U,(,), x3) > 0.
A.4. Proof of Theorem 4.1
Theorem. symmetric zero-sum games, given the population P: P, ! ........ v.f E Pi, we have V(TT)) S Vi(0, P.). Here, 0, is the equilibrium of the meta-game corresponding to the population P;.
The population P, can be viewed as a subgame. Applying Theorem 3.4 for this subgame we get the following property:
Proof.
VT E P., Vi(T. P.) S V100 P.).
(16)
Then we the following derivation:
ViTT() = Ui(m BR(x{))= = -U(B))())
S (BR (B()) Unt,,, BR (T/() where BR"(z() = argmin,'ER, (''
(17)
S U,,O, BR BO.)).)
= V.(0: P:).
From this theorem, can that Vi(0; P:) is an upper bound for V=(T)) This suggests that exploring new strategies in the neighborhood of 0, increase the probability of improving the advantage of population.
Here we give an example of (m+²) 2 V.(O)).
Q1
02
A3
Q4
Q5
C6
01
(0.0)
(1,-1)
(-1,1)
(-0.1,0.1)
(0.9,-0.9)
(-1.1,1.1)
02
(-1,1)
(0,0)
(1,-1)
(-1.1,1.1)
(-0.1,0.1)
(0.9,-0.9)
03
(L,-1)
(-1,1)
(0,0)
(0.9,-0.9)
(-1.1,1.1)
(-0.1,0.1)
04
(0.1,-0.1)
(1.1,-1.1)
(-0.9,0.9)
(0.0)
(1,-1)
(-1,1)
05
(-0.9,0.9)
(0.1,-0.1)
(1.1,-1.1)
(-1,1)
(0.0)
(1,-1)
Q6
(0.9,-0.9)
(1.1,-1.1)
(0.1,-0.1)
(1,-1)
(-1.1)
(0,0)
In this game, assuming that the current population is Pi = P, = {a1, as), then Va(as) = -1 However, V.(0, | P.)
(aa)) = -1.1 -1.
A.5. Proof of Theorem 4.2
Theorem. Given the meta-equilibrium strategy 8;, if (0..) < 0, there exists An, E A and > satisfying:
vo<d< V. ((1 - d) 0, + d. Am,) ((())).
Proof. From Theorem 3.4 we have that the inverse of advantage function (m;)) convex about ,,, Since V.(O,) <
0 max (T;),, from the convexity of the function -V, we can find direction of descent in the domain of the strategy
D [(Pi,** -PA)) Pm 0, E. Pm 1}:
38, ED, 44 vo<d<0'
V1((1 - d) 0, + d. x')= (..).).
(18)
15

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Since the domain of the strategy D is convex combination of pure strategy space A, n' E D can also be expressed
convex combination of all elements in A. This means that there exists Ar, E A, which satisfies that (T', Arri) 0. We define that Kr Am 8' Then we have:
vo<d<ō, Vi((1 - d) 0; + d. (m;) > Vi(O:).
(19)
A.6. Proof of Theorem 4.4
Theorem, In two-player simplified games, VT, for any df E a Ui(Te, az) and Vo > 0, there always exists Ti. which satisfies | Til < and BR(T)) n = {at]-
Proof. We assume that म. = (p), ... -P)..)). Since we are searching for Ti in the neighbour of n;, without loss of
generality, we assume Pt > 0, vt E (1,..., ....,,,A)))) -Aii).. Since the game is simplified, the pure strategy of is not dominated. Therefore, there exists m E {1, .. I..I.. VaJ # aj. a' ..y-- < df Uy a.a.. We choose गÝ. (1-(++))m I-pm Pl. , (1+
50pm' 1m P.A.)). it is obvious that | mil < 5. Then we proof Va'j + alj, a²z BR(T;)), we have U,(T', d,)
I-Pmn af). It obvious that
()(mi,a)) - o() -pyly -U, a - d,j 0/,U,, U, o²) + ... + (d) U, d - dj. U, a...a,m) d.A.1)- =
(20)
Then we have
Uf d,) - U,( 03)) = 1- 1 (1+ Pm
Pi (a Uy af - d/ UU..a) a;)
1 - Pm
+ (1 5) (a), Uy 0, d₃ Uj a
1 (1 + 8) Pm
PIA.(a3. Uy a//a al U, a/Ail) (21)
Pm
Pm pmp (a) Ug a.hh d, Ug a. 00
= 8
1-Pm Pm
This indicates that BR[ n A₁ }.
A.7. Proof of Theorem 4.6
Theorem. In two-player simplified games,
Vi, (T;)) is Lipschitz continuous.
We assume that the joint strategy (T, nT)) is a Nash equilibrium. If BR(T,) n.A, has the unique element, then (T;))) is a local maximum.
Under the same assumption, if (T, m3) and (T), m/) are both NEs, then (T), mz) Pareto dominates (T7/=z) if and only if (i! 2 (m²))) and (T()) 2 (TT))
Proof. In Theorem 3.4, the proof of the Lipschitz continuity of the advantage function does not require that the game is zero-sum. Therefore, we can similarly prove that (T,))) is Lipschitz continuous in two-player general-sum games.
If the joint strategy (mi, mT) is a Nash equilibrium, we have that π BR(T.). We assume that:
BR(*)nA) {.
(22)
which means that:
Vag + af. U,(Ti, (z) < (T,TT,))
(23)
From the proof of Theorem 3.4 we have that Vn,, Vo, Ue(m, a) is Lipschitz continuous about n. Then there must exsits 5 > 0, which satisfies that:
VO E BT(T)), (BR(T)) n AA) S (BR(m)
(24)
16

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
where (T,) is the open ball of radius ò centered on Ty. From Theorem 3.2, have that {a]) -BR(z() n.g. then we have:
(m.) = UT mT) ( ag)
2 U,(TT, TT)) = U Ui(T a9) (becaue(Ty, Ty)is Nash equilibrium)
(25)
We assume that the elements of (R(T)) n A, are unique in assumption. Since (T,, Ty Ty)is Nash equilibria, πj is the optimal response to mj. This indicates that Jj =a (xz is linear combination of BR (T:) nA))) Therefore the third holds. This illustrates that (TT)) is a local maximum of the advantage function V..
Under the assumption that BR (T)) MA are unique, we have (m²²)) = U,(m), mz) and (T (, mz) Therefore,
(mt, m Pareto dominate (mā. m;)) is equivalent to Ui(=! m3) (M] x3) and (5 mf) 2 ( m ) Since
(m), mf) and (m3, xz) are both Nash equilibrium, this holds if and only if Vi 2 V(T and (T()) 2 (j(()) )
A.8. Proof of Theorem 4.7
Theorem. In two-player simplified games, the current population for agent i is P: .... m . 0g is the global maximum point of the advantege Vi in hP,) Then there must exist a non-zero measure set DD hhull(:)), which satisfies that if 6 is a local maximum point of the advantege V, in D', then (0)) = V.().).
Proof. We assume that the strategy of the player i is m (p1,-.. .PAA.). For k {1,... [Ayl], we define gT(TT))
af),, where at Aj. Then we have:
ge PIA.)) = PLU PiU,(a,, a2) +.... +.... UlA. (a) .a)).
(26)
If the elements in set (R(T)) n Aj are not unique, there must exists k and k'' which satisfies that gu (T(T))) - gue (m.). Since the game is simplified, (U, (a),a))) ... U,(a|Ail,,0
,a5)) and (Ug(at, af)) )..,, (U A:: .f)) are linearly independent
vectors. This indicates that क. satisfying gt (T.)) = gr (T;) is zero measure set and non-dense in the domain II, We define
DO = = n; E (BR))) Aj) is singleton set}.
(27)
Since m. satisfying that there exists & and k with gu (TT: - g (Tx) is non-dense in the domain II, we consider the projection of those Ti onto hu.) This indicates that either D an empty set (which means that ग. intersects different functions g covers the plane of hu)) or (h,)l(P;) \ D2) is non-dense set.
D is an empty set means that VT; hull(P:), (m:) = (m.). Since the game is simplified, VT;; E hhul(P.), U((Te, at) = U,(T ) Thus, we can remove of feom Aj, which does not affect the calculation of (TT)). This is because in this theorem, 9k and gk are always the same on hull(P) when D is an empty set. Since all operations in this theorem are performed on hull(P), and both y correspond to the same Uj. by the definition of V, it is only necessary to keep the one corresponding to the larger Ug. Therefore, we can remove another one for simplification.
If (P:)l(P:) \ DO) is a non-dense set, we consider separately whether 0₂ E <Do If 0g E D there must exists non-zero measure set DJ C hull(P.), which satisfies that:
VT, E DJ, BR(T))AA = BR(O,)
(28)
This indicates that (m,,,) is a linear function about n.. Since 6; is the global maximum of this linear function, there must exists non-zero measure set D' C hull(P:), which satisfies that if 0% is a local maximum in D', then (0())) = (O.).).
If 0, E (Iull(P.)) \ D we assume that:
argmax, (bx) = {1, .1}.
(29)
Due to the Lipschitz continuity of Uj. there must exists d > 0, which satisfies that:
AT:
A VAT, BR(0; +
d) C (m)....... .493.
(30)
A
17

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Since 9h (T,) hyperplane corresponds to linear function, the value of function ()())) on the ray 0, + Ar
-d 0 < 8 < d
Ard
either all maximal or all non-maximal for all k. Thus we can assume that there is a unique pure strategy best response x..k k E (1.-.. .{} for a strategy on that ray.
Thus, the open ball (2(+ can be divided into at most [Ayl region DR h E {1, ... |Ayl]- In every region D* Vi(mT) is linear function about иy Since Og is the global maximum of this linear function, there must exists non-zero measure set D' C Ba(B)). which satisfies that if 0g is a local maximum in D', then vi(O)) (.(O.).
A.9. Proof of Theorem 4.8
Theorem. Assuming that VV,, (TT:) - n., [mm)) < $ V., (T,)),, the algorithm will converge to equilibrium with sublinear convergence rate in symmetric zero-sum games.
Proof. We use to denote n; and f(x) to denote (m;)). We use f to denote the global maximum of the function f. According Theorem 4, f()) is Lipschitz continuous about x, and (x) is convex function about From the convexity, there exists M for Vn.
f(a = f(x)) = (f)() f(z) + M |))a()) -
2
S {(<))
2n
V 12 + M
2 - 3
4
{(())²
(31)
3
(
2n
8
f(x)
(
3
9
By assuming that S 48. we have
2n
8M
(32)
3
Then we have:
f(x ((-n)\(()) s f(x) 2 [
(33)
We denote = =x- aa-1/ -n))(((x), then we have:
( S - [
S + [5xx)
T (x - xx)) - - ((x0)
1
(34)
= =f" + 21
[|0 x" 2 - || x² - [({{))1
= fr + 27
[1 x² 11 - 11 1²)
(((x))--1)
(| -x=11= 20- -11000 2011 11²))
2n i=1
(1|=00 - x²11 -13 - 1| - x² 112)
(35)
2n
1000
xx 11
2n
is obvious that f(=') is non-increasing, then we have:
f {2²²) - fr k
(5 (x
-))
<
||200 xx1
(36)
2km
18

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
The convergence rate is O This indicates that the approximate gradient-based algorithm will converge the equilibrium with sublinear convergence.
B. Algorithm Introduction and the Pseudo-Code
B.1. Fictitious Play
In fictitious play algorithm with two players, strategies are randomly initialized as (n.. x2). In iteration agents select the best response to the average strategy of its opponent:
BR (R( TT))
(37)
Fictitious play has convergence guarantees simple structures such as two-player zero-sum games. However, has the disadvantage that convergence can be very slow in games with large strategy spaces.
B.2. Classic PSRO Algorithm
Algorithm Policy-Space Response Oracles
Input: initial policy populations for all players P. Compute the expected utilities UP for each joint E P. Initialize meta-strategies 0: (NIFOR
while iters e in (1.2....) do
2: for player E (1, .n] do
3: for many episodes do
4:
Sample - ~ 0-; 5: Train oracle T& over O --))
6: end for
7:
P; : P; P
8: end for
9: Compute missing entries in UP from P
10: Compute meta-strategy 0 from UP
11: end while
Output: Current solution strategy 0, for player i.
Pseudo-code of the classic PSRO algorithm is given in Algorithm 1. UNIFORM denotes random sampling according to the uniform distribution. The two main components of the algorithm are the exploration of the new strategy nं and the computation of the meta-strategy 0. In this paper. we focus on improving the PSRO framework from the perspective of new strategy exploration. We use the meta-strategy solver with exactly the same parameters as the other PSRO algorithms in our comparison experiments (Perez-Nieves et al., 2021; Liu et al., 2021).
B.3. A-PSRO for Solving Zero-Sum Games
In this section, we provide the algorithm for the generation of new strategy, and the rest of the framework is the same as other PSRO algorithms. We assume that the current population is (Pr, Pz). where P; = { ... . Since A-PSRO primarily improves the strategy exploration process, we outline how to enhance strategies through exploration within single PSRO iteration. The other components of the algorithm remain consistent with the PSRO algorithms compared in this study.
It is worth noting that the PSRO variant algorithms typically prioritize updating existing strategies. New strategies generated randomly only when the existing ones fail to improve. For further details, please refer to the DPP-PSRO or PSD-PSRO algorithms. Similarly, in our algorithm, the agents initially decide to update the last strategy T/. The new strategy o is generated and incorporated into the population only if the update process does not enhance the utility. As LookAhead updates the strategy in the transitive dimension, we set its learning rate lower than ||0|| to prevent stagnation as the strategy approaches the Nash equilibrium.
19

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Algorithm 2 Strategy exploration process of A-PSRO in zero-sum games
Input: Population (Pt. Pj), meta-Nash equilibrium (0,, B2), strategy to be updated of the agent m/. Parameter: diversity weight Aa. learning rate 4, improvement bound Cm--
1: Randomly generate dr U l].
2: if d, I Xd then
3: ATT = argmax A EC(P: (mf) U ((1 4.) af +4 Am) P2)).
4:
o. = (1 (1-4)- + Ar.
5:
else
6:
Randomly generate 4 U min(k, 4r [[,
7:
ATT = arrgaax A [:[(1 1,) + 4. AT).
8:
(1-11-4)
+ Am.
9: end if
10: if my xL4x6,
1 12 Cm then
xxxxx
11:
T = T
12: else
13: mp = _.. Then randomly generate प. = P (The randomly generated strategy n; will be updated
in the next iteration, this is equivalent adding an explored strategy.)
14: end if
15: return P..
Output: P.
In Algorithm 2, we combine the diversity module and our LookAhead module. The HC (expected cardinality) function is the diversity measure used (Perez-Nieves et al., 2021):
EC(P: P2) = Tr (c (C-))
(38)
L - C-M.M. = P;
Here Tr denotes the trace of a matrix. In all zero-sum game experiments, we control the proportion of diversity and LookAhead modules with uniform parameter Ag. We find from our experimental results that A-PSRO achieves good convergences in games with different transitive and cyclic structures.
B.4. A-PSRO for Solving Two-Player General-Sum Games
In experiments with general-sum games, we find that the diversity module does not contribute to improving the reward of the strategy learning process. Therefore, the strategy exploration process of our algorithm A A-PSRO contains only the LookAhead module. The Pseudo-Code of A-PSRO is given in Algorithm 3. In Algorithm the meta-solver of the oracle O(P,, Py mfg)) is the fictitous play with 1000 itereations. In our experiments, set the number of repeats k 10. The rest of the A-PSRO algorithm in the general-sum game is consistent with the zero-sum game.
B.5. A-PSRO for Solving Multi-Player Games
The main modification in applying A-PSRO algorithm to solve multi-player games is the computation of the advantage function. Unlike the two-player game with direct utilization of the best response BR, the computation of the advantege of the strategy requires the usage of oracle O πz). In multi-player games, we adopt the joint best response as an approximation to the optimistic equilibrium. The Pseudo-Code of calculating the advantage in A-PSRO is given in Algorithm 4. Besides the computation of the advantage function, A-PSRO is consistent with the two-player game in the multi-player game.
20

---

A- A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Algorithm 3 Strategy exploration process of A-PSRO in general-sum games
Input: Population (Pi, Pj), meta-Nash equilibrium (0,, f2), strategy to be updated of the agent nद.
Parameter.learning rate 4,, improvement bound Cm-
1: for repeats k in {1, 2, ..)....)))...)..... do
2: (m .T. UNIFORM]ull
(0,,05) (P,,, Py m
4: end for
5: 0, argmnxx v=()
6: Randomly generate 4, 00, min (4. )]
7: AT argmax AREA VV[(1 - (,) 0; + 4 AT).
8: qं 41 8; 1, 1.-.-... Am.
9: if "i xidx8;
- 2 Cm then
x xxx
10:
m π..
11: else
12:
T/ = ... Then randomly generate -,*1, P. = P; (*.+))
end if
return P:.
Output: P.
Algorithm 4 Calculation of the advantage function in multi-player games
Input: Strategy of the player Tú, initializaion :/:L M,, U M.
1: The identifying numbers set of other agents is (-i) = (1, {1.... k-}
2: The joint pure strategy space of other agents is A-; A1 x ... x A
3: for (aT). a E A-; do
4: Uf R- = (aT" ....
a. ))= > U then
5:
U (T x-1), U0 U_ π -;
6: else if U (_ _11 (aTT a Uo then
7:
if (T, -=; (af .., ag U then
8:
UP=U0(mp i))
9: end if
10: end if
11:
end for
12:
Vi(T.)) UP
Output: V,(TT)
21

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Settings
Value
Description
nb_iters
200
Training iterations
meta solver
fictitious play
Metasolver method
meta_iter
1000
Iterations for Metasolver
muproveeeet..hresiiee threshhld Cm
0.03
Convergence criteria
learning_ran
0.5
Default learning rate
num lemmeereers
4
Number of strategies updated in each iteration
num repeats
10
Number of repetitions per experiment
4
0.5
Default step size
Xd
0.5
Diversity weight
Table I. Parameter setting for experiments Zero-sum games.
C. Experiment Details and Additional Experiment Results
C.1. A-PSRO for Solving Zero-Sum Games
The parameter setting of zero-sum games is given in Table 1. All experiments in this paper were run with CPU support on model Intel Core 19- 10900KF CPU @ 3.70GHz. Experiments can be performed under both Windows and Linux systems.
In our setup, each experiment repeated times and the results are averaged for plotting. Within each experiment, the population is initialized randomly, and the meta-game is solved in the same manner for different algorithms. The number of learners for all algorithms, except the classic PSRO, is set to 4, which implies that four strategies within the population will be updated in each iteration. In order more accurately compare the effiency of different algorithms in learning the strategies, we gradually increase the iterations for meta-solver. The initial iterations for meta-solver is set as 1000. Every 20 steps of training, we increase the iterations for meta-solver by 500.
Our experiments for symmetric zero-sum games are conducted in the environments used the previous papers about PSRO algorithms. Detailed description of these game environments can be found in (Czarnecki al., 2020; Liu al., 2022). Taking the AlphaStar an example, it is derived from the experimental environment StarCraft, which is commonly used in multiagent reinforcement learning. By extracting meta-strategies in large scale extend-form game StarCraft, can obtain symmetric normal-form game AlphaStar. In detail, AlphaStar is symmetric zero-sum games with dimension 888 888. Other normal-form form game environments are similarly obtained by extracting meta-strategic for real world games (Go, Kuhn Poker, etc.).
Additional experiment results are shown in Figure 8. According to the previous work (Czarnecki et al., 2020), the following games
has strong transitive structures. From Figure 8, we can see that in these games, adopting only the LA (lookahead) module with the objective of maximizing the advantage function is effective reduce the exploitability. In those games with cyclic structures, is necessary adopt the diversity module in learning Nash equilibrium. We can see that A-PSRO combining LA and Diversity Module achieves the optimal results across all environments. In the stochastic game Disc game 8(d) with almost no transitive dimension, all algorithms obtain the same convergence results.
Figure 9 shows the advantage distribution of these games. From Figure 9, we can see that although there may be large differences in the payoff matrices between different games, they may have similar advantage distribution. Games with the same advantage distribution have similar convergence processes of strategies when applying the PSRO algorithms to solve them, e.g. 9(c), 9g), 9n). Although the advantage function does not fully characterize the transitive dimension in zero-sum games, we believe that it has similarities to the geometric visualization of the transitive and cyclic dimensions in the previous work (Czarnecki et al., 2020).
C.2. A-PSRO for Solving Two-Player General-Sum Games
The parameter setting of general-sum games is given in Table 2. The hardware and system setup used for the experiments are the same as those for zero-sum games. Similar to zero-sum games, the initial iterations for meta-solver is set as 1000. Every 20 steps of training, we increase the iterations for meta-solver by 500.
The StagHunt game is a commomly used general-sum game environment to test the ability of algorithms to learn the optimal Nash equilibrium (Tang et al., 2021). The payoff matrix of the traditional StagHunt game is given in Table 3. In the Stag
22

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Settings
Value
Description
nb_iters
100
Training iterations
meta solver
fictitious play
Metasolver method
meta_iter
1000
Iterations for Metasolver
num.oracle_reper repeats
10
Repetitions of the inner loop for strategy exploration
distribution
normal
Gaussian distribution
distribution mean
0
Mean value of the distribution
distribution var
20
Variance of the distribution
0.03
Convergence criteria
learning
Bare rrae
0.5
Default learning rate
leanners
Number of strategies updated each iteration
num repeats
100
Number of repetitions per experiment
Table 2. Parameter setting for experiments in General-sum games.
Hunt game, both (U.L) and (D.R) are Nash equilibriums. In order achieve higher reward joint strategy, cooperation required in the learning process of agents.
L
30,30
-10,-10
-10,-10
20,20
Table 3. Traditional StagHunt game.
Q1
Q2
ag
d1
U1
-U(
-U
-U
-u
02
-
11
:
-1
-U
-11
-06
U
-U
-U
:
-U
-u
Qp
-U
11
-U
Table Advanced StagHunt game.
In this paper, extend the traditional StagHunt game structure to large scale general-sun sum game. The payoff matrix of Advanced--Saghunnt is given in Table C.2. In Advanced-Staghume each agent has a pure strategy space {ar ... ), where {a,, a, corresponds to the Nash equilibrium strategies resulting from cooperation. In Table C.2, U, denotes the reward corresponding to the cooperative strategy in StagHunt, which is drawn from unifrom ditribution U[1, 2]. order to judge whether A-PSRO deterministically converges to the optimal Nash equilibrium, we set one of those
For the rest of the payoff matrix for the Advanced-StagHuume we the uniform distribution U 0.8) to fill the rewards corresponding each joint strategy. This suggests that there are many inefficient Nash equilibria in the Advanced-StagHlue game besides the cooperative equilibrium in the shape of (a,, a.).
In our experiments, we set n = 100 and there are cooperation equilibrium with reward U; U[1, Each PSRO algorithm was run times repeatedly to solve game and results were averaged for presentation.
From the experiment result 4(a), we can see that most PSRO algorithms in the Advanced-StagHHu stagnate in the inefficient Nash equilibria. This is because the space of strategies whose strategy gradient points to cooperative Nash equilibrium is small proportion of the full space. In order for the agent to learn the optimal Nash equilibrium strategy, it is necessary to design reward-related objective for the agent. We can see that A-PSRO based on the advantage function effectively learns the optimal Nash equilibrium strategy, which indicates that the strategy exploration objective with advantage can improve rewards when solving general-sum games.
The optimal Nash equilibrium in the Advanced-StagHHine game is pure strategy equilibrium. In order to test the effectiveness
23

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
of A-PSRO in games where the optimal equilibrium is mixed strategy equilibrium, design large-scale general-sum game Advanced-RSI with the structure similar the traditional game Rock-Paper-Scisee of the RSP in general-sum game URSP. The payoff matrix of URSP is given in Table 5. In URSP, e is random number satisfying the uniform distribution U(0, 100). This general-sum game has the similar mixed Nash equilibrium to the traditional RSP.
We first design the structure
Based on the URSP, we design large scale general-sum game Advanced-RSP. The payoff matrix Advanced-RR ---nneddd-PPP- given Table C.2. For the rest of the payoff matrix for the Advanced-Ree we use the uniform distribution U 100) fill the rewards corresponding to each joint strategy. We can easily find that each subgame corresponding the joint strategy RR, S. P.) is mixed Nash equilibrium. There also other equilibra with inefficient rewards.
In our experiment, we set 1000 and = 10. Each PSRO algorithm was run 10 times repeatedly to solve the game and the results were averaged for presentation. The experiment result is shown in Figure 4(b). From the figure, we can see that A-PSRO learns the optimal mixed equilibrium strategy, while all other PSRO algorithms stagnate in the inefficient Nash equilibrium.
R
R
100
180+c
S
100
180+E
P
180+e
100
Table S. General-sum RSP structure URSP.
R1
S
P1
aj
R
S
P
a₂
Q1
U
-U
-U
-U1
-u
-
-U
-1
-M6
-11
-16
-0
R1
-1
-11
-1
-16
-26
-14
-11
-2
81
-1
URSP
-1
11
-0
-0
-U1
-U
-U
P1
-8
-18
-1
-1
-0
-0
-U
-U
-U
-U
-0
-U
-0
-0
-U
-U
-2
-U1
-1
-26
-U
-2
-11
-1
-2
-2
R;
-W
-1
-11
-M
-11
-11
-1
-11
S
-U
-U
-U
-U
-U
-U
-1
-Ul
URSP
-U
-U
P
-U1
-U1
-UU
-U
-11
-11
-1
-tl
-U
-21
-U
-U
-U
-U
-26
-U
Gg
18
...
-W
-0
-1
-0
-M
-W
...
Table Advanced RSP game.
We also perform experiments in randomly generated games that feature the same reward distribution. The dimension of random generated games are 1000 x 1000. these games, each element distribution with mean μ 0 and variance o² 20. To the convergence results of different algorithms in random generated games, let the PSRO algorithms operate in 100 independently generated game environments and the results were averaged for presentation. The experiment result is shown in Figure 4(c). From Figure 4(c), we can see that A-PSRO achieves the optimal reward of the joint strategy.
payment matrix generated by a normal
Since A-PSRO requires multiple equilibrium oracles in general-sum games to explore strategies with higher rewards, its runtime increases significantly compared to existing algorithms. In future work, we will explore ways to simplify this process.
24

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Settings
Value
Description
players
3
Number of agents in the game
nb iters
50
Training iterations
meta.solver
fictitious play
Metasolver method
meta_iter
10000
Iterations for Metasolver Gaussian distribution
distribution _ttpe
normal
distribution mean
0
Mean value of the distribution
distribution var
20
Variance of the distribution
improvement.three
0.03
Convergence criteria
learning.ras rate num learners num repeats
0.5
Default learning rate
4
Number of strategies updated each iteration
4
Number of repetitions per experiment
Ad
0.5
Diversity weight
Table 7. Parameter setting for experiments in multi- player games.
C.3. A-PSRO for Solving Multi-Player Games
The parameter setting of multi-player games is given in Table 7. The hardware and system setup used for the experiments the same those for zero-sum games. our multi-player game experiments, we adopt randomly generated games that feature the same reward distribution.
In multi-player zero-sum games, we use randomly generated symmetric games with dimension 20 x 20 x 20. This is because we have found in our experiments that reducing exploitability in larger-scale games requires very large computational complexity. We believe that a comparison with other algorithms in the setting of this size sufficient to demonstrate effectiveness. During the generation of these games, we added constraints to avoid generating strong pure strategies, which substantially increased the difficulty of strategy learning.
In the generation of multi-playe general-sum games, the structure similar to the Advanced-Staghune game with dimension 10 x 10 x 10, and set the reward of the optimal equilibrium strategy to 90.
D. Code and Dataset
provide part of the code necessary for the full operation of A- A-PSRO the supplementary materials. Once paper is accepted, we will upload the complete A-PSRO code along with the game data used for testing.
25

---

A- A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
Expcstabl Byat
Mag0oaa Of
(a) AlphaStar
(b) Blotto
(c) Elo game
(d) Disc game
seprstaallyy Tranciive pane
de Call by gars
Exatstall of gamee FOGGINE
(c) Transitive game
(1) Triangular game
( Random game of skill
(b) Elo game + noise=0.1
Elo game 0.5
Elo game + noise=1.0
(k) Tic tac toe
(I) Kuhn poker
Oetirabliyy d'
Coplersiing
(m) Connect four
(n) 3-move parity game
(o) Go (sizc=3)
(p) Go (size=4)
Figure& 8. The exploitability of the joint strategy learned by agents in various zero-sum games is depicted. The reduction in exploitabiliyy through population iterations can serve as an indicator of the effectiveness in approximating the Nash cquilibrium.
26

---

A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
A1
64 64
19
18
1.5
(a) AlphaStar
(b) Blotto
(c) Elo game
(d) Disc game
Aduaragge dhileg eaih Tarulirre game
Advarape Elatrnngiin aagggeargaee
-04
40
12
202
08
1.0
(c) Transitive game
(f) Triangular game
(g) Random game of skill
(h) Elo game noise=0.1
Adaartie timitg en the De came robee1
Adrentage of stzuges Jac
Abeelag wel.ggooiiihhheeee
-113
-00
425
440
02
04
08
Fpe maary anrorrs
Ieer mora penmerr
(i) Elo game noisc=0.5
(j) Elo game noise=1.0
(k) Tic
(I) Kuhn poker
Adounlag: chslegeii the the
-01
09-
-24
.04
-06
42
.08
60
Bun
Isperimegyy paanerr
68
(m) Connect four
(n) 3-move parity game
(0) Go (sizc=3)
(p) Go (size=4)
Figure The advantage distribution strategies various zero-sum games. Lighter colored regions indicate strategies with higher advantage.
27


Reviews:
[{"review_id": "VMrl2S7CYo", "reviewer": "Reviewer_DSTe", "summary": "The paper addresses the challenge of solving Nash equilibria in normal-form games, particularly for games with large strategy spaces. Traditional PSROs and their variants have been effective in learning equilibria but often lack an efficient metric to evaluate and guide strategy improvement. This limitation affects their convergence efficiency and performance in both zero-sum and general-sum games.\n\nAs a solution, the proposed method leverages the Advantage function—a new evaluative metric for guiding strategy updates toward Nash equilibria. Theoretical analysis shows that the Advantage function has desirable properties like convexity and Lipschitz continuity, ensuring more efficient equilibrium approximation. Furthermore, by integrating a LookAhead module for refining strategy updates and supports neuralization, APSRO makes it scalable to large games. Experiments in zero-sum and general-sum games demonstrate that A-PSRO significantly reduces exploitability, finds higher-reward equilibria, and outperforms existing PSRO variants in convergence efficiency and reward maximization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "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.\n\nRegarding 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.\n\nWe 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. \n\nIn 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.\n\nRegarding the computational complexity of A-PSRO, please refer to our response to Reviewer ayi4.\n\nRegarding 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.\n\nAbout the esential references not discussed, thank you for pointing this out, and we will add the missing references.\n\nRegarding 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.).\n\nGiven 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.\n\nThe current experimental results of exploitability are:\n\nPSD-PSRO: $4 \\times 10^{-1}$, A-PSRO: $3 \\times 10^{-1}$.\n\nDue 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.", "claims_and_evidence": "Overall, most claims in the paper are supported by theoretical analysis and empirical results, but a few areas could benefit from further clarification or stronger evidence, I list them as follows:\n\n> A-PSRO has a deterministic convergence rate advantage over diversity-based PSRO methods.\n\nThe paper claims that advantage-based exploration leads to more deterministic convergence, but experimental evidence is limited. The convergence rate is not explicitly analyzed against diversity-based PSRO variants. A more detailed convergence speed comparison would strengthen this claim.\n\n> The Advantage function helps overcome the limitations of diversity-based exploration in PSRO.\n\nWhile A-PSRO does reduce exploitability, the role of diversity exploration in complementing the Advantage function is not deeply analyzed. The interaction between diversity-based methods and the Advantage function needs more empirical justification, as some results (e.g., in Transitive games) suggest diversity alone may sometimes perform better.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem of solving Nash equilibria in normal-form games. However, there are a few areas where the evaluation could be expanded or clarified, e.g.\n\n> Computational Efficiency Analysis Missing\n\nThe paper does not provide a runtime or scalability comparison against existing PSRO methods. Since Advantage computation and LookAhead introduce additional complexity, an evaluation of training time would help assess practical feasibility.\n\n> Limited Real-World Validation\n\nThe experiments focus on synthetic normal-form games, which are common in game theory but may not directly translate to real-world multi-agent learning problems (e.g., poker, RTS games like StarCraft). Testing A-PSRO in a multi-agent reinforcement learning (MARL) setting would demonstrate its broader applicability.", "theoretical_claims": "No obvious errors were found", "experimental_designs_or_analyses": "For the ablation test for:\n- A-PSRO without LookAhead (LA)\n- A-PSRO without Diversity\n\nThe effect of LookAhead is clear, as removing it worsens exploitability reduction. But a potential issue is: the interaction between Advantage-based updates and Diversity is not fully explored.", "relation_to_broader_scientific_literature": "A-PSRO is strongly connected to prior work in PSRO methods, Nash equilibrium learning, and multi-agent learning. It extends these areas by introducing the Advantage function, which provides a principled optimization target for reducing exploitability and selecting better equilibria. While diversity-based PSRO methods rely on heuristic exploration, A-PSRO offers a mathematically grounded alternative, making it a meaningful contribution to equilibrium learning research.", "essential_references_not_discussed": "Relevant Missing Work:\n\n1. Neural Population Learning Beyond Symmetric Zero-Sum Games (Liu et al., 2024)\n2. Pipeline-PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games (McAleer et al., 2020)", "other_strengths_and_weaknesses": "Has been discussed in previous questions", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "", "extra_scores": {}}, {"review_id": "iVGt8Q3O3C", "reviewer": "Reviewer_vFFK", "summary": "The authors propose an extension of PSRO to normal-form games with large-scale action spaces. They incorporate an advantage function to guide strategy exploration and speed up convergence to NE and improve joint rewards in general-sum normal-form games.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "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.\n\nWe 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. \n\nThe use of normal-form games in the title is primarily for the following reasons.\n\nFirst, 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. \n\nAdditionally, 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:\n\n\"Choosing samples to compute the heuristic strategy Nash equilibrium\"\n\nThe 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.\n\nThis 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. \n\nOne 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.\n\nRegarding 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. \n\nSince 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.\n\nOn 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.\n\nConsidering 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.\n\nAs 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.\n\nAbout 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.\n\n[1] Czarnecki et al. Real World Games Look Like Spinning Tops, NeurIPS 2020.", "claims_and_evidence": "- The authors claim to establish an equivalence between advantage maximization and Nash equilibrium. Theoretically, this seems to follow.\n- The authors claim that including advantage maximization in normal-form PSRO allows their method to achieve higher joint rewards in general-sum games. \n\nThey empirically support these claims by showing that they outperform other PSRO variants in normal form games.\n\n\nA-PSRO is positioned as a solver for large-scale normal-form games, yet the paper does not compare it to standard methods for solving such games, such as linear programming, fictitious play, or regret minimization. Furthermore, PSRO and its extensions are predominantly designed for and applied to extensive-form and partially-observable Markov games, but the paper does not address how A-PSRO relates to or extends beyond these settings. This omission raises concerns about the generality and significance of the proposed approach.", "methods_and_evaluation_criteria": "The proposed evaluation criteria does not make sense for the problem discussed in the paper. A-PSRO is designed as a large-scale normal-form game solver, yet it is not compared with normal-form game algorithms other than PSRO variants.", "theoretical_claims": "I did not rigorously check the proofs\n\nTheorem 4.8 suggests that training a best-response approximator with sufficient accuracy for a game will guarantee a sublinear convergence rate in symmetric zero-sum normal-form games. It needs to be discussed that the amount of time necessary to calculate a sufficient training dataset of many best response targets could be large.", "experimental_designs_or_analyses": "The experimental design (exploitability/joint reward vs training iterations) is sound.", "relation_to_broader_scientific_literature": "The authors should be clear early on that their decision to consider PSRO as a solution to normal-form games is unusual. They should provide better context that PSRO and nearly all of its extensions are designed to solve games with sequential decision making like extensive-form and partially-observable Markov games. PSRO is typically considered as a extension of the normal Double Oracle algorithm to sequential interaction games.\n\nIt also needs to be made more clear that most of the works cited in this paper address games with sequential interaction, not normal-form games (except as sanity checks and stepping stones to other game representations).", "essential_references_not_discussed": "The authors focus on solving normal-form games, and should include foundational algorithms that are still used today to solve them [1,2,3]\n\n[1] Von Neumann's minimax theorem: v. Neumann, J. \"Zur theorie der gesellschaftsspiele.\" Mathematische annalen 100.1 (1928): 295-320.\n\n[2] Lemke-Howson Algorithm: Lemke, Carlton E., and Joseph T. Howson, Jr. \"Equilibrium points of bimatrix games.\" Journal of the Society for industrial and Applied Mathematics 12.2 (1964): 413-423.\n\n[3] Multiplicative Weights Update Algorithm: Freund, Yoav, and Robert E. Schapire. \"Adaptive game playing using multiplicative weights.\" Games and Economic Behavior 29.1-2 (1999): 79-103.", "other_strengths_and_weaknesses": "Strengths:\n- The advantage metric provides a useful signal to speed up convergence of PSRO in normal-form games.\n\nWeaknesses:\n- It is unclear how useful this method is for normal-form games without comparing to non-PSRO methods.", "other_comments_or_suggestions": "Error bounds need to be added in Figure 2 and Figure 7.", "questions_for_authors": "1) What constitutes a large-scale normal-form game in this setting? At what scale would A-PSRO be more preferable than traditional normal-form game algorithms like linear programming, fictitious play, and regret minimization? Why is a PSRO-style approach necessary in this context compared to other methods?\n\n2) Why evaluate against Pipeline-PSRO? It speeds up wall-time performance in extensive-form games by concurrently pretraining behavioral deep RL best-responses. It's applicability as a normal-form game solver is extremely limited.\n\n3) This question generally extends to comparing against most of the other PSRO baselines. If you are trying to solve large-scale normal-form games quickly, why not compare to other methods designed to solve normal form games, like linear programming approaches, fictitious play, or regret matching?\n\n4) Is your goal to extend A-PSRO to extensive-form games where PSRO is generally applied? If so, this motivation is very unclear, and the non-trivial challenges in extending the advantage metric to extensive-form games need to be discussed.", "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": "", "extra_scores": {"ethical_review_concerns": "I have no ethical concerns regarding this paper."}}, {"review_id": "2BCZKIIv0Y", "reviewer": "Reviewer_ttsB", "summary": "This paper defines “Advantage” in 0s games and 2p simplified games as the value of a policy can achieve given all other policies in the strategy profile are playing as their best response. The authors thus derive A-PSRO with Diversity and LookAhead for large-scale games. The authors thus proposed A-PSRO based on the advantage defined and shows the algorithm retains sublinear convergence rate in 0s games. Experiments show that the proposed A-PSRO with LookAhead can achieve better exploitability across domains compared with baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "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.\n\nDue 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.\n\nRegarding 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.\n\nRegarding 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. \n\nFor 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.\n\nRegarding 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.\n\nThank 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.\n\nWe appreciate your recognition of our work, and we hope the above responses address your concerns. We hope you continue to support our paper.", "claims_and_evidence": "Claim 1: introduced A-PSRO as an improved equilibrium solver for empirical games \n\nYes there are supportive evidence by experiments\n\nClaim 2: The paper studies the theoretical properties of the proposed advantage functions\n\nYes these are supported by the theoretical analysis", "methods_and_evaluation_criteria": "- The paper uses exploitability and reward for 2p0s and general-sum games in a few matrix games which makes sense to me.\n- The paper does not explicitly present how the advantage function, diversity and look ahead are used within the PSRO algorithm in the main text. I suggest you put an algorithm block either in the main text or appendix.", "theoretical_claims": "- The paper studies the convergence rate with A-PSRO and introduces some theoretical properties of the advantage function\n    - I think the results makes sense to me, but I did not fully check the correctness of all the proofs.", "experimental_designs_or_analyses": "This paper conducted experiments in several matrix games, yet it is still to be examined in more complex games with extended form. Moreover, the scalability is questionable as the calculation of the advantage function requires an approximation of the BR and the computation complexity is not specifically discussed.", "relation_to_broader_scientific_literature": "- I think the paper has already discussed enough related works regarding the PSRO line of work in the paper.\n- I wonder how the advantage is related to the counterfactual regret minimization (e.g. [1-2]) lines of work.\n\n[1] Zinkevich, M., Johanson, M., Bowling, M., & Piccione, C. (2007). Regret minimization in games with incomplete information. *Advances in neural information processing systems*, *20*.\n\n[2] Brown, N., Lerer, A., Gross, S., & Sandholm, T. (2019, May). Deep counterfactual regret minimization. In *International conference on machine learning* (pp. 793-802). PMLR.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- Strength\n    - Clear demonstrations of the game solution dynamics and visualization of the advantage functions in the experimental results\n- Weakness\n    - The authors focus too much on the theory instead of the a clear presentation of the method. I was very distracted by the theorems when I tried to understand the methodology. I suggest that you present in the following way:\n        - Here is PSRO\n        - Here is how we utilize advantage function\n        - Here is the Look ahead module\n        - Here is the diversity module\n        - then go over the theorems under different game properties\n    - state clearly about the limitation of your method (e.g. only applies to xxx games)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Q1: Can you compare the computational cost between the A-PSRO and PSRO for a single iteration?\n\nQ2: The exploitability of PSD-PSRO, although in different games, is pretty low (at a scale of 10^-1) in the paper [3], while it is at a scale of 10^0 in this paper (Figure 6a). Can you elaborate on the potential reasons for the phenomenon and do the experiment domains of that paper can apply to your work?\n\n[3]Yao, J., Liu, W., Fu, H., Yang, Y., McAleer, S., Fu, Q., & Yang, W. (2023). Policy space diversity for non-transitive games. *Advances in Neural Information Processing Systems*, *36*, 67771-67793.", "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": "", "extra_scores": {}}, {"review_id": "jafhRqeS9h", "reviewer": "Reviewer_ayi4", "summary": "This paper proposes Advantage Policy Space Response Oracle (A-PSRO), a new framework for learning Nash equilibria in normal-form games with large strategy spaces, applicable to both zero-sum and general-sum settings. The key contribution is the Advantage function, a new evaluative metric that guides strategy updates toward equilibrium, ensuring efficient and deterministic convergence in zero-sum games while optimizing for higher-reward equilibria in general-sum games. To enhance learning efficiency, A-PSRO introduces LookAhead updates for faster equilibrium approximation and meta-equilibrium search to identify high-reward strategies. Finally, empirical results demonstrate that A-PSRO reduces exploitability more effectively in zero-sum settings and achieves superior rewards in general-sum games, offering a scalable and unified solution for strategic learning.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "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.\n\nRegarding the computational complexity of the LookAhead module, we will explain it from both theoretical and experimental perspectives. \n\nFor 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.\n\nFrom 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.\n\nFrom 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.\n\nNext, 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.\n\nTaking the classic EC diversity metric in Equation (38) as an example:\n\n$\\operatorname{EC}(\\mathcal{P}_i \\mid \\mathcal{P}_j) := \\operatorname{Tr} (\\mathbf{I}-(\\mathcal{L}+\\mathbf{I})^{-1})$\n\n$\\mathcal{L} = \\mathcal{M}_i \\mathcal{M}^T_i, \\ \\mathcal{M}_i =  \\mathcal{P}_i \\times U_i \\times \\mathcal{P}_j$\n\nIts 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)$.\n\nFor 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\n\n$min([Q \\cdot (1-d)+I \\cdot d] \\times U \\times I).argmax()$\n\nThis 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.\n\nThe 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.\n\nRegarding 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.\n\nFor 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$. \n\nThis 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.\n\nA typo appears in Theorem 4.1. Thanks for pointing it out.", "claims_and_evidence": "All claims are well-supported by both theoretical analysis and experiments, particularly for zero-sum games.", "methods_and_evaluation_criteria": "Yes, the proposed method generally make sense for the problem of learning Nash equilibria in norm-form games.", "theoretical_claims": "Yes, the authors provide proofs of their theoretical results in the Appendix. I checked the first several proofs, and they all appear to be correct.", "experimental_designs_or_analyses": "Yes, I reviewed the experimental design and analysis. The evaluation includes zero-sum and general-sum normal-form games, using exploitability as the primary metric for assessing convergence to Nash equilibrium. The experiments compare A-PSRO against state-of-the-art PSRO variants (e.g., P-PSRO, DPP-PSRO, UDF-PSRO, PSD-PSRO) across various game environments, including AlphaStar, Go, Staghunt, and Randomly Generated Games. The experimental setup is generally sound, as it uses well-established benchmarks and relevant baselines.", "relation_to_broader_scientific_literature": "Although this paper proposes A-PSRO as an extension of Policy Space Response Oracles (PSRO), the introduction of the Advantage function as a new metric for evaluating strategy improvement appears to be a novel contribution.", "essential_references_not_discussed": "No, I did not find any essential related works that are missing from the paper.", "other_strengths_and_weaknesses": "Strengths: \n\n1. The introduction of the Advantage function as a new strategy evaluation metric is a novel idea that extends beyond traditional best-response and diversity-based approaches in PSRO.\n\n2. The LookAhead update mechanism offers a deterministic strategy improvement method, which differentiates it from existing stochastic diversity-based strategy exploration methods\n\n3. The paper is well-structured, with clear theoretical explanations and empirical validation.\n\nWeakness:\n\n1. The paper does not explicitly discuss the computational overhead of Advantage function evaluations compared to standard PSRO methods. A runtime comparison or complexity analysis would strengthen claims about scalability.", "other_comments_or_suggestions": "In Page 4, Theorem 3.4 states that $-V_i(\\pi_i)$ is a convex function. However, above Theorem 4.1, the paper states that “Since $V_i(\\pi_i) $ is convex……”, which may be a typo.", "questions_for_authors": "1. How does the additional computation required for Advantage function evaluation and LookAhead updates compare to standard PSRO methods? Could you provide a complexity analysis or runtime comparison?\n\n2. I know this paper focuses on normal-form games. Since many real-world applications (e.g., poker, security games) involve extensive-form or imperfect-information settings, I just wonder whether A-PSRO can be extended to handle sequential decision-making scenarios? If so, what modifications would be needed?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In contrast to the standard best-response strategy expansion of PSRO, the authors suggest proposing new strategies that optimize the “advantage”. The reviewers generally appreciated this novel approach and the accompanying guarantees. A-PSRO is shown to achieve lower levels of exploitability and higher joint reward in several NFGs. In response to the reviewers, the authors added results for the EFG Leduc poker. This remains a concern as PSRO is primarily recognized as a technique to extend NE-approximation to games so large that traditional techniques cannot cope.
Decision: Accept (poster)