A Meta-Game Evaluation Framework for Deep Multiagent Reinforcement Learning

1 Introduction

Evaluating complex AI algorithms requires careful attention to stochastic factors. Deep reinforcement learning (RL) algorithms in particular are subject to randomness within the algorithm and the operational environment, and variations with choices of hyperparameters and initial conditions. It is conventional to address these uncertainties in part by aggregating results across multiple runs [Bellemare et al., 2013]. Deep multiagent RL (MARL) algorithms present these issues, and additional challenges due to agent interactions. Evaluating performance against humans has been one source of compelling demonstrations [Silver et al., 2016; Vinyals et al., 2019; Perolat et al., 2022], but this approach is limited by the range of tasks for which human expertise exists, and the cost of engaging it when it is available. Generally speaking, we lack evaluation protocols for comparing different MARL methods in a statistically principled way.

In purely adversarial (i.e., two-player zero-sum) environments, distance to Nash equilibrium may be a sufficient metric [Brown et al., 2020; Schmid et al., 2023], as all equilibria are interchangeably optimal. More generally, where there are multiple equilibria or where we do not necessarily expect equilibrium behavior, the metrics for MARL performance may be less clear. In collaborative domains, global team return is the common objective [Foerster et al., 2018], however complex learning dynamics may lead agents using the same MARL algorithm to equilibria of distinct machine conventions in different runs [Hu et al., 2020].

We seek an approach to evaluating deep MARL in general-sum domains. We propose a meta-game evaluation framework (§5), which frames MARL algorithms as metastrategies: mapping games and random seeds to joint policies. We sample seed combinations to generate meta-game instances, from which we compute evaluation metrics of interest based on game-theoretic solution concepts. Through resampling and bootstrap techniques, we generate a statistical characterization of algorithm performance in these games. Our contributions:

• The meta-game evaluation framework.
• A new search algorithm for imperfect information games, Gumbel Information-Set Monte-Carlo Tree Search (§6), based on the recent development of Gumbel AlphaZero [Danihelka et al., 2022].
• Extensive experiments on state-of-the-art MARL algorithms (§7.2) on a class of negotiation games (§7.1), illustrating the framework and providing new evidence regarding the algorithms studied.

2 RelatedWork

While evaluating single-agent deep RL algorithms is wellstudied [Henderson et al., 2018; Agarwal et al., 2021], there are relatively few works that consider evaluation principles for deep MARL [Gronauer and Diepold, 2022]. Typically, agents are evaluated against a selected set of background opponents or emergent behaviors in certain contexts [Lowe et al., 2017; Leibo et al., 2021]. Other work has defined evaluation protocols for cooperative settings [Papoudakis et al., 2020; Gorsane et al., 2022], where a global team reward is well-defined. Our scenario falls into the agent-vs-agent category of Balduzzi et al. [2018], who argue for the necessity of comprehensively considering the possible joint interactions.

Kiekintveld and Wellman [2008] employed a concept of meta-games for evaluating general game-playing methods. In their setting, meta-strategies map normal-form game specifications to strategy choices. Treutlein et al. [2021] construct label-free coordination (LFC) games among instances of a cooperative MARL algorithm, in order to study zero-shot coordination [Hu et al., 2020]. LFC games are a kind of metagame in our sense, as they take dynamic game descriptions (Dec-POMDPs) as input.

Bootstrapping is a non-parametric statistical approach that constructs sampling distributions for any specified statistic by resampling from the original dataset [Davison and Hinkley, 1997]. Bootstrapping techniques have been applied in machine learning methods such as aggregating decision-tree models [Breiman, 1996]. Widenbeck et al. [2014] applied the bootstrap for statistical analysis of game-theoretic models estimated from simulations.

3 Game Theory Preliminaries

A normal-form representation of a game G consists of a player set N = {1, . . . ,N}, and for each player i ∈ N a pure strategy space Πi and a utility function ui : Π → R. Π = Π1 × · · · × ΠN is the joint pure strategy space. A mixed strategy σi ∈ ∆(Πi) for player i defines a probability distribution over that player's pure strategy space. Player i's payoff for choosing σi while others play σ-i = (σj)j̸=i is given by expectation over the respective mixtures: ui(σ) = Eπi∼σi ,π-i∼σ-i [u(πi, π-i)].

