Team-PSRO for Learning Approximate TMECor in Large Team Games via Cooperative Reinforcement Learning
Authors: Stephen Marcus McAleer
Gabriele Farina
Gaoyue Zhou
Mingzhi Wang
Yaodong Yang
Tuomas Sandholm
Venue: NeurIPS 2023 poster (2023)
Keywords: PSRO
team games
TMECor
populations
equilibrium
game theory
RL
TL;DR: We provide a scalable deep RL algorithm for finding TMECor, the leading game-theoretic solution concept for adversarial team games.

Abstract: Recent algorithms have achieved superhuman performance at a number of two-player zero-sum games such as poker and go. However, many real-world situations are multi-player games. Zero-sum two-team games, such as bridge and football, involve two teams where each member of the team shares the same reward with every other member of that team, and each team has the negative of the reward of the other team. A popular solution concept in this setting, called TMECor, assumes that teams can jointly correlate their strategies before play, but are not able to communicate during play. This setting is harder than two-player zero-sum games because each player on a team has different information and must use their public actions to signal to other members of the team. Prior works either have game-theoretic guarantees but only work in very small games, or are able to scale to large games but do not have game-theoretic guarantees. In this paper we introduce two algorithms: Team-PSRO, an extension of PSRO from two-player games to team games, and Team-PSRO Mix-and-Match which improves upon Team PSRO by better using population policies. In Team-PSRO, in every iteration both teams learn a joint best response to the opponent's meta-strategy via reinforcement learning. As the reinforcement learning joint best response approaches the optimal best response, Team-PSRO is guaranteed to converge to a TMECor. In experiments on Kuhn poker and Liar's Dice, we show that a tabular version of Team-PSRO converges to TMECor, and a version of Team PSRO using deep cooperative reinforcement learning beats self-play reinforcement learning in the large game of Google Research Football.

Team-PSRO for Learning Approximate TMECor in Large Team Games via Cooperative Reinforcement Learning
Stephen McAleer Carnegie Mellon University
Gabriele Farina MIT
Gaoyue Zhou Carnegie Mellon University
Mingzhi Wang Peking University
Yaodong Yang Peking University
Tuomas Sandholm Carnegie Mellon University
Abstract
Recent algorithms have achieved superhuman performance at number of two- player zero-sum games such as poker and go. However, many real-world situations are multi-player games. Zero-sum two-team games, such as bridge and football, involve two teams where each member of the team shares the same reward with every other member of that team, and each team has the negative of the reward the other team. A popular solution concept in this setting, called TMECor, assumes that teams can jointly correlate their strategies before play, but not able to communicate during play. This setting is harder than two-player zero- games because each player use their public actions to signal to other members of the team. Prior works either have game-theoretic guarantees but only work in very small games, are able to scale to large games but do not have game-theoretic guarantees. In this paper we introduce player games to team games, and Team-PSRO Mix-and-Mate which improves upon Team PSRO by better using population policies. In Team-PSRO, every iteration both teams learn joint best response to the opponent's 's meta-strategy via reinforcement learning. As the reinforcement learning joint best response approaches the optimal best response, Team-PSRe is guaranteed to converge to TMECor. In experiments on Kuhn poker and Liar's Dice, we show that tabular version of Peam-PSRO converges to TMECor, and version of Team PSRO using deep cooperative reinforcement learning beats self-play reinforcement learning the large game of Google Research Football.
team has different information and must
algorithms: Team-PSRO, an extension of PSRO from two-
1 Introduction
Two-player zero-sum games have served as testbeds artificial intelligence research. Algorithms that have achieved superhuman performance in games such go (Silver et al.) (017) and poker (Bowling cet al. 20155 Brown & Sandholm (017) are widely seen as milestones. These algorithms use game- theoretic techniques find an approximate Nash equilibrium, in other words strategy that cannot be exploited by humans. Despite these successes in two-player games, real-world scenarios often involve more than two players.
this paper we study class games with multiple players where each player shares reward with the other players in one of two teams, which we call two-team games. A canonical example of
Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

two-team game is bridge, a game in which current algorithms fail to compete with expert humans. There are multiple solution concepts for team games, but the one we consider is known as TMECor. In this setting, we allow each team to jointly sample value from a distribution to correlate their strategies before play. This setting has many nice properties and is the natural solution concept for many team games. Two joint team strategies are in TMECor if the value that a joint best response for an opponent team gets against each team is the same as the value when both teams are playing their current strategy.
There are two strands of research surrounding two-team games. The first has developed tabular methods that have game-theoretic guarantees. These algorithms work well on very small games but do not scale to large team games. The second has developed deep reinforcement learning algorithms that can scale to large two-team games, but end up being exploitable because they are not based on game-theoretic algorithms.
In this paper, we introduce the first scalable game-theoretic techniques for two-team games. We show that a straightforward extension of PSRO team games, called Team PSRO, and is guaranteed to converge to an approximate TMECorr. We also introduce a novel algorithm called Team PSRO Mix- and-Match (Team PSRO-MM) that mixes and matches best responses to create larger population and show that it outperforms Team PSRO. In our experiments, we show that Team PSRO-MM outperforms Team PSRO and that both methods outperform self-play on the large benchmark game of Google Research Football.
Team PSRO is based on policy space response oracles (PSRO) (Lanctot al. 2017). PSRO is already one of the most promising methods for finding approximate Nash equilibrium in large two-player zero-sum games because is simple
with existing RL methods, naturally provides measure of approximate exploitability, and doesn't 't require full game-tree traversals. Methods based on PSRO such AlphaStar (Vinyals al. (019b) and Pipeline PSRO (McAleer et al.) 2020) have achieved state-of-the-ar performance on Starcraft and Barrage Stratego, respectively. Our method, called Team PSRO is the first PSRO-based algorithm for team games and show that it converges to TMECor when the RL best response is strong enough.
Despite being the first scalable method for computing TMECor, Team PSRO does not efficiently use the population of best responses because each policy must be deployed with the corresponding policy in its joint best response. Building on Team PSRO we fix this issue by allowing policies to be mixed and matched with other policies in the population that are not the corresponding policy in its joint best response. We show that the resulting algorithm, called Team PSRO Mix-and-Match (Team PSRO-MM) is able to empirically improve upon Team PSRO. We hypothesize that this is because computing best responses is more costly that evaluating the expected value of policies when the number of policies is low enough.
Our contributions include the following:
1. We show that a straightforward extension of PSRO to team games converges to TMFCor.
2. We introduce a novel method based on Team PSRO, called Team PSRO Mix-and-Matchh that emperically converges faster by better using the best responses in the population.
2 Background
Extensive-form games (EFGs) model games that are played on a game tree, and can capture both sequential and simultaneous moves, as well as private information. In this section, for simplicity we focus on four-player zero-sum games where two players-T1 and T2-play as a team against two opponent players, denoted by O1 and O2. However, these methods generalize to games with more than two players, as shown in our experiments on Google Research Football.
Each node in the game tree belongs to exactly one player i E {T1, T2, 01, 02) U {c} whose turn to move. Player C a special player, called the chance player. It models exogenous stochasticity in the environment, such as drawing card from a deck or tossing a coin. The edges leaving v represent the actions available at that node. Any node without outgoing edges is called a leaf and represents an end state of the game. We denote the set of such nodes by Z. Each E Z is associated with tuple of payoffs specifying the payoff u, (z) of each player E [T1, T2, O1, 02) at z. The product of the probabilities of all actions of C the path from the root of the game to leaf is denoted by Pc(2).

---

Private information is represented via information set (infoset). In particular, the set of nodes belonging to i E [T1, T2, O1, 02) is partitioned into collection I of non-empty sets: each I E I, groups together nodes that Player cannot distinguish among, given what they have observed. Necessarily, for any 7 E I and u w E 7, nodes e and w must have the same set of available actions. Consequently, we denote the set of actions available at all nodes of / by A₁. As it is customary in the related literature, we assume perfect recall, that is, no player forgets what he/she knew earlier in the game. Finally, given players and j. two infosets 1, E I₁ 1j E I₃ are connected, denoted by 4 = 1,, if there exist o E I; and w E 1 such that the path from the root to e passes through w or vice versa.
The set of sequences of Player i, denoted by Σ, is defined as Σ, ((I,a): I I, Ar} U {ø}. where the special element Ø is called the empty sequence of Player i. The parent sequence of a node of Player i, denoted (v)) the last sequence (information set-action pair) for Player i encountered on the path from the root of the game to that node. Since the game has perfect recall, for each E I, nodes belonging to 7 share the same parent sequence. So, given 1 E Ig we denote by o E Σ, the unique parent sequence of nodes in /. Additionally, we let (1) = Ø if Player never acts before infoset
Sequences.
Reduced- normml--ooomm plans. A reduced-nnommal-fon plan ह; for Player i defines a choice of action for every information set Ij that is still reachable as a result of the other choices in и itself. The set of reduced-normal -fomm plans of Player is denoted II, We denote by (I) the subset of reduced-normall-ee normal-form plans that prescribe all actions for Player on the path from the root to information set 7 E I, Similarly, given a (T,a) E E, let (r) S (7) be the set of reduced- normal-form plans belonging to (T) where Player plays action a at 1, and let (2) == II;- Finally, given leaf E Z, we denote with (z) C ПТ; the set of daduced-normal-fomm plans where Player i plays so as to reach 2.
Sequence-form strategies. A sequence-fore form stralegy is a compact strategy representation for perfect- recall players in EFGs (Romanovskil 1962 Koller al. 1996). Given a player i E {T1, T2, O1, O2) and normal-form strategy E A(I))) the sequence- form strategy induced by is the real vector y. indexed over a E Σ,, defined as y
(e) p(z).. The set of sequence-fore strategies that can be induced as varies over (TI,,) is denoted by )/ and is known to be a convex polytope (called the sequence- form polytope) defined by a number of constraints equal to [Za] (Koller et al. 1996).
TMECor as a Bilinear Saddle-Point Problem. A TMECor strategy is a probability distribution JuT over the set of randomized strategy profiles D/r X J'22 that guarantees maximum expected utility for the team against the best-responding opponent team {O1, 02). Since each player has perfect recall, any randomized strategy for player is equivalent to distribution over reduced-normal--ie pure strategics (Kuhn [953). Hence, any distribution over profiles of randomized strategies of the team members can be expressed in equivalent way as a distribution over deterministic strategy profiles 11T: x LT2. Denote by P(LIT) all possible combinations of pure strategies of a population IT: { TTT2) [TTI, 4T2 E I. The benefit of this transformation is that IITI x II is finite set, unlike WTI x DT22. For this reason, TMECor is usually defined in the literature as a distribution over I1 x Il without loss of generality. We will follow the same approach in our characterization.
For each leaf z, let (z) = (uT (z) + (re())))e(z).. The expected utility of the team can be written as the following function of the distributions of play μut E A(ITTI x ITT2), no E A(To1 x To2)):
(T((T:HO)= (úr(=)
Σ (TTTTT TT2)
Σ no (TOOI mO2)
=62
an (=) (Tp)ll)p()))
Nor (x)
For given opponent coordinated strategy no E A(IIo1 x Io22). a best response BRT is defined as a coordinated strategy that gives the highest expected utility against the opponent coordinated strategy:
BR, (vo) = arg max PT (TEA(TT, xTTp)
UT(HT,
By definition, a team-maxmin equilibrium with coordination device (TMECor) (Celli & Gatti 2018 Farina et al. 2018b) is a Nash equilibrium of the game where the team plays according to the
(XX) denotes the probability simplex over the finite set X.
3

---

coordinated strategy AT E A(IIT x IT2)) and the opponent team plays according to the coordinated strategy Ho E Allo1 x Hoz). In the zero-sum setting, this amounts to finding solution of the optimization problem
max (TE xII))) ( x
min
"T(TT MO).
(2)
Note that if pair of joint strategies (JT,HO) are in TMECor, then
ut uT ur (BBR Ho) = ur (BT,
(3)
2.1 Approximate TMECor
Define an e-best response (c-BR) BRI as any coordinated strategy that achieves expected utility against the opponent coordinated strategy within of optimal: ur (BBRT(H)) Mo) S ur (BR, (po), po). The exploitabilityy e(uT, Ho) of a pair of correlated strategies (JIT, (o) is defined as E(UTT, = ut (BBT((O), no) + uOTT, (IT)) A pair of joint strategies (KT,HO) is in an c-approximate TMECor if NO) <
3 Related Work
3.1 Double Oracle (DO) and Policy Space Response Oracles (PSRO)
Double Oracle (McMahan et al. 2003) is an algorithm for finding a NE in two-player zero-sum normal-form games. The algorithm works by maintaining population of strategies for each player. Each iteration a NE is computed for the game restricted to strategies in each player's 's population. Then, best response to this NE for each player is computed and added to the population. Although in the worst case DO must expand all pure strategies, in many games DO empirically terminates early and outperforms existing methods. Policy-Space Response Oracles (PSRO) Lanctot al. (2017) scales DO to large games by using reinforcement learning to approximate a best response. The restricted-game game NE is computed on the empirical game matrix generated by having each policy in the population play each opponent policy and tracking average utility in a payoff matrix (Wellman 2006).
There are a number of methods related to PSRO. NXDO (McAleer et al., 2021; Tang et al. 2023) iteratively adds reinforcement learning policies to a population but solve extensive-form restricted game and has shown to be more efficient than PSRO in certain games. AlphaStar (Vinyals et al. 2019b) trains population of policies through procedure that is somewhat similar PSRO. AlphaStar also uses some elements of self-play when constructing its population, and outputs a meta-Nash equilibrium of the population at test time. P2SRO (McAleer et al.) (020) parallelizes PSRO with convergence guarantees. Other work has generalized PSRO to more players (Muller et al. 2020 Marris al. 2021), incorporated diversity objectives cover more of the strategy space (Liu et al. 2021bb Perez-Nieves et al., 202T]] McAleer et al. 2022a Slumbers et al., 2023 Yao et al.,
2023), and meta-learned the mita-disttibutton (Feng al. 2021). PSRO has also been applied to core problems in game theory (Zhang et al. (202)) and reinforcement learning (Liang et al.
2023 ).
3.2 Team Games
In this paper we study the TMECor Celli & Gatti (2018); Farina et al. (0118a: Zhang & Sandholm (2021): Zhang et al. (022)) setting where players on the same team are allowed to coordinate before
playing. A related solution concept is equilibrium where team members are not able to coordinate,
which is known as a
equilibrium (TME) strategy (von Stengel Koller 1997] Basilico
al. 2017 Zhang & An 2020a b Kalogiannis al. 2021 Anagnostides et al. 2023)) A solution of this type yields the maximum expected utility for the team players against a best-responding opponent. The TMECor solution concept has several advantages over TME. First, the team is guaranteed at
least as much expected utility under TMECor than under TME (Celli & Gattil 2018). Second, the TMECor objective is convex while the TME objective is not convex.
3.3 Cooperative Reinforcement Learning
In this section we focus on the regime of centralized training and decentralized execution (CTDE) in cooperative reinforcement learning. In the CTDE regime, we assume to have access to all agent's