The regret of player i who plays σi when others are playing σ-i is REGRETi(σi, σ-i) = maxπ′i∈Πi ui(π′i , σ-i) - ui(σi, σ-i). A Nash equilibrium (NE) is a mixed strategy profile σ such that nobody has positive regret: ∀i. REGRETi(σi, σ-i) = 0. As a measure of approximation to NE, we define SUMREGRET(σ) = ∑i REGRETi(σi, σ-i).

If a game is known to be symmetric, we can reduce its normal-form description complexity. Formally, in a symmetric game, players share the same strategy space Π1 = · · · = ΠN = Π , and utility function u1 = · · · = uN = u. Furthermore, each player's utility is permutation-invariant to other players' strategies. For symmetric games we overload Π to refer to the common individual strategy space, rather than the joint space. In a symmetric profile, every player adopts the same (generally mixed) strategy. Solutions in symmetric profiles are guaranteed to exist in relevant settings [Nash, 1951; Cheng et al., 2004; Hefti, 2017], and are generally preferred absent any basis for breaking symmetry [Kreps, 1990].

Also given symmetry, let u(σ′ ,σ) be the expected payoff of a player when it chooses a strategy σ′ ∈ ∆(Π) while the other N - 1 play the same mixed strategy σ ∈ ∆(Π). We thus have REGRET(σ′ , σ) = maxπ′∈Π u(π′ , σ) - u(σ′ , σ). A symmetric NE strategy σ satisfies REGRET(σ, σ) = 0.

An extensive-form game (EFG) representation goes beyond normal form to include temporal and information structure. Effectively, an EFG defines a dynamical system (usually visualized by a tree) with a world state or history h that is not necessarily fully observable by every player. At each state h, starting with the initial state h0, there is a single player τ(h) ∈ N ∪ {c}, where c is the chance player, designated to select an action a ∈ A(h). The chance player chooses according to a fixed random policy. Player i ∈ N chooses according to its information state/set, si(h), which comprises the information that i has observed at h. Often si(h) is represented by a concatenation of public and private action-observation histories. Following action a, the world transits to h′ = ha until a terminal state z ∈ Z is reached. Then each player i ∈ N receives a utility ui(z) as a function of z. A behavioral strategy or policy, πi, of player i is a mapping from i's infostates to distributions over actions. For EFGs we overload Πi to refer to the set of behavioral strategies of player i. A joint behavioral strategy profile π thus induces a probability distribution over the terminal states and we define ui(π) as the expected payoff for player i under this distribution. In this paper, we consider EFGs with perfect recall, that is, information sets si(h) distinguish all actions i had taken to reach h. A consequence is that any mixed strategy σi ∈ ∆(Πi) is payoff-equivalent to some behavioral strategy πi ∈ Πi [Aumann, 1964].

4 Multiagent Training Algorithms

We define a multiagent training algorithm (MATA) M as a stochastic procedure that produces a policy profile π = M(G,Θ, ω) for an EFG. In general, the input EFG G cannot be tractably represented as an explicit game tree. Instead, we assume the game is given in the form of a black-box simulator that the algorithm can exercise by submitting actions and receiving observations and rewards. Θ is the set of hyperparameters of the algorithm, and ω is a random seed. If G is symmetric, then it is often natural to constrain the output π to be likewise symmetric (i.e., single policy to be played by all). More generally, π is a policy profile. For the AlphaZero MATA, for example, G could be represented by a Go simulator, and Θ would include the learning rate schedule and neural architecture. The output profile π specifies Go-playing policies for white and black, respectively.

A MATA is effectively a form of meta-strategy: a procedure that given a game G, generates a strategy profile for G. We can employ the MATA to play from the perspective of any particular player i, simply by selecting the ith element π(i) of the output profile.