---

observations during training time, which is reasonable assumption for our setting of computational game solving. CTDE methods such as MADDPG Lowe et al. (2017) and COMA Foerster al.) (2018) make use of this centralized training learning centralized critic that can condition on private information. Although this critic taken away at test time and only the actor is used decentralized execution, by conditioning on all relevant information, the centralized critic can reduce much more variance than an individual agent's 's critic.
2022 trains one PPO agent for the whole team with centralized critic, among other tricks. Although off- off-policy CTDE methods such as MADDPG and QMix (Rshhd et al. 2018 Schäter et al., 2023 Mguni et al., 2023) tend to outperform
Multi-Agent PPO (MAPPO) (Yu et al. 2021 Kuba et al.
on-policy methods such as COMA (Papoudakis et al.) 2020 Wang al. 20211. in practice MAPPO
can be surprisingly effective and stable baseline, and we use it as our joint best response in Team
PSRO.
3.4 Deep RL for Team Games
number of previous works have studied deep reinforcement learning methods in team games. Jaderberg et al. (2019) and et al. (2021a 2019) train deep RI. agents via self play and population based training to achieve high performance on capture the flag video game and simulated soccer environment, respectively. Berner et al. (2019a) use self-play reinforcement learning to achieve expert level performance on Dota. None these methods are grounded in game theoretic techniques, however, and may not be expected converge to TMECor. Concurrent to our work, Xu al. (2023) propose an algorithm that similar to Team PSRO, but they do not make a connection to TMECor and do not propose the idea of mixing and matching.
Team PSRO
As described in the previous section, existing methods for learning approximate TMECorrs are tabular, and result will not scale to large games. In this paper propose Team-PSRO, Team-PSRO makes the simple observation that approximate joint best responses can be learned via cooperative reinforcement learning. The resulting algorithm is very similar to PSRO in that every iteration, best response is computed against the opponent's 's restricted distribution and the resulting policy is added population. However, instead of computing single-agent best responses for single player, the best responses for Team-PSRL are joint best responses for a single team. These joint best responses a set of policies for each member of the team and are learned through cooperative reinforcement learning.
4.1 Tabular Team Double Oracle
In this section we introduce team double oracle, a double oracle method for computing TMECor in zero-sum games with two teams. Team DO is conceptually the same as existing single oracle algorithms (Celli & Gatti 2018) for team games but extends these algorithms to two team games. Team DO very similar to the original double oracle algorithm for two-player zero-sum normal form games. Team DO maintains& population of pure joint strategies for each team II,, Io. Each pure strategy team's population is pure joint strategy for each player on that team μrT = (TT1. TT2). Similar to DO, we construct restricted game in the space of pure strategies of the populations for each team. Our restricted game G(IT, Io) is a two-player zero-sum normal-form game that takes as actions the pure strategies fuT E IT for the team and μo0 E TT for the opponent team. Every iteration, the NE (uF, (46) of the restricted game G(II,, 111)) is computed. Next, a best response to this NE in the original game BRO((G) is computed and added to the population. Team DO terminates when the best response for both players does not improve over the Nash value of the restricted game. Like DO, since there are finite number of pure strategies, team DO must terminate (potentially in number of iterations exponential in the size of the game). When it does terminate, the NE of the restricted game is a TMECor of the original game because no best response can improve the Nash value. Team DO is described in Algorithm]] [
Compared to other methods for finding TMECor, team DO has number of downsides. First, there are no known convergence rates for double oracle algorithms in general and team DO in particular. In fact, there exist games where Team DO must expand all joint pure strategies of the game before
5

---

Algorithm Team Double Oracle (Mix-and-Match)
Result: TMECor
Input: Initial population 11; MTg
repeat (for / = 0, 1,...} if Team DO-MM then
(uf, + NE in restricted game G(P(LI)), P(LI))
else
(RF (6) + NE in restricted game G(U,, 115) {Team DO}
II +- 11 (+)))
ITo1 1 U { (m4)
until WT (uG, (4) = ue (HO); ur (MF, (RT))
Return: (6)
terminating. Second, in extensive form games, the number of pure joint strategies is exponential in the size of the game. Lastly, computing a best response in team games is computationally intractable in general (Celli Gatti 2018).
Despite these issues, team DO a promising method for the following reasons. First, it naturally outputs measure of exploitability for free. This is useful to track progress of the algorithm, especially in large team games where computing exploitability is difficult. Second, team DO often terminates well before expanding all joint pure strategies. Indeed, as shown in experiments below, find that team DO terminates in a very low number of iterations for all of the games we tested. When team DO terminates in small number of iterations, it is often much faster than existing methods. Lastly, in the same way that double oracle provides a foundation for PSRO, team DO provides a natural way of scaling up large games by replacing the best response operator with deep reinforcement learning with Team PSRO. We describe this approach in the next section when we describe our main contribution, Team PSRO.
The main bottleneck for the tabular algorithm consists of the computation of the best response policy of each team. Taking for example the side of team T, that task corresponds to solving the optimization problem
BRT (RO
arg max In (M
WT (TT,,
(ūr(=)
Σ (T( [nT(TT,,TT)) TT2)
( Σ Ho (To (oo)
arg max ME xI1)))
ZEZ
(l)
Ellor Grop Elloa(=)
(T))
While the above optimization problem is computationally intractable in the general case (Celli & Gatti 2018), several computational approaches that can scale up to moderately sized games are
known. Celli & Gatti (2018) propose simultancous row and column generation using an integer-
programming- based pricing oracle. Additionally, Farina al. (2088)); Zhang et al. (2020): Farina et (2021) propose approaches based on integer programming, while Zhang & Sandholm (2021);
Zhang et al. (2022) propose approaches based on tree decompositions. Finally, Farina & Sandholm
(2020) propose a algorithm with worst-case polynomial-time guarantees in a subclass of games called
triangle-free. As of today, even the best among these approaches can scale only up to games with a few tens of thousands of terminal sequences, and quickly run out of time or memory beyond that
scale.
In our tabular experiments, we implemented a variant of the pricing algorithm of & Gatti (2018)
compute best responses for the teams. The algorithm we implemented construct an integer program to capture the domain of feasible μT in the best-response problem 4 We chose the algorithm by Celli & Gatti| (2018) since it only requires a linear number of integer variables in the size of the game tree (this is in contrast, for example, with other integer-proge progremmiogr.nnngg-..... based approaches that use quadratic number of integer variables to achieve tighter formulation, see e.g. Farina et al. (202T); other approaches such as Zhang & Sandholm (20T): Zhang et al. (2022) use a worst-case exponential number of variables to construct an exact linear programming relaxation of the optimization problem). Pseudocode for the implemented best-response oracle is available in the Appendix.

---

4.2 Tabular Team Double Oracle Mix-and-Match
In this section we introduce team double oracle mix-and-match (Team DO-MM), which builds on Team DO by adding additional joint policies to the population for free. Similarly to Team DO, Team DO-MM maintains population of pure joint strategies for each team IIT, lo. Each pure strategy in a team's 's population is a pure joint strategy for each player on that team μtt = (TT1, TT2). In Team DO-MM, however, we construct a restricted game in an expanded space of pure strategies that considers all possible mixtures of policies from each joint best response. Contrasted with Team DO, Team DO-MM considers pure strategies that mix and match policies from different best responses of the players within each team. Our restricted game GII( ). P(IIo)) is two-player zero-sum normal-form game that takes as actions the pure strategies μTT E P(IIT) for the team and po PIIlo) for the opponent team. Similar to Team DO, every iteration, the NE (uf. (6) of the restricted game G(P(L))) P()g)) is computed. Next, a best response to this NE in the original game IBR (u²) is computed and added to the population. Team DO-MM also terminates when the best response for both players does not improve over the Nash value of the restricted game. Because upon termination no best response can improve on the Nash value, Team DO-MM inherits the convergence guarantee of Team DO to TMECor. Team DO-MM is shown as one-line change in Algorithm
Proposition 1. Tabular Team DO and Team DO-MM with exact best responses converge to a TMECor.
Proof. Proof is contained in the Appendix.
4.3
Team PSRO
We now describe our main contribution, team PSRO and team PSRO Mix-and-Matte Match. All existing tabular algorithms cannot scale to a game the size of Google Research Football. And existing algorithms such as self play do not minimize exploitablility. even though they might do well sometimes in practice. Team PSRO scales up Team DO to large games by swapping out an exact joint best response (15) for an approximate joint best response 3r that trained through reinforcement learning. Instead of learning policy for each player individually, as in PSRO, Team PSRO trains a joint best response every iteration. This joint best response is a pair of policies that are trained using cooperative RL. In particular, we use MAPPO to train the joint best response. As in PSRO, once the joint best response for a team is trained, it is added to to that team's 's population IIद and a two-player zero-sum normal form restricted game G(I IT,) is created. The actions of this normal form game correspond to pure joint strategies in the population and the payoff's correspond to the estimated expected value when one team chooses one joint policy and the other team chooses another joint policy ut (T(S(HHO) (4)) Payoff values in the restricted game estimated by sampling rollouts from both teams' joint policies. Team PSRO is described in Algorithm 2
Note that when the joint best responses achieve expected value within e of the optimal best response, then upon convergence Team PSRO will output an approximate TMECor. Even when the cooperative reinforcement learning is not within c of the optimal best response, we find that in practice the reward that joint best responses achieve against the restricted NE tends to go down over time. We call this evaluation metric of the sum of the reward that both joint best responses achieve against the restricted NE approximate exploitability because the this is lower bound on the exact exploitability. The better the cooperative RI. algorithm is in team PSRO, the more accurately the approximate exploitability will match true exploitability. As mentioned previously, a key benefit of Team PSRO is that outputs approximate exploitability a byproduct of the algorithm. If the RL algorithm is very strong and Team PSRO converges, then one can be reasonably sure that the strategy produced is strong.
The MAPPO algorithm we use contains centralized critic value function that has access to the history of the game. Since we train the joint best response centrally but execute decentrally, MAPPO allows the critic to see the partner's 's cards at training time to reduce variance in the update. Another MAPPO trick we use is to share the parameters of the neural network between partners a joint best response. This has been found to help stabilize training. Although we use MAPPO as our joint RL best response, in principle any cooperative RI. algorithm could be used to learn an approximate joint best response.
7