A key issue for analysis of MATAs is uncertainty in strategy generation. It has been well observed (e.g., by Hu et al. [2020]) that a MATA with the same G and Θ but different ω may generate policies with vastly different strategic behaviors. For example, in a negotiation game, different runs of a MATA may lead to strategies that adopt distinct offering conventions. In the present work, we assume the hyperparameters Θm for each MATAMm have been fixed, so the uncertainty in behavior of a training algorithm is fully captured by the random seeds. Note that there is always discretion about what one considers a distinct MATAM versus a parametric variation, so it is possible to bring choice among hyperparameter settings within the scope of our analysis framework.

5 Meta-Game Evaluation Framework

Given M different MATAs {(M1 ,Θ1 ), . . . , (MM ,ΘM )} with associated hyperperameters, how can we evaluate their relative performance with respect to a given game G? Viewing the MATAs simply as game-solvers, we could focus on measures of their effectiveness in deriving a solution-for example, time and accuracy of convergence to Nash equilibrium. Viewing the MATAs' role as generating strategies to play a game, however, requires a different focus that considers the interaction with other strategy generators. This is particularly salient for games that have a multiplicity of solutions (the general case), or for which the operable solution concept may be open to question. Consequently, we propose to analyze competing MATAs by framing their interaction as itself a game. As MATAs are meta-strategies, we refer to this approach as a meta-game evaluation framework.

As noted above, we are particularly concerned with uncertainty in the results of multiagent training. In analysis of the MATA meta-game, therefore, we aim to characterize the implications of this uncertainty in probabilistic form.

5.1 Empirical Game-Theoretic Analysis

Our approach employs empirical game-theoretic analysis (EGTA), a methodology for reasoning about games through agent-based simulation [Wellman et al., 2024]. EGTA aligns with our assumption that the game of interest G is defined by a black-box simulator. In the typical framing, EGTA operates by estimating an empirical game model in normal form over an enumerated strategy set. The enumerated strategies are a small selection from the full strategy space of the extensive game represented by the simulator.

We employ EGTA with respect to an N-player game of interest G, and strategies defined by the output of MATAs. The meta-game is likewise over N players, and is symmetric regardless of whether G is symmetric or not. Let ˆπm denote the output from MATA m, for instance ˆπm = Mm(G,Θm, ω): the result from running the MATA on G for a particular random seed. We also allow that ˆπm be an aggregate of policy profiles from multiple random seeds. From these MATAgenerated profiles ˆΠ = {ˆπ1 , . . . , ˆπM }, we construct an empirical meta-gameMG( ˆΠ) over policy space ˆΠ as follows.

If the base game G is symmetric, then the ˆπm are singleplayer policies, and we estimate the meta-game utility function by the standard EGTA approach of simulating profiles over ˆΠ. If G is not symmetric, then each ˆπ ∈ ˆΠ is an N-player profile for G. Simulating a meta-game profile (ˆπ1, . . . , ˆπN) of these base-game profiles entails first assigning the ˆπ to players, according to a random permutation perm drawn uniformly from the N! possibilities. Then it simulates a play where player i of MG plays ˆπi(perm(i)) as if it is player perm(i) in G. This construction also corresponds to an EFG beginning with a root chance node that uniformly chooses among N! different outcomes, each followed by a copy of the original EFG with player indices permuted.

Symmetry of the meta-game reflects a view that, for multiagent training, developing effective strategies for each of the player positions is equally important. If this were not the case, or if one wished to perform an analysis of the differential effectiveness of various MATAs from the perspectives of different players or roles, a non-symmetric (or role-symmetric) meta-game model could be constructed instead.

5.2 Meta-Game Evaluation Procedure

Just as single-agent RL algorithms are statistically evaluated by return performance across different random seeds, we can analyze strategic properties among MATAs across different combinations of seeds. Let X denote statistics characterizing the strategic properties of interest (discussed below). Given an N-player game G and parametrized MATAs {(M1 ,Θ1 ), . . . , (MM ,ΘM )}, our evaluation procedure comprises the following steps:

1. Select a finite set of seeds Ωm for each MATAm. Generate ˆπm(ω) = Mm(G, Θm, ω) for each ω ∈ Ωm.
2. For each m, uniformly sample |Ωm| seeds from Ωm with replacement, yielding the sequence (ω1, . . . , ω|Ωm|). Let ˆπm be a profile that that is payoff-equivalent to a uniform mixture over the multiset {ˆπm(ω1), . . . , ˆπm(ω|Ωm|)}.
3. Given ˆΠ = {ˆπ1 , . . . , ˆπM }, estimate the symmetric empirical meta-game MG( ˆΠ ) as described in §5.1.
4. Compute the statistics-of-interest X fromMG( ˆΠ)
5. Repeat Steps 2 through 4. Estimated profile payoffs should be memoized for reuse across iterations. Obtain an empirical distribution of X and report statistical properties of X.

One way to understand this evaluation procedure is to view each MATA as a mixed strategy, selecting policies uniformly over the possible random seeds. The "ground-truth" metagame represents an expectation over the results of this randomization. The empirical meta-game estimates this from finite samples Ωm. By resampling from these seeds at hand, Step 2 constructs multiple empirical games among MATAs, from which we construct sampling distributions over X using bootstrapping.

There are a variety of choices for statistics X to gather. The only requirement is that X can be computed from the information in a normal-form game model. For example, one possible metric on MATA performance is uniformscore: average payoff against a uniform distribution over other MATAs. Such scores have been employed in a variety of contexts, however putting equal weight on the possible counterparts is questionable, as they are not equally relevant [Balduzzi et al., 2018].

An alternative proposed by Jordan et al. [2007] is NEregret: REGRET(π, σ∗ ), where σ∗ is a symmetric mixed equilibrium of MG( ˆΠ). The motivation for this measure is that it focuses on behavior against rational opponents. Performance against obviously flawed opponents should carry much less weight, as they are less likely to be encountered in practice, all else equal. 1 For games with multiple equilibria, however, NE-regret is sensitive to the choice of solutions σ∗ . This sensitivity is inherent to situations with multiple equilibria, but it can still be helpful to adopt a focal equilibrium to reduce ambiguity in analysis. Balduzzi et al. [2018] proposed Nash averaging, which is essentially NE-regret with respect to the max-entropy equilibrium. The intuition for preferring to evaluate with respect to higher-entropy solutions is that they reflect diversity, and thus reward robustness to a wide range of rational opponents.

1 If however there is some basis to expect opponents who are flawed or boundedly rational in some particular way, then by all means it would make sense to measure regret with respect to a solution concept capturing that basis.

5.3 Max-Entropy Nash Equilibrium

Computing max-entropy NE is hard in general, but practically feasible to approximate for bi-matrix games of modest size. We adapt the mixed-integer programming formulation of Sandholm et al. [2005]:

with real variables σ∗ (π), uπ, binary variables bπ for each strategy π, and an equilibrium payoff real variable u∗ . U is the maximum difference across payoffs. The variables bπ indicate whether strategy π is outside the equilibrium support. That is, bπ = 1 iff σ∗ (π) = 0. Otherwise uπ = u∗ : strategies in the support have the same payoff. The details of our implementation are in App. A. 2

Although max-entropy NE is not generally unique, it narrows the possibilities considerably compared to unconstrained (approximate or exact) NE.

6 Search as aMeta-Strategy Operator

Many MATAs produce a policy network p that maps directly from an infostate to a distribution over actions in a forward pass for every player. Recent work has found that leveraging computation at run-time and adding search to p can improve performance in large EFG domains [Silver et al., 2018; Brown et al., 2020; Schmid et al., 2023]. As a case study for our meta-game evaluation framework, we apply it to investigate the effect of search as a general policy improver.

Toward that end, we propose a heuristic search method for large EFGs based on information-set MCTS (IS-MCTS) [Cowling et al., 2012] and Gumbel AlphaZero [Danihelka et al., 2022]. Alg. 1 presents the procedure, Gumbel IS-MCTS, in detail. Parameterized by a policy net p and a value net v, Gumbel IS-MCTS conducts multiple passes over the gametree guided by v and p at an input infostate s, and outputs an action a for decision-making. We can apply this procedure to a variety of underlying MATAs, as a meta-strategy operator: transformingM toM′ (with additional hyperparameters like simulation budget). The meta-strategyM′ in effect