---

Algorithm 2 Team PSRO (Mix-and-Match))
Result: Approximate TMECorr
Input: Initial population 11; MTg repeat (for / = 0, 1, 1,...}
if Team-PSRO-MM then
(Pf + NE in restricted game G(P(LI)), P(L1)) else
(6) - NE in restricted game G(I 115)
for m iterations do
Update joint best response 3T toward B BT (16) via cooperative RL
Update joint best response 8o toward (R) via cooperative RL
-I - 11 {BT} -
- Ho U {
until un (Br())), (())))))) + (o0,4,,0001)) S ur (1F; uo 12)) +
Return: (14,
4.4 Team PSRO Mix-and-Match
Similarly to how Team DO-MM builds on Team DO by adding mixed-ame und-matched pure strategies, Team PSRO Mix-and-Matee (Team PSRO-MM) builds on Team PSRO by adding mixed-and sond--ndd-mtthhed deep RL policies. As in Team PSRO, once the joint best response for team is trained, it is added to to that team's population IT.. Similarly to Team DO-MM, an expanded two-player zero-sum normal form restricted game G(P(L))) P(U))) )) created. The actions of this normal form game correspond to mixed-and-mant and-matched joint strategies in the population and the payoffs correspond to the estimated expected value when one team chooses one joint policy and the other team chooses another joint policy ur (B(()))) ( Payoff values in the restricted game are estimated by sampling rollouts from both teams' joint policies. Team PSRO-MM described in Algorithm
5 Experiments
4-player Kuhn poker (13 ranks)
Liar's dice (coin)
Team DO
10a
Team DO-MM
10
Fictitions team-
Exploiability
Exploitbilltt
10-1
10-1
Team
Team DO-MM
Fictitious team-play
10
2
10
10
20
30
40
50
20
40
60
80
100
Number of hest response computations
Number of best response computations
Figure Experimental results in tabular games
5.1 Team DO Experiments
We run Team DO and Team DO-MM on two small games, Kuhn poker and Liar's dice, and present the results in Figure Although we do not know of any existing regret bounds for double oracle techniques, these results demonstrate that in practice double oracle methods work well and can find approximate TMECor in a reasonable number of iterations. Notably, Team DO-MM is able to achieve faster convergence compared to Team DO in the number of iterations. However, we found that since calculating best responses in this game does not take much time, computing the extra payoff values caused Team DO-MM to converge much slower in wall clock time compared to Team DO.

---

Additionally, both Team-DO methods outperform Fictitious Team Play (Farina et al., 2018b). which adds team best responses the opponent average strategy every iteration. large games, as shown below, finding best response requires much more time than evaluating the expected value of two team policies, so Team DO-MM converges faster wall clock time as well. We include detailed analysis of wall clock time on these tabular experiments in the appendix.
5.2
Team PSRO Experiments
X>S
CO
6PN
1.2
6N
DM Cify
(a) Elo
(b) Goal Diff. vs. AI
(c) Relative Pop. Performance
Figure 2: Team PSRO Results on Google Research Football. Both Team PSRO and Team PSRO-MM outperform self play, with Team PSRÓ-MM performing the best.
We demonstrate that Team PSRO can scale to large games by training it on the benchmark game of Google Research Football (GRF) (Kurach et al.) 2020). Because there do not exist any other game-theoretic techniques for approaching TMECor in large games, we only compare to self play. Although we do not know of any theoretical guarantees that self play will converge to TMECor, methods based on self play (Berner et al. 2019b Liu et al. 2019 Jaderberg et al. 2019) have achieved impressive performance
large team games. As result, believe that play reinforcement learning is a strong benchmark to beat. In these experiments we use the four our-player version of GRF and modify it that each player only observes the information of his own team, the ball, and three closest opponents" information (which means that there are always two opponents that are not observable for player). We also include results the perfect-information version of the game in the Appendix and find that the same pattern holds where Team PSRO-MM is better than Team PSRO which is better than self-play. We also include further training details in the Appendix.
We use the same reinforcement learning algorithm for both Team PSRO and self play, namely MAPPO with centralized critic and shared parameters for a team. We allow the centralized critic to see all players' information. Self play reinforcement learning continually trains one joint policy for one team against the other joint policy for the other team and does not make of population like Team PSRO. In Figure 2 we see that Team PSRO and Team PSRO-MM are both able to outperform self-play across all three measures of Elo, average goal difference against the built-in AI, and relative population performance (Balduzzi et al., 2019). Furthermore, Team PSRO-MM outperforms Team PSRO with small additional cost of extra rollouts evaluate the matrix payoffs. Since this is such large game, the time needed to compute the BRs is much more than the time needed to evaluate two team policies, the extra time is negligible.
Discussion
6.1
Limitations
As with any double oracle algorithm, the main limitation of our algorithm is that it suffers from lack of practical guarantees. It is possible that all pure strategies of the game must be expanded before termination, and indeed we find that in Kuhn poker, even using an exact best response plateaus indefinitely. With that being said, sometimes exploitability can be too strict of measure if the exact best response is hard to find. In the case of team games, where finding an exact best response is Na-Hard, perhaps being approximately unexploitable against a reinforcement learning best response is reasonable goal, and one that we achieve with Team-PSRO.