2 Appendices can be found in an arxiv version of this paper [Li and Wellman, 2024].

Algorithm 1 Gumbel IS-MCTS

1: function Gumbel-Search(s, v, p) 2: ∀(s, a). R(s, a) ← 0,C(s, a) ← 0 3: ∀a ∈ A(s). sample g(a) ∼ Gumbel(0), ˆ A ← A(s) 4: repeat 5: Sample a world state: h ∼ Pr(h | s, p) 6: while do 7: if h is terminal then 8: r ← payoffs of players Break 9: else if i ≜ τ(h) is chance then 10: a ← sample according to chance 11: else if si(h) not in search tree then 12: Add si(h) to search tree 13: r ← v(si(h)). Break 14: else if si(h) is root node s then 15: a, ˆ A ← one step of sequential halving (Alg. 3) based on GS(s, a) and remaining actions in ˆ A 16: else 17: Select a according to (3) in App. B.2. 18: end if 19: h ← ha 20: end while 21: for (si, a) in this trajectory do 22: Increment R(si, a) by ri, C(si, a) by 1. 23: end for 24: until num sim simulations done 25: return Action a that remains in ˆ A 26: end function

adds run-time search to the output policy p of M. Unlike AlphaZero-which uses the same MCTS method for training and run-time, with meta-strategy operators we can explore a variety of MATAs as training-time methods which produce v and p for search at test-time [Sokota et al., 2024] (details in §7.2).

Just like MCTS, IS-MCTS incrementally builds and traverses a search tree and aggregates statistics such as visit counts C(s, a) and aggregated values R(s, a) for visited (s, a) pairs. During each simulation of the search (line 5), a world state is sampled from a posterior belief Pr(h | s, p) assuming the opponents played according to p prior to s. In our test domains, Pr(h | s, p) can be computed exactly via Bayes's rule, where in larger domains, using particle filtering [Silver and Veness, 2010] or deep generative models [Hu et al., 2021; Li et al., 2023] to approximate Pr(h | s, p) are possible. Further technical details are provided in App. B.

The key feature of Gumbel IS-MCTS is how it selects actions at the search nodes. At the beginning of the search (line 3), a Gumbel random variable, g(a), is sampled i.i.d. for each legal action a of the root, for later use in action selection. At the root (line 15), the algorithm treats each legal action as an arm of a stochastic bandit, and uses a sequentialhalving algorithm [Pepels et al., 2014] (Alg. 3) to distribute the simulation budget. Sequential-halving algorithms usually are designed for minimizing the simple regret [Bubeck et al., 2009], which is the regret at the last-iteration action recommendation. By contrast, UCB-style algorithms are usually designed for minimizing the accumulated regret during an online learning process. For a game-playing search algorithm, minimizing simple regret makes more sense in terms of producing a single optimal action at a decision point.

We assign to each arm a a Gumbel score GS(s, a) = g(a) + logit p(s, a) + G(ˆ q(s, a)). The second term is the logit of a produced by p, and the third term is a monotone transformation of the action value ˆ q(s, a), which is estimated by R(s, a), C(s, a), and v. The intuition is that a high ˆ q(s, a) value indicates a direction for policy improvement. Indeed, the improved policy Imp(p)(s, a) ≜ SoftMax(logit p(s, a)+ G(ˆ q(s, a))) provably achieves higher expected values [Danihelka et al., 2022, App. B]. The forms of G and ˆ q are detailed in App. B.1.

Adding Gumbel noise g(a) implements the "Gumbel topK-trick": deterministically selecting the top K actions according to GS(s, a) is equivalent to sampling K actions from Imp(p)(s, a) without replacement [Huijben et al., 2022]. The Gumbel score induces a low-variance non-deterministic action selection of the root node during the sequential halving process, which encourages exploration while distributing the simulation budget toward actions likely to yield higher expected values.

At a non-root node (line 17), an action is selected to minimize the discrepancy between Imp(p) and the produced visited frequency (details in App. B.2). At the end of the search, Gumbel IS-MCTS outputs the action a that survives the sequential halving procedure.

7 Evaluation Study

7.1 Domain: Alternating Negotiation

We test our MATAs and evaluation framework in the context of a two-player negotiation game. The particular version we study, called "Deal-or-No-Deal" (DoND) by Lewis et al. [2017], is a family of two-player negotiation games where the players alternate proposals to divide a pool of resources: three different goods available in various amounts. At the start of the game, quantities of goods in the pool and players' private valuations for units of each good are sampled from a known distribution. The valuation distribution is constrained to fix a constant value for both players of the aggregate pool: c · w1 = c · w2 = 10. For example, in Fig. 1, the pool of goods can be represented as c = [1, 2, 3]. The negotiation proceeds through alternating proposals for dividing the resources. In this example, player 1 first proposes o1 = [1, 2, 0] for itself which entails o2 = c - o1 = [0, 0, 3] for player 2. Player 2 rejects and proposes a counter-offer, to which 1 may either agree or continue bargaining. For a particular game parametrization Barg(T, ε, γ), the game ends if either (1) a deal is made, (2) a maximum number of rounds T is reached, or (3) chance decides to terminate the game, which happens at every round with probability ε. If an agreement (o1, o2) was reached at the tth round, player i receives payoff γ twi · oi. Otherwise both players receive zero payoff.

DoND is a family of challenging general-sum environments with imperfect information. Players have a common interest in reaching a deal (and quickly, for γ < 1), and the different ways of dividing the pool have different total value. In our studies, we sample configurations uniformly from a database of 6796 published byLewis et al. [2017]. This leads to prohibitive complexity: a game with T = 10 has O(1011 ) infosets for every player, which is intractable for enumeration (detailed in App. G), and grows exponentially with T .

7.2 Benchmark Algorithms

Our meta-game evaluation considers the following M = 17 MATAs. These algorithms represent a comprehensive set of state-of-the-art MARL algorithms, including methods using self-play based training, population based training, and model-free and model-based approaches. Details are below and in App. D.

Independent/Multiagent PPO (IDPPO/MAPPO)

Both IDPPO and MAPPO train policy and value nets using self-play trajectories by minimizing the trust-region clipped loss [Schulman et al., 2017]. Value nets are trained by minimizing L2 loss from the targets produced by GAEs. In IDPPO each player maintains its own policy and value nets whereas in MAPPO [Yu et al., 2022] players share the same neural nets.

Regularized Nash Dynamics (R-NaD) and NFSP

Both R-NaD [Perolat et al., 2021] and Neural Fictitious SelfPlay (NFSP) [Heinrich and Silver, 2016] are self-play modelfree MARL algorithms originally designed for purely adversarial settings. R-NaD has recently shown success in producing human-level agents in Stratego [Perolat et al., 2022], where it iteratively trains policy nets by minimizing NeuRD loss [Hennes et al., 2020] and value nets using the V-Trace estimator [Espeholt et al., 2018] on a sequence of regularized games. NFSP mimics the classic fictitious play algorithm [Heinrich and Silver, 2016] by alternating between training a supervised learning net that summarizes historical plays and training a DQN policy that serves as a best response.

Policy Space Response Oracles (PSRO) and FCP

PSRO [Lanctot et al., 2017] and Fictitious Co-Play (FCP) [Strouse et al., 2021] are two population-based MARL algorithms. PSRO is an EGTA method that iteratively adds policies that are best responses to the current solution. We use max-entropy Nash as the solution concept (solving an asymmetric version of (1)), and PPO as the best-response method. We consider two ways of extracting the final agents: (i) PSRO: using the final-iteration solution and (ii) PSROLAST: using the final-iteration best-response policies. FCP has notably demonstrated success in collaborating with humans from scratch [Strouse et al., 2021]. FCP builds a population by picking policies of different skill levels on multiple self-play runs, and trains final best responses against such populations. Our implementation of FCP uses IDPPO to generate self-play runs, picks the agents based on social welfare, and uses PPO as the best-response method.