---

6.2
Future Work
There are many future directions build on this work. First, we are interested in continuing to scale up to large games, with the goal of becoming superhuman at bridge. A second direction of future work involves studying the problem of cooperative reinforcement learning directly, where improvements should directly transfer to our setting. A third research direction is transferring over new PSRO algorithms such as Anytime PSRO (MeAleer et al. 2022b). and NXDO (MeAleer et al.) 2021). Related efforts in solving team games using regret minimization and subgame solving possibly complimentary to our approach.
7
Acknowledgements
This material is based on work supported by the Vannevar Bush Faculty Fellowship ONR 1-0014-33-1-2876 National Science Foundation grants RI-2312342 and RI-1901403, ARO award W911NF2210266, and NIH award A2401085001.
References
Anagnostides, I., Kalogiannis, F., Panageas, I., Vlatakis- GaanakiiGGGarakkuuiiss, E.-V., and McAleer, Algorithms and complexity for computing nash equilibria in adversarial team games. Economics and Computation (EC), 2023.
Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnecki, W., Perolat, J., Jaderberg, M., and Graepel, T. Open-ended learning in symmetric zero-sum games. International Conference Machine Learning (ICML), 2019.
Basilico, N., Celli, A., Nittis, G. D., and Gatti, N. Team-maxmin equilibrium: efficiency bounds and algorithms. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 356-362, 2017.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q.. Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 192.0699,00 2019a.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q. Hashme, S., Hesse, C., et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06680 2019b.
Bowling, M., Burch, N., Johanson, M., and Tammelin, O. Heads-up limit hold'en em poker is solved. Science, 347(6218) 8), Jamuary 2015.
Brown, N. and Sandholm, T. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, pp. eaaol733, Dec. 2017.
Celli, A. and Gatti, N. Computational results for extensive-form adversarial team games. In AAAI Conference Artificial Intelligence (AAAI), pp. 962-972, 2018.
Farina, G. and Sandholm, T. Polynomial-time computation of optimal correlated equilibria in two-player extensive-form games with public chance moves and beyond. In ArXiv preprint, 2020.
Farina, G., Celli, A., Gatti, N., and Sandholm, T. Ex ante coordination and collusion in zero-sum multi-player extensive-form games. In Advances in Neural Information Processing Systems, pp. 9638-9648, 2018a.
Farina, G., Celli, A., Gatti, N., and Sandholm, T. Ex ante coordination and collusion in zero-sum multi-player extensive-form games. Advances in Neural Information Processing Systems, 31, 2018b.
Farina, G., Celli, A., Gatti, N., and Sandholm, T. Connecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity results. In International Conference Machine Learning, 2021.
10

---

Feng, X., Slumbers, O., Wan, Z, Liu, B., McAleer, S., Wen, Y., Wang, J., and Yang, Y. Neural auto-curricula in two-player sero-sum games, Advances in Neural Information Processing Systems, 34, 2021.
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S. Counterfactual multi agent policy gradients. In Proceedings of the Thirly-Second AAAI Conference on Artificial Intelligence, 2018.
Jaderberg, M.. Czarnecki, W. M., Dunning, I., Marris, L., Lever, G., Castaneda, A. G., Beattie, C., Rabinowitz, N. C., Moreos, S., Ruderman, A., al. Human-level performance in 3d multiplayer games with population-based reinforcement learning. Science, 364(6443) 865, 2019.
Kalogiannis, F,, Vlaaakis- E.-V., and Panageas, Teamwork makes von neumann work: Min-max optimization in two-team zero-sum games. arXiv preprint arXiv:2/11 1..0478, 2021.
Koller, D., Megiddo, N., and von Stengel, B. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2), 1996.
Kuba, G.G Chen, R., Wen, M., Wen, Y., Sun, F., Wang. J., and Yang, Y. Trust region policy optimisation multi-agent reinforcement learning. In International Conference on Learning Representations, 2022. URL /tpppeee///oo net/ forum? 1=EEGGGFKTTXX 1
Kuhn, H. W. Extensive games and the problem of information. Kuhn, H. and Tucker, A. W. (eds.), Contributions to the Theory of Games, volume 2 of Annals of Mathematics Studies, 28, pp. 193- 216. Princeton University Press, Princeton, NJ, 1953.
Kurach, K., Raichuk, A., Stanczyk, P., Zajac, M., Bachem, O., Espeholt, L., Riquelme, C., Vincent, D., Michalski, M., Bousquet, O., et al. Google research football: A novel reinforcement learning environment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4501-4510, 2020.
Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Pérolat, J., Silver, D., and Graepel, T. A unified game-theoretic approach to multiagent reinforcement learning. Advances Neural Information Processing Systems (NeurIPS), 2017.
Liang, Y., Sun, Y., Zheng, R., Liu, X., Sandholm, T., Huang, F., and McAleer, S. Game- theoretic robust reinforcement learning handles temporally-coupled perturbations. arXiv preprint arXiv:2307. /2062, 2023.
Liu, S., Lever, G., Merel, J., Tunyasuvunakool, S., Heess, N., and Graepel, T. Emergent coordination through competition. International Conference on Learning Representations, 2019.
Liu, S., Lever, G., Wang, Z., Merel, J., Eslami, S., Hennes, D., Czarnecki, W. M., Tassa, Y., Omidshafiei, S., Abdolmaleki, A., et al. From motor control to team play in simulated humanoid football. arXiv preprini arXiv:2 205. 121110551111. /2/96 2021a.
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. Advances in Neural Information Processing Systems, 34:941-955 2021b.
Lowe, R., Wu, Y. I., Tamar, A., Harb, J., Abbeel, O. P., and Mordatch, I. Multi-agent actor-critic for mixed cooperative-cone competiiiv environments. Advances in neural information processing systems, pp. 6390, 2017.
Marris, L., Muller, P., Lanetot, M., Tuyls, K., and Graepel, T. Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers. In International Conference on Machine Learning, pp. 7480-7491. PMLR. R, 2021.
McAleer, S., Lanier, J., Fox, R., and Baldi, P. Pipeline PSRO: A scalable approach for finding approximate Nash equilibria in large games. In Advances Neural Information Processing Systems, 2020.

---

McAleer, S., Lanier, J., Baldi, P., and Fox, R. XDO: A double oracle algorithm for extensive-form games. Advances in Neural Information Processing Systems (NeurIPS), 2021.
McAleer, S., Lanier, J., Wang. K., Baldi, P.,. Fox, R., and Sandholm, T. Self-play psro: Toward optimal populations in two-player zero-sum games. arXiv preprint arXiv:2207.0654/4 2022a.
McAleer, S., Wang, K., Lanier, B., Lanctot, M., Baldi, P., Sandholm, T., and Fox, R. Anytime PSRO for tlo-rlayer zero-sum games. CoRR, abs/2201.077000 2022b. URL httpt::/p//axx erg/aba/ 22011. 07700
McMahan, H. B., Gordon, J., and Blum, A. Planning in the presence of cost functions controlled by an adversary. Proceedings of the 20th International Conference on Machine Learning (ICML), 2003.
Mguni, D., Jafferjee, T., Chen, H., Wang, J., Fei, L.,, Feng, X., McAleer, S., Tong, F., Wang, J., and Yang, Y. Mansa: Learning fast and slow in multi-agent systems. International Conference on Machine Learning (ICML), 2023.
Muller, P., Omidshafiei, S., Rowland, M., Tuyls, K., Perolat, J., Liu, S., Hennes, D., Marris, L., Lanc- tot, M., Hughes, E., et al. A generalized training approach for multiagent learning. International Conference on Learning Representations (ICLR), 2020.
Papoudakis, G., Christianos, F., Schäfer, L., and Albrecht, S. V. Comparative evaluation of multi-agent deep reinforcement learning algorithms. arXiv preprint arXiv:2006.07869 2020.
Perez-Nieves, N., Yang, Y. Slumbers, O., Mguni, D. H.. Wen, Y., and Wang, J. Modelling behavioural diversity for learning in open open-ended games. In International Conference on Machine Learning, pp. 5514-8524 PMLR, 2021.
Rashid, T., Samvelyan, M., Schroeder, C., Farquhar, G., Foerster, J., and Whiteson. S. QMIX:
Monotonic value function factorisation for deep multi-agent reinforcement learning. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4295-44954444 4304. PMLR, 10-15 Jul 2018. html
URL hwtphhttpppooceecinoeeo
Romanovski,, I. Reduction of a game with complete memory to matrix game. Soviet Mathematics, 3, 1962.
Schäfer, L.. Slumbers, O., McAleer, S., Du, Y., Albrecht, S. V., and Mguni, D. Ensemble value functions for efficient exploration multi-agent reinforcement learning. arXiv preprint arXiv:2302.03449, 2023.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., Driessche, G. d., Graepel, T., and Hassabis, D. Mastering the game of go without human knowledge. Nature, 55077666::54333999 10 2017. ISSN 0028-0836. doi: 10.1038//ature22270.. URL hwllatttptatttss/eo...ooo 1038/nan (033//nauure2440
Slumbers, O., Mguni, H., McAleer, S., Wang, J., and Yang. Y. Learning risk-averse equilibria in multi-agent systems. International Conference Machine Learning, 2023.
Tang, X., Dinh, L. C., McAleer, S. M., and Yang, Y. Regret-minimizing double oracle for extensive- form games. International Conference Machine Learning, 2023.
Vinyals, O., Babuschkin, I., Czarnecki, M. W., Mathieu, M., Dudzik, A., Chung. J., Choi, H. D., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre. L., Cai, T., Agapiou, P. J., Jaderberg, M., Vezhnevets, S. A., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, L. T., Gulcehre, C., Wang, Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap, T., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, pp. 1-5, 2019a.
12