Gumbel Search and Vanilla AlphaZero-style Search

We include the following variants of Gumbel IS-MCTS: (i) G-Search: Using Gumbel IS-MCTS for both training the networks (Alg. 4) at training time and conducting search at test time. (ii) G-Search-PN: Using search at training time, but only policy net without search at test time. (iii) GSearch-IDPPO: Using IDPPO to train the policy and value nets, based on which Gumbel IS-MCTS executes test-time search. (iv) G-Search-MAPPO and (v) G-Search-R-NaD are similarly defined. In addition, we implement an extension of the original AlphaZero-style MCTS to IS-MCTS. The differences between this search method (Alg. 2 in App. C) and Gumbel IS-MCTS are in the mechanisms for exploration (e.g., Dirichlet noise) and action selection (e.g., PUCT) within the search tree. We include (vi) VA-Search: Using this search for both training time and test time, and (vii) VASearch-PN: similarly defined as (ii).

Heuristic Strategies

We further include the following baseline bargaining strategies: (i) Uniform, which uniformly samples among all legal actions at each decision point. (ii) Tough, which never agrees, and always proposes uniformly among offers that maximize its own payoff. (iii) Soft, which always agrees, or uniformly proposes among all offers if it is the first-mover.

7.3 Experimental Setup

All methods are implemented within the programming model of OpenSpiel [Lanctot et al., 2019]. Each MATA that involves neural training uses models of approximately equal size (e.g., number of layers, hidden nodes). The neural net inputs are likewise the same across all MATAs, and include complete history information (i.e., losslessly represent infosets) for the DoND game. For procedures that involve selfplay or RL training we employ roughly the same number of training trajectories. For all search methods we use 200 simulations per call. We fine-tuned the learning rates based on SUMREGRET performance. Most of the MATAs reliably produce approximate equilibria. Details are in App. E.

We set |Ωm| = 10, m ∈ {1, . . . ,M}. To simplify the evaluation procedure, we pre-compute an empirical payoff matrix covering every policy pair: (ˆπm 1 (ω), ˆπm′ 2 (ω′ )), for m,m′ ∈ {1, . . . ,M}, ω and ω′ among the seeds sampled for Mm and Mm′ , respectively. For each payoff entry we run 2 × 104 simulations to compute the expected payoff. We then sample and analyze 106 M × M empirical meta-games from this matrix, per Steps 2-4 of §5.2, to obtain distributions over the statistics of interest.

7.4 Results

We test all 17 MATAs on two DoND instances: Barg(10, 0, 1) and Barg(30, 0.125, 0.935). The two settings are qualitatively different. The latter includes discounting and per-round ending probability, incentivizing the players to find and agree on a good deal in early rounds. Without these factors, the first game reduces to an ultimatum-game-like environment. Meta-game statistics are reported in Tables 1 and 2.

In addition to NE-Regret and uniform scores, we also report a statistic we term the NE-Nash-Bargaining-Score (NENBS). The NE-NBS for MATA m in an empirical game is defined as the utility-product between πm and an opponent strategy σ∗ : u(πm,σ∗ ) · u(σ∗ ,πm). Here σ∗ is a maxentropy Nash computed by (1). This statistic is intended to measure the effectiveness of an agent in achieving high social welfare and fairness with a rational opponent.

From the tables we can see that while there is positive correlation between NE-Regret Scores and Uniform Scores, NE-Regret Scores are better at identifying the most robust MATAs: the rankings of the top four MATAs in NE-regret scores are the same for both environments, and from the empirical distribution plots in App. F we can see G-Search-RNaD and G-Search consistently produce strategies that are selected in a max-entropy equilibrium support with high probability. By contrast uniform-score comparisons can be distorted by non-salient success against weak strategies. It is also interesting to note positive correlation between NERegret and NE-NBS. This reflects the non-zero-sum nature of these environments.

The performance of search-based agents is especially noteworthy. Three of the top four MATAs employ search at test time. All search methods are stronger than their policy net counterparts, confirming that IS-MCTS is a policy-improver in imperfect information games. We hypothesize that this is because a search-based algorithm is usually a better responder to its policy network counterpart, while both behave strategically similarly against other methods. The relative strength among search-based algorithms mirrors that of their policy-net counterparts. In both environments, G-Search and VA-Search are among the top four. This suggests that using search at training time is compatible with the same search at test time, and produces better policy and value nets compared with other methods.

We notice some algorithms behave qualitatively differently in these two environments. We found FCP consistently produces collaborative strategies with rather high agreement probability. This may explain its better performance in the second environment, which encourages settling a deal in early rounds. Likewise, Soft achieves higher individual scores and NE-NBS in the second environment. By contrast, while Tough achieves better individual performance than Soft in the ultimatum game, it is still worse than all learning methods, as shown by its terrible NE-NBS values for both environments.

Another interesting view is provided by best-response graphs. In a best-response graph for a game instance, strategies are vertices, and there is a directed edge (m1 →m2) iff m2 = argmaxm′ u(πm′ ,πm1 ). We generate an aggregate graph for a MATA meta-game by recording the frequency of such edges in the sampled empirical games. These are shown for the two game settings in Fig. 2. The correspondences between the vertex labels and MATAs can be found in the "Label" column of the tables.

The empirical best-response graphs support several observations. First, many MATA vertices such as IDPPO(label 6) and MAPPO(7) have self-edges with non-negligible frequencies. This is consistent with previous observations that selfplay MARL algorithms are likely to produce agents that overfit to themselves [Hu et al., 2020]. However, self-edges do not necessarily suggest poor generalization performances. For example, G-Search-NaD(5) has a self-edge with a high probability in both environments, but still performs the best. Selfedges persist even after applying search as policy-improver at test time. For example, there are self-edges for G-SearchIDPPO(2) and G-Search-MAPPO(3). This may suggest that there are certain strategic correlations between a search agent and its policy net counterpart. Interestingly, we also observe certain self-edge probabilities for PSRO(9) and PSROLAST(10), which are normally regarded as population-based training methods. It could be that the equilibria selected at each iteration introduce correlations between different players. By contrast, NFSP(8) and FCP(0) are two MATAs without strong self-edges; both use a uniform distribution for opponent modeling, which may reduce the correlation between player positions.

Edges across MATAs illuminate strategic interaction structure. Tough(13) is unsurprisingly the best response to Soft(12). G-Search-NaD(5) is a strong attractor in both graphs, as G-Search(1) is in the first. Sometimes a searchbased MATA is a best response to its policy-net counterpart, as illustrated by R-NaD(11) to G-Search-R-NaD(5), and VASearch-PN(16) to VA-Search(15). This could also explain why MATAs such as G-Search-PN(4) and VA-Search-PN(16) do not have apparent self-edges.

8 Conclusion

We propose a meta-game evaluation framework for MARL in general-sum environments. Our approach is analogous to the evaluation process for single-agent RL, effectively aggregating the strategic analysis procedures across possible worlds defined by different seed combinations. We illustrated the method by constructing a meta-game model over a comprehensive set of multiagent training algorithms using deep RL on a class of negotiation games. The meta-game analysis evaluated the algorithms in multiple ways, most prominently through max entropy NE-regret ranking and the structure of best-response graphs. Bootstrap statistics provide a basis for assessing uncertainty in evaluation results.

Experimental results support several interesting observations about Gumbel IS-MCTS as a meta-strategy operator, especially regarding the value of search at both training time and test time, and on patterns of strategic interactions among the algorithms.

A key feature of our evaluation framework is the flexibility to investigate a variety of statistics of interest through a carefully structured process. Future work will focus on understanding the robustness of alternative measures that can be employed for algorithm assessment through meta-games, and developing effective tools for statistical analysis.

Acknowledgments

This work was supported in part by funding from the US Army Research Office (MURI grant W911NF-18-1-0208), and a grant from Open Philanthropy.