---

Vinyals, O., Babuschkin, I., Czarnecki, W. M.. Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)3300-333
2019b. 2019b.
von Stengel, B. and Koller, D. Dexm-naxmin equilibria. Games and Economic Behavior, 21(1-2): 309-321, 1997.
Wang, Y., Han, B., Wang, T., Dong, H., and Zhang, C. {DOP): Off-policy multi-agent decomposed policy gradients. International Conference on Learning Representations, 2021. URL https
//openreview.rr net forum id= qKivAdI3
Wellman, M. P. Methods for empirical game-theoretic analysis. AAII conference on artificial intelligence, 2006.
Xu, Z., Liang Y., Yu, C., Wang, Y. and Wu, Y. Fictitious cross-play: Learning global nash equilibrium in mixed cooperative-compeiive games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pp. 1053-1061, 2023.
Yao, J., Liu, W., Fu, H., Yang, Y., McAleer, S., Fu, Q., and Yang, W. Policy space diversity for non-transitive games. Conference Neural Information Processing Systems (NeurIPS). 2023.
Yu, C., Velu, A., Vinitsky, E., Wang, Y., Bayen, A., and Wu, The surprising effectiveness of ppo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0195: 2021.
Zhang, B. H. and Sandholm, T. Team correlated equilibria in zero-sum extensive-form games via tree decompositions. arXiv preprint arXiv: 100.052844 2021.
Zhang, B. H., Farina, G., and Sandholm, T. Team belief dag form: A concise representation for lerm-correlated game-theorete decision making. arXiv preprint arXiv:2202.00788. 2022.
Zhang, B. H., Farina, G., Anagnostides, I., Cacciamani, F., McAleer, M., Haupt, A. A., Celli, A., Gatti, N., Conitzer, V., and Sandholm, T. Computing optimal equilibria and mechanisms via learning in zero-sum extensive-form games. Conference on Neural Information Processing Systems (NeurIPS), 2023.
Zhang, Y. and An, Computing cam-maxmin equilibria in zero-sum multiplayer extensive-form games. In AAAI Conference on Artificial Intelligence (AAAI), pp. 2318-2325, 2020a.
Zhang, Y. and An, B. Converging to team-maxmin equilibria in zero-sum multiplayer games. In International Conference on Machine Learning (ICML), 2020b.
Zhang, Y., An, B., and Černy, J. Computing ex ante coordinated deam-maxmi equilibria in zero-sum multiplayer extensive-form games. In ArXiv preprint:2009.12222 2020.
A Proof of Proposition
Proof. Note that by Equation 3 and the stopping condition in Algorithm ! when Team DO(-MM) terminates, the meta-NE (ut, (5) is a TMECor. What is left show that Team DO(-MM) eventually terminates. Team DM(- eventually terminates because in every iteration it either adds a new strategy for at least one player or it terminates. To see this, consider the case where no new strategies are added for either player in an iteration. Then the best response value for each player is no greater than the value of their meta-NE against the opponent, so Equation is satisfied and Team DO(-MM) terminates in a TMECor.
B Tabular Best Best-Response Oracle
In this section we give the formulation of the Seam-best-responss oracle we implemented in the tabular case.
As discussed the body (Section 4.1 , the algorithm is based on integer programming and implements the algorithm introduced by Celli & Gatti (2018). The integer programming formulation uses the
13

---

fact that by convexity, the optimal solution je" E AIIT1 IT2)) in 4 puts all mass on exactly a pair
(πi T E I1T1 Ilr. With that, for any can write
Σ
pf(an: TT2) [ E [T]())] (mf E [T2(2)) o lon (=) x2)()12(2))
iT ellm (4) (=)
Hence, we can rewrite as
(Ro(H0)= =
arg max (#f Jelly x Tua
Σ 2E
ür (3))
Σ Ho (TO1, To2) ToI (oloo(a) (T22
We represent the set of plans (# ` f2) E IT TT using binary variables and linear constraints, by using the well-known fact that 1l V a00n000000000 2m
2m Ill2 J12 n {0, 1 Finally, for each in the objective function by introducing
E Z we model the product loT 12 additional binary variables &. subject to the constraints & < क lon (z)], (ii) &. S (T2l
and (iii) &s 2 को (TTI (z)] + Tf2(oT2(2)] 1. Putting everything together, we arrive to the best- response integer program
arg max
Σ (T()){= 2EZ
Σ (TOs #oI (2) (lloa))
subject to:
1 S -. (oTT
V2 E Z
0 1 =
V2 E Z
1 ( + TieloTe()]] -1
E Z
4 का E)n
5 TT y/2
@ E. E (0,1)
Ve 7
mm mा E 1m
1T2 {0, 11 112
C Tabular Experiment Details
For 4-player Kuhn poker with 13 ranks and 4-player Liars dice (coin) with 2 outcomes we used the original multiplayer game but had player 0 and player be one team and player I and player 3 be on the other. Then each player's utility is the average of their original utility and their partner's s. This version of Kuhn poker has 566280 leaves and this version of Liar's coin has 4080 leaves.
D Details of Google Research Football Training
The Google Research Football (Grac et al. 2020) environment is simulation environment for real-world football games, where each game consists 3000 steps. Players need to control one more players compete with the opposing team, and the rules are the same as in general football games.The team with the highest number of goals at the end of the match wins. To validate the effectiveness of algorithm, conducted training and evaluation of our algoritm the full 5 vs. 5 game in GRF, where the goalkeeper is controlled by built-in AI, while the rest of the four players controlled by model.
Feature Engineering and Action Space. Given the default setting where every player has access to complete game information, we have meticulously crafted (33-dimensional feature vector to
14

---

enhance the training process. The input layer of the network is structured as [133 x 128] to ensure effective feature representation and processing. Furthermore, the player's action space is defined using default set of 19 discrete actions, encompassing fundamental moves such as movement, passing, and shooting. Consequently, the output layer of the network configured as [128 x 19), allowing for the mapping of features to appropriate action selections.
Reward Shaping. Due to the sparsity of rewards in the GRF environment, it crucial design appropriate reward mechanisms. In addition to the rewards provided by the environment, we have designed specific reward components, including win reward, goal reward, yellow card reward, checkpoint reward and lost ball penalty, to expedite our training process and enhance its effectiveness. We adopt a consistent reward configuration across all our experiments.
Training. For each algorithm, our models were trained for 1500M steps on a cluster with 256 CPUs and 8 RTX3090 GPUs, using three different random seeds. The batch size for each GPU was set to 512 and The discount factor ? was set to 0.9999. We employed the Adam optimizer with a learning rate of 0.00005.5 Speciffccl,, for team PSRO-MM. to mitigate the increased training cost associated with incorporating excessive mix strategies, we implemented a strategy of introducing Iwo mix strategies to the population in each round (We set two here, however, you can add more if you wish). Each mix strategy was constructed by randomly selecting pure strategies from past checkpoints and assigning them individual players within the team. This approach allows for controlled inclusion of mix strategies while managing the overall training overhead, enabling an efficient training process while benefiting from the incorporation of diverse strategies within the population. More haper-parameters are summarized as bellow:
Value
game length batch size
3000
512
max clipped value loss
0.2
gradient clip norm value loss discount factor 7 learning rate ppo update number gain GAE entropy coefficient
10
huber loss
0.9999
5e-4
5
0.01
0.95
0.001
Table 1: Haper-parameters
Evaluation Metrics. Due to the complexity of the GRF, calculating the exploitability of a specific policy or Predictive Error (PE) for certain population becomes challenging. Both metrics involve max or min operators, and approximating the best response can significantly inaccurate in such complex game. We use the relative population performance (RPP/Vinyals et al.] (2019a) as the metric. RPP represents the game interaction results of two populations À and B under their meta-nash equilibrium. Besides, onsidering our objective of identifying robust policies with strong performance in worldworld games, we assess the effectiveness by comparing the average goal differences, score and Elo between the policies obtained from different methods and the built-in bots with varying difficulty levels within the General Reinforcement Learning Framework (GRF). This evaluation allows us to gauge the capabilities of the policies in challenging game scenarios and their ability outperform predefined bot opponents.
Elo Calculation Elo refers to the Elo rating system used to measure the relative skill levels of the algorithms. For the computation of Elo ratings, they was computed by making agents play against each other. Here is a detailed explanation of how they were computed:
Assign an initial Elo rating (1000 in our setting) to each player.
Determine the expected score of each player in game. This is calculated as follows:
- For player A: expected score
(B-A)
1+10 400
15

---

For player B: expected score
(4-16 where A and B are the current Elo
1+10 400
ratings the two players.
Play the game and determine the actual score of each player.
Update the Elo ratings of the two players based on the outcome of the game and the expected scores:
For player A: new rating old rating K (actual score expected score)
For player B: new rating = old rating K x (expected score
actual score) where K a constant that determines the "weight" of the update (set as 10 in this case).
Repeat the process for each game, using the updated Elo ratings from the previous game as the starting point for the next game.
Additional Experiments. Since each player can observe the entire game information in GRE, conducted experiments involving feature engineering to create an imperfect information scenario in the main body. In this scenario, each player only able observe information related teammates, the ball, and the three nearest opposing players, which means there is always lack of information regarding two opposing players. However, also conducted experiments with perfect information, as depicted in the figures. Remarkably, we observed that the same pattern held true in both imperfect and perfect information scenarios, with Team PSRO-MM outperforming Team PSRO, which in turn outperformed self-play.
Team PSSOO
5%
880
62
MANISHOM
DAV
Madea
(a) Elo
(b) Goal Diff. VS. AI
(c) Relative Pop. Performance
Figure 3: Team PSRO Results on Google Research Football perfect information scenario. Both Team PSRO and Team PSRO-MM outperform self play, with Team PSRO-MA performing the best.
Additionally, we aimed to compare the performance of both Team PSRO and Team PSRO-MM as the training time steps increased, using the policy trained by self-play as the benchmark. Since draws can occur in football, win rate may not accurately reflect the policies' performance. Therefore, we used average scores the evaluation metric, where the score for a single game is for win, 0.5 for a draw, and 0 for a loss. To better reflect the relative strength of each policy against the other, we multiplied the average scores by 100.
The results of the experiments are presented Figure with the dashed line representing the performance of the policy trained through self-play. We can see that both Team PSRO and Team PSRO-MM ultimately outperform self-play. Additionally, Team PSRO and Team PSRO-MM exhibit comparable performance in the initial stages of training. However, as the training timesteps progress, Team PSRO-MM exhibits superior performance, surpassing Team PSRO. This signifies that the integration of mixed strategies enhance the training effectiveness and robustness of the models. With an extended duration of training, Team PSRO-MM demonstrates a heightened ability to adapt to complex game environments, yielding eigher-uuait, strategies.
Finally, we include additional comparisons with fictitous play (FP) and prioritized fictitous self play (PFSP). These methods learn team best response to either the opponent average strategy (in FP) or a mixture of the average and the most recent (PFSP). We show figure that Team PSRO and Team PSRO-MM outperform these additional baselines well.
16

---

Anarape
Timostop
160
Timossop
100
(a) Perfect Information
(b) Imperfect Information
Figure Team PSRO results on both perfect and imperfect information scenarios of Google Research Football. Both Team PSRO and Team PSRO-MM outperform self-play, with Team PSRO-MM performing the best.
(a) Additional Baselines Elo
(b) Additional Baselines Head to Head
Figure 5: We include additional baselines of fictitious play and prioritized fictitious self play and show that Team PSRO and Team PSRO-MM are able to outperform all existing basclines.
17


Reviews:
[{"review_id": "peGUNpQW8r", "reviewer": "Reviewer_MAu9", "summary": "This work aims to find TMECor in two-team zero-sum games. They extend PSRO from two-player games to two-team games and proposed Team-PSRO which is guaranteed to converge to a TMECor. They further proposed Team-PSRO Mix-and Match which generates more joint policies by mixing individual policy from different PSRO iterations. They evaluate the proposed algorithms on Google Research Football and achieved better results than self-play.", "questions": "1. What is the difference between Team-PSRO and using PSRO by regarding the whole team as a single agent.\n2. If there are n players in one team, and team-PSRO has run k iterations, then the number of joint policies produced by mix-and-match would be $k^n$, and it would require a lot of rollouts to complete the payoff matrix. Did the author produce all the joint policies in the experiments? Is there a better way to produce part of the joint policies that are most useful for training?\n3. What is the rule of 4-player Kuhn poker and how many players are there in Liar's dice? These two games are originally two-player games and there is no description about how they are modified into two-team games.\n4. In the experiment of GRF, how many iterations are trained for Team PSRO and Team PSRO-MM？Does the population start from random policy?\n5. Comparison with NFSP and CFR in 4-player Kuhn poker and Liar's dice.\n6. Comparison with PSRO w. BD and RD, FXP, NFSP in GRF.", "limitations": "The authors have discussed the limitations.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper is clearly written and easy to follow. The use of symbols and definitions in the theory part is in accordance with the standard notations.\n", "weaknesses": "The novelty of the proposed algorithms is marginal, and more comparisons with closely related work are needed in the experiment. Please see below for detailed discussions.\n\n1. Lack of novelty. Team-PSRO simply applies PSRO to two-team zero-sum games by learning a joint best response for the whole team, which has no difference from PSRO for two-player games and has been discussed in recent works like [4]. Team-PSRO-MM further proposes to mix individual policies in different iterations to generate more joint policies. However, mixing all individual policies will produce exponentially many joint policies and requires a lot more computation to get the payoff table. This paper simply mixes all policies or randomly samples policies to mix. It would help improve the novelty of this paper if the author can design a better way to smartly mix-and-match to produce joint policies that are most useful.\n2. Need more baselines in experiments. For small games like 4-player Kuhn poker and Liar's dice, methods like NFSP [1], CFR [2] should be added as baseline. Though these methods are designed for two-player zero-sum games, they can be easily extend to two-team zero-sum games with some modification. For larger games like GRF, some closely related work like PSRO w. BD and RD [3], FXP [4] should be added as baseline. These methods also build on PSRO and report strong results in GRF full games. It is also straightforward to use NFSP in GRF.\n\n[1] \"Fictitious Self-Play in Extensive-Form Games.\" Heinrich, Johannes, Marc Lanctot, and David Silver.\n\n[2] \"Deep counterfactual regret minimization.\" Noam Brown, et al.\n\n[3] \"Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games.\" Xiangyu Liu, et al.\n\n[4] \"Fictitious Cross-Play: Learning Global Nash Equilibrium in Mixed Cooperative-Competitive Games.\" Zelai Xu, et al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our gratitude to the reviewer for taking the time to assess our work and providing valuable insights. We would like to clarify certain aspects of our research that may not have been fully grasped, along with a plan to address the constructive suggestions.\n\n**Lack of Novelty** \nWhile it is true that our approach leverages the principles of PSRO, there are significant differences between applying PSRO to two-player games and two-team zero-sum games. The transition from the individual to team-based setting introduces complexities that need to be taken into account when designing algorithms. One consideration in the setting we study in this paper is that the players on the same team are not allowed to communicate with one another once the game has started.  **A direct consequence is that methods like CFR are not applicable, unlike what is stated in the review in Weakness 2 and Question 5.** \n\nWe agree that a more sophisticated approach to mixing and matching could further improve performance. For example, we can select the top k strongest opponents (in this case k equals 4) after every iteration of evaluation and use these policies to get a mixed policy. Then we can add this policy to the population. We call this variant as Team PSRO-MM Top-K, and we have done additional experiments to compare our method with other baseline methods, including a deep RL version of fictitious team play [FCGS18] and PFSP [AlphaStar] (For PSRO w. BD and RD, it may take a lot of time to implement and train because they didn't reveal their code for GRF experiments.) **We have included these experiments in the rebuttal pdf and show that the PSRO-MM Top-k outperforms all other baselines.** \n\nThank you for the reference to Xu et al. That paper indeed proposes a similar algorithm to Team-PSRO but it came out after the NeurIPS deadline so we were not able to cite it for the submission. We will be sure to reference it as contemporary work in the camera-ready version. However, in that paper the authors do not make a connection to TMECor and do not propose the idea of Team-PSRO-MM. \n\nNeed for More Baselines in Experiments: We concur with the reviewer's observation that more baselines in experiments would provide a more comprehensive evaluation. **However, the reviewer’s suggestions for including methods like NFSP, CFR, and replicator dynamics do not make sense in our setting (see above).** NFSP, CFR, and replicator dynamics are all algorithms for two-player zero-sum games with perfect recall. They do not apply to two-team zero-sum games. **Although the suggested algorithms do not make sense in our setting, we have included new results with Fictitious Team Play [FCGS18]. As shown in the figure in our rebuttal pdf, we find that our methods outperform this baseline. For deep RL experiments, as mentioned above, we include baselines of deep RL versions of fictitious team play and PFSP, and show that we outperform them.** \n\n**Clarification on Specific Questions**\n\nDifference between Team-PSRO and single agent PSRO: Our setting considers games where team members cannot communicate during the game. As a result, Team-PSRO learns joint best responses for the team, taking into consideration the fact that team members cannot communicate. This differs significantly from considering the whole team as a single agent, which is equivalent to two-player zero-sum games with perfect recall. We study two-team zero-sum games which are equivalent to two-player zero-sum games with imperfect recall. In this setting, Team-PSRO converges to TMECor, instead of Nash as in two-player zero-sum games. We will add more discussion of this in the paper, although this is fairly well-known background information in the literature.\n\nConcerns about joint policies in Team-PSRO: We acknowledge the computational challenges related to the mix-and-match strategy, and we will expand on the methods used in our experiments to manage these complexities. Your suggestion for a more strategic approach is well-received, and we have included a new variant called PSRO-MM Top-k which outperforms all other methods. However, for team games with two players per team, which capture many domains of interest such as bridge, the number of joint policies only scales quadratically. As shown in our paper, Team-PSRO-MM seems to perform well in practice and is a valuable contribution as-is.\n\nDescriptions of 4-player Kuhn poker and Liar's dice: Your point is valid; we will provide detailed information on the modifications made to these games to adapt them to two-team formats in the revised version of the paper. These games are standard in the literature, for example in [FCGS18].\n\nExperiment details: Each policy was trained for 1.5×10e9 iterations. Since the random policy doesn't know how to pass or shoot, which makes it hard to train(especially in imperfect information scenarios), we first used RL to train a random policy against build-in AI with easy difficulty, and stopped training when win rate reaches 40%. The aim of it is to enable the agent to learn basic behaviors (especially shooting). Then we used Self-play and Team-PSRO to train the pretrained model. Specifics about the number of iterations and the starting policies for Team-PSRO and Team-PSRO-MM will be included to enhance clarity.\n\n\nComparisons with other models: As noted above, NFSP and CFR are not valid algorithms for our setting, but fictitious team-play [FCGS18] is. We include additional experiments benchmarking against fictitious team play and show that our methods outperform fictitious team play.\n\n[FCGS18] Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. \"Ex ante coordination and collusion in zero-sum multi-player extensive-form games.\" In: Advances in Neural Information Processing Systems (NeurIPS), 2018."}, {"review_id": "fUWeRsSlsB", "reviewer": "Reviewer_kqkC", "summary": "The paper presents “game-theoretic” reinforcement learning methods for playing zero-sum games (between teams of players).  A theoretical claim (proof is in the supplementary material) is made about convergence of the base tabular methods to the TMEcor solution concept, and empirical results compare the methods to self play RL in the “Google Research Football” domain.\n", "questions": "The results need better explanation and analysis, particularly surrounding the presentation of Figure 2.  Not enough information is supplied.  I have the following questions: (1) Were appropriate statistical tests run to evaluate statistical significance?  If so, they should be reported.  If not, claims of being better are unsubstantiated.  (2) What do the error bars in Figure 2a-b represent?  (3) What is Elo (Figure 2a)?  (4) What is the built-in AI against which the algorithms were paired?  Why only the comparisons when paired with the built-in AI?  What about results when self play RL and PSRO-MM were the opponents?  What about RL algorithms trained against a variety of opponents instead of just self play?\n\nI'm potentially inclined to change my review based on the answers to these questions.\n", "limitations": "Yes, I think the paper does a good job with this.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. By and the large, the paper is presented very well.  Concepts are explained well, the paper is very polished.  The derivation and explanation of methods appear to be sound.\n\n2. The topic seems important, with well-defined limitations\n\n3. The results appear to show good (albeit incremental) performance, though see statements in “weaknesses” for clarification\n\n4. The enhanced methods are simple\n\nOverall, this seems to be a useful paper.\n", "weaknesses": "1. The results need better explanation and analysis, particularly surrounding the presentation of Figure 2.  Not enough information is supplied.  I have the following questions: (1) Were appropriate statistical tests run to evaluate statistical significance?  If so, they should be reported.  If not, claims of being better are unsubstantiated.  (2) What do the error bars in Figure 2a-b represent?  (3) What is Elo (Figure 2a)?  (4) What is the built-in AI against which the algorithms were paired?  Why only the comparisons when paired with built-in AI?  What about results when self play RL and PSRO-MM were the opponents?  (5) What about RL algorithms trained against a variety of opponents instead of just self play?\n\nI think these questions are easily addressable, and understand the difficulty of fitting everything into a short conference paper.  It remains to be seen whether the clarifications would favor the proposed techniques or not.\n\n2. The paper has a couple of unsubstantiated claims that, in my opinion, need to be removed or altered:\n\nA) The paper claims to “introduce *the first* game-theoretic techniques for two-team games” (emphasis added).  The paper does not prove this to be true (it is doubtful this could be proven), and often such claims are not true.  The paper later re-states the claim with the caveat of it being the first “to their knowledge,” which is better but still unsubstantiated.  In general, the claim about being “the first” has little to no scientific value and causes the reader to focus on whether it is indeed “the first” rather than the contribution of the paper.  I’d recommend the statements be removed altogether.\n\n- Second, the paper claims (intro to section 4) that tabular methods will not scale to large games.  That may or may not be true (seems like there are ways it could be done, and perhaps very well, if one looks at it from a different paradigm).  Regardless, the paper does not back up the claim.  I think the statement should be softened or at least the opinion be given better context.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's time and detailed feedback. We aim to address all the concerns mentioned:\n\n**Results Explanation and Analysis (Figure 2)**\n\nError Bars and Statistical Significance: We acknowledge that the information about statistical tests was not included in the main text. Indeed, we performed statistical tests for the comparisons, and the results were statistically significant. This will be clarified in the revised version. The training details and additional experiments can be found in the appendix. For Figure 2a-b, we made the agents trained by different algorithms play against built-in AI with different difficulties and compared the goal difference. To avoid the influence of randomness, we ran three seeds for each experiment, the error bars in Figure 2a-b means the standard deviation. This comparative approach has also been employed in PSRO w. RD and BD[1] as a major evaluation method.\n\n\nElo Explanation: Elo (Figure 2a) refers to the Elo rating system used to measure the relative skill levels of the algorithms.  For the computation of Elo ratings, they was computed by making agents play against each other. Here is a detailed explanation of how they were computed:\n- Assign an initial Elo rating (1000 in our setting) to each player.\n- Determine the expected score of each player in a game. This is calculated as follows:\n- For player A: expected score = 1 / (1 + 10^((B - A) / 400))\n- For player B: expected score = 1 / (1 + 10^((A - B) / 400)) where A and B are the current Elo ratings of the two players.\n- Play the game and determine the actual score of each player.\n- Update the Elo ratings of the two players based on the outcome of the game and the expected scores:\n- For player A: new rating = old rating + K * (actual score - expected score)\n- For player B: new rating = old rating + K * (expected score - actual score) where K is a constant that determines the \"weight\" of the update (set as 10 in this case)\n- Repeat the process for each game, using the updated Elo ratings from the previous game as the starting point for the next game.\nWe will add an explanation of these details in the revised version.\n\nExplanation of Built-in AI and Comparison to other Methods: GRF incorporates  built-in AI agent and allows for difficulty adjustments. Consequently, in GRF-related experiments, the built-in AI is frequently employed as a benchmark to evaluate the performance of trained agents, such as PSRO w.RD and BD[1], TiKick[2], etc. We use relative population performance to evaluate the performance of different populations. In the appendix, in Figure-4, by using the agent trained by Self-play as the benchmark, we also compare the performance of both Team PSRO and Team PSRO-MM as the training time steps increased.\nNew Self-Play Variant: While we haven’t seen the suggested approach of RL trained against a variety of opponents in the literature, and we don’t predict that such a method would have game-theoretic guarantees, this is an interesting suggestion for future work.\n\n\n[1] Liu, X., Jia, H., Wen, Y., Hu, Y., Chen, Y., Fan, C., ... & Yang, Y. (2021). Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. Advances in Neural Information Processing Systems, 34, 941-952.\n[2] Huang, S., Chen, W., Zhang, L., Xu, S., Li, Z., Zhu, F., ... & Zhu, J. (2021). TiKick: towards playing multi-agent football full games from single-agent demonstrations. arXiv preprint arXiv:2110.04507.\n\n\n**Unsubstantiated Claims**\n\nFirst Scalable Game-Theoretic Techniques Claim: We do not claim to be the first game theoretic technique for two-team games. That is clearly not true based on the literature we cite in the paper. Instead, we claim to be the first **scalable** game-theoretic technique for two-team games. The current most scalable method for two-team games is Zhang et al. [ZFS23], which is a tabular method that clearly will not scale to google research football. We will soften the language a bit by claiming that *to our knowledge* we are the first scalable game-theoretic technique for two-team zero-sum games.  \n\n[ZFS23] Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. \"Team Belief DAG: A Concise Representation for Team-Correlated Game-Theoretic Decision Making.\". In: International Conference In Machine Learning (ICML), 2023.\n\n\n**Answers to Questions**\n\nWe believe that the answers provided above address the questions raised by the reviewer.\n\n**Conclusion**\n\nWe value the constructive feedback provided, and we believe that with the planned revisions, the paper will be strengthened significantly. The questions and concerns raised are indeed addressable, and we are committed to making the necessary changes to clarify all aspects.\n\nWe hope that these explanations and our commitment to revise the paper accordingly will lead the reviewer to reconsider the rating. Thank you once again for the thoughtful review, and we look forward to your feedback on our responses.\n"}, {"review_id": "sfk2uYxzwT", "reviewer": "Reviewer_Gu1R", "summary": "This paper proposes two algorithms, “Team PSRO” and “Team PSRO Mix-and-Match” for zero-sum two-team games. Team-PSRO is guaranteed to converge to a TMECor. The algorithms extend PSRO to zero-sum two-team games. Team-PSRO Mix-and-Match is an improved version of Team-PSRO with better population policies. The experimental results show the convergence of Team DO in Kuhn poker and Liar’s dice, and Team PSRO beats self-play in the Google Research Football environment.\n", "questions": "The citations are written in a very confusing way. I believe you use a wrong latex command. \n", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Extend PSRO to “Team PSRO”, and propose “Mix-and-Match” Team PSRO. \n- Team-PSRO is guaranteed to converge to a TMECor. \n- The experimental results show the convergence of Team DO in Kuhn poker and Liar’s dice, and Team PSRO beats self-play in the Google Research Football environment.\n", "weaknesses": "- The description about Team DO-MM and Team PSRO-MM is unclear. For example, the function P is not clearly described, so it becomes unconvincing for the success of the new method. \n- It is unclear about how NE is derived exactly in TEAM-PESO when implementing it. It would be also helpful if an anonymous github is given or in the supplementary attachment. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful examination of our paper and their valuable comments. In response to their concerns, we provide the following explanations and planned corrections:\n\n**Weaknesses**\n\t\nUnclear Description about Team DO-MM and Team PSRO-MM: P is defined in line 262. We will move this definition to the notation section to make it clearer.  We will also work on improving the text to better elucidate the concepts and methods involved in Team DO-MM and Team PSRO-MM.\t\n\nDeriving NE: The paper indeed missed a detailed description of how NE (Nash Equilibrium) is computed in TEAM-PSRO. The short answer is that we solve it exactly using an LP. We will add the required details in the revised version, making sure it's clear and understandable.\n    \t\nCode Availability: Your suggestion about providing an anonymous GitHub link or supplementary attachment with the code is valuable. We will try to provide an anonymized repository for the camera-ready version. \n\n\n**Questions**\n\t\nConfusing Citations: We apologize for the confusion caused by the way citations are written. We suspect a technical issue in the LaTeX formatting. We'll correct this in the revision, ensuring that the citations follow a consistent and standard format.\n\n**Conclusion**\n\nWe are committed to addressing all the points you have raised and believe that these revisions will substantially enhance the clarity and completeness of the paper. We hope that our response assures you of our determination to deliver a high-quality paper and that you might consider a higher rating. Thank you once again for your thoughtful review, and we look forward to your further feedback.\n"}, {"review_id": "PhLRclt66E", "reviewer": "Reviewer_eV3g", "summary": "This work addresses the problem of solving large-scale zero-sum two-team games. To solve this they explore extensions to the Double Oracle and Policy-Space Response Oracle algorithms that solve for a team-based equilibrium concept called TMECor. This is a straightforward extension of both of these algorithms that modifies the equilibrium concept and how policies are added to the empirical game. They evaluate their methods on the four-player variants of Kuhn Poker, Liar's Dice, and Google Football.", "questions": "- L33: Why are you considering TMECor and what other alternatives did you consider and why not them?\n- Could you please cite and define TMECor and its abbreviation?\n- L56: The stratego paper explicitly says they use self-play. Could you please provide a citation that the in fact are using Pipeline PSRO? \n- L123: I thought team games defined the players sharing payoffs. Why are they being separated here?\n- L247: What is the \"variant\" of the algorithm? What specific changes are being made that are novel to this work and why are they necessary? If applicable, can you show gains from these changes?\n- This work could be enhanced by including baseline method(s). For example, natural one is to consider that each teamplayer plays the same policy, where the policy parameters are a correlation device and their private information realizes different behaviors. Another option is to treat each team as a single agent and then an algorithm like QMIX to factor out per-player behavior. Without something akin to these baselines, it's hard to understand what benefit of the team-like treatment applied here.\n- L292-293: It's not clear to me that this is true. Surely, if the first 1-n BR are exact and the last, n, iteration is an epsilon BR, then the final result will be an approx TMECor. However, the compounding errors of having epsilon BRs at every iteration makes it hard to say anything about convergence. Or are you trying to make a super weak claim about how approximate the TMECor is? If so, I suggest being more clear about this.\n- L305: If the teammates are sharing policy parameters what is really the difference between Team-PSRO and Team-PSRO-MM? The strategy sets are the same?", "limitations": "Adequately discusses limitations with team double oracle (L220-225), and generally (L356-362).", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Background clearly explains all of the necessary elements required.\n- The subscripting used in notation throughout that uses both color and unique font (colorblind-friendly) helps keep keep concepts very clear and organized.\n- This paper is honest and humble with how much of their work is building upon preexisting work.\n- Include discussions of their results on both algorithmic iterations and walltime.\n", "weaknesses": "- Related work contains a lot of very tangential references. For example, the various PSRO extensions. Later in the paper a variety of significantly more related work is discussed, it would make sense for this to be in the related work section instead.\n- L232: This reads like the authors are claiming using DRL as a BR oracle is a contribution of this work, when it is one of PSRO.\n- L238-244: This is pretty challenging to read and is a single sentence, strongly recommend editing into individual statements.\n- In the PSRO sections, the empirical game is treated as a restricted game. This is misleading and incorrect, because the payoffs are estimates.\n- No baselines are considered in DO variants of their algorithms.\n- Limited evaluation of the PSRO variants of the algorithms.\n- Missing approximate exploitability curves of PSRO algorithms. Consider also performing a combined-game analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed review and valuable feedback on our work. These insights have greatly helped us in identifying areas of improvement. We would like to address the concerns as follows:\n\n**Strengths**\n\nWe're pleased that the reviewer appreciated our clear background explanation, unique notation, honest portrayal of our contributions, and the inclusion of discussions on algorithmic iterations and walltime.\n\n**Weaknesses**\n\nRelated Work Organization: We agree that some references in the related work section could be reorganized. We will revisit this section and ensure that the most relevant works are appropriately placed and discussed.\n\nLines 232, 238-244: We understand your concerns and will clarify our contributions and rephrase the complex sentence to enhance readability.\n\nTreatment of the Empirical Game: Your point about our phrasing of the empirical game as a restricted game is well-taken, and we will edit this description to avoid any confusion.\n\nBaselines in DO Variants: Thank you for this great suggestion. We have included additional experiments against fictitious team play [FCGS18]. As shown in the figure in our rebuttal pdf, our methods outperform fictitious team play. We believe that these additional experiments greatly improve the paper. \n\nEvaluation of PSRO Variants: We will work on providing more comprehensive evaluation details for the PSRO variants.\n\nApproximate Exploitability Curves: Our decision not to compute exploitability in Google Research Football (GRF) aligns with previous research, given the substantial computational resources required and the potential for high inaccuracy due to the environment's complexity and randomness.\n\n**Questions**\n\nConsideration of TMECor: When it comes to adversarial team games in which the players cannot secretly communicate, there are two main notions of equilibrium that are considered: TME and TMECor. TME corresponds to having the team members play independently, while TMECor allows for correlation between the team members. We believe there are several reasons why TMECor is the superior solution concept for the setting we consider. First, TMECor always guarantees a higher value for the team. Second, correlation between team members can be achieved easily, for example by communicating before the game starts, as in bridge. Finally, TMECor is known to be learnable, while TME is significantly harder, both in theory and in practice (for example [ZFS23] shows that TME is in a harder complexity class than TMECor). We discuss this in lines 164-170 but will include expanded discussion. We define TMECor in lines 128-132 (we will add a citation to the original paper too in the final version). \n\nStratego Paper and Pipeline PSRO: Sorry for the confusion. The Pipeline PSRO paper achieves state-of-the-art performance in Barrage Stratego. We will edit the paper to reflect this fact. \n\nTeam Games and Payoffs: Although different players can achieve different utility, the team utility is the sum of both players, so solving for TMECor can be viewed as a setting where both players have the same utility (the team utility). We will add discussion to make this more obvious.  \n\nNovelty of Algorithm Variants: We will clarify the specific novel changes in the algorithm variant and demonstrate the necessity and gains from these changes.\n\nInclusion of Baseline Methods: Regarding the suggestion of having each team player play the same policy: in fact, that is exactly what we do with MAPPO. Each team player has the same weights. But we don’t just have one policy, we have multiple in a population. We already include a self-play variant where there is just one policy, which I think is what is being referenced. As to including QMIX ablations, we believe that this is not the interesting aspect of our approach. There are multiple existing methods for cooperative deep RL, including MAPPO, QMIX, and many others. We run experiments with MAPPO because it has been shown to be the best-performing algorithm, but perhaps different cooperative RL algorithms would work better in different domains. However, we leave this ablation study to future work, as the main contribution of our paper is showing that cooperative RL can be combined with a PSRO-based method to find approximate TMECor.  \n\nConvergence: Actually we still have convergence to epsilon-TMECor if all best responses are epsilon-BRs. To see this, at convergence, we have that the best response cannot exploit the opponent meta-Nash more than epsilon over the existing meta-Nash for both teams, so by definition the meta-Nash is an epsilon-TMECor. We will make this point more clear in the paper and can add a brief proposition and proof if the reviewer would like. \n\nL305: The team members share parameters in the joint BR. So every strategy in Team PSRO will share parameters. But in Team PSRO-MM, the policy for each player can come from different iterations, which have different parameters. We will make sure this is clear in the revised version. \n\n**Conclusion**\n\nWe acknowledge your concerns and agree that our paper requires improvements. We believe that the planned revisions, as addressed above, will significantly enhance the quality of our work and respond to your critique. We hope that these clarifications and commitments to improvements might lead you to reconsider the rating.\n\n\n[FCGS18] Gabriele Farina, Andrea Celli, Nicola Gatti, and Tuomas Sandholm. \"Ex ante coordination and collusion in zero-sum multi-player extensive-form games.\" In: Advances in Neural Information Processing Systems (NeurIPS), 2018.\n\n[ZFS23] Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. \"Team Belief DAG: A Concise Representation for Team-Correlated Game-Theoretic Decision Making.\". In: International Conference In Machine Learning (ICML), 2023.\n\n[CG18] Celli, Andrea, and Nicola Gatti. \"Computational results for extensive-form adversarial team games.\" In: AAAI Conference on Artificial Intelligence (AAAI), 2018.\n"}]

Author rebuttal:
Details about these experiments have been included in individual responses. Full details will also be included in the camera-ready version.


Meta-review: This paper extends the PSRO algorithm to teams and provides some theoretical guarantees. The setting is such that members of a team cannot communicate with one another during the game. The reviewers' main concern was novelty, but the conversation in the rebuttal phase seems to have straightened that out.
Decision: Accept (poster)