Neural Auto-Curricula in Two-Player Zero-Sum Games
Authors: Xidong Feng
Oliver Slumbers
Ziyu Wan
Bo Liu
Stephen Marcus McAleer
Ying Wen
Jun Wang
Yaodong Yang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-agent
Meta-Learning
Auto-Curricula

Abstract: When solving two-player zero-sum games, multi-agent reinforcement learning (MARL) algorithms often create populations of agents where, at each iteration, a new agent is discovered as the best response to a mixture over the opponent population. Within such a process, the update rules of "who to compete with" (i.e., the opponent mixture) and "how to beat them" (i.e., finding best responses) are underpinned by manually developed game theoretical principles such as fictitious play and Double Oracle. In this paper, we introduce a novel framework—Neural Auto-Curricula (NAC)—that leverages meta-gradient descent to automate the discovery of the learning update rule without explicit human design. Specifically, we parameterise the opponent selection module by neural networks and the best-response module by optimisation subroutines, and update their parameters solely via interaction with the game engine, where both players aim to minimise their exploitability. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive or even better performance with the state-of-the-art population-based game solvers (e.g., PSRO) on Games of Skill, differentiable Lotto, non-transitive Mixture Games, Iterated Matching Pennies, and Kuhn Poker. Additionally, we show that NAC is able to generalise from small games to large games, for example training on Kuhn Poker and outperforming PSRO on Leduc Poker. Our work inspires a promising future direction to discover general MARL algorithms solely from data.

Neural Auto-Curricula
Xidong Feng".', Oliver Slumbers* Ziyu Wan', Bo Liu", Stephen McAleer ', Ying Wen', Jun Wang', Yaodong Yang University College London, 2Shanghai Jiao Tong University, Instittte of Automation, CAS, 'University of California, Irvine, Instittte for AI, Peking University
Abstract
When solving two-player zero-sum games, multi-agent reinforcement learning (MARL) algorithms often create populations of agents where, at each iteration, new agent is discovered as the best response population. Within such process. the update rules of "who to compete with" (i.c., the opponent mixture) and "how to beat them" " (i.e., finding best responses) are underpinned by manually developed game thcoretical principles such as fictitious play and Double Oracle. In this paper', we introduce novel framework- Auto-Curricula (NAC) that leverages meta- veeta-graiiett descent to automate the discovery of the learning update rule without explicit human design. Specifically, we parameterise the opponent selection module by neural networks and the best- response module by optimisation subroutines, and update their parameters solely via interaction with the game engine, where both players aim to minimise their exploitability. Surprisingly, even without human design, the discovered MARL algorithms achieve competitive even better performance with the state-of-the the-art population- game solvers (c.g.. PSRO) on Games Skill, differentiable Lotto, non-transitive Mixture Games, Iterated Matching Pennies, and Kuhn Poker. Additionally, we show that NAC is able to generalise from small games to large games, for example training Kuhn Poker and outperforming PSRO on Leduc Poker. Our work inspires a promising future direction to discover general MARL algorithms solely from data.
mixture over the opponent
Introduction
Two-player zero-sum games have been a central interest of the recent development of multi-agent reinforcement learning (MARL) [60, 2, 53]. In solving such games, MARI. agent has clear objective: to minimise the worst case performance, its exploitability, against any potential oppo- nents. When both agents achieve zero exploitability, they reach Nash equilibrium (NE) [36], a classical solution concept from Game Theory [34, 10]. Even though this objective is straightforward, developing effective algorithms to optimise such an objective often requires tremendous human efforts. One effective approach is through iterative methods, where players iteratively expand population of agents (a.k.a auto-curricula [26]) where at each iteration, a new agent is trained and added to the player's 's strategy pool. However, within the auto-curricule process, it is often non-trivial to design effective update rules of "who to compete with" (i.e., opponent selections) and "how to bear them" (i.e., finding best responses). The problem becomes more challenging when considers additional requirements such as generating agents that have behavioural diversity [58, 37, 3, 28) or generalisation ability [47, 38).
''Euull contributions. 'Corresponding syaodong.yang@pku.cccu.. Code relcased https:// gi github. /o/.ub.cco//aateetoreee//aA
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

One effective approach to designing auto-curricue curricula is to follow game theoretical principles such as fictitious play [5] and Double Oracle (DO) methods [33, 11]. For example, in the DO dynamics, each player starts from playing sub-game of the original game where only a restricted set of strategies are available; then, at each iteration, each player will add a best-response strategy, by training against a NE mixture of opponent models at the current sub-game, into its strategy pool. When an exact best response is hard to compute, approximation methods such as reinforcement learning (RL) methods are often applied [25]. One of the potential downsides of this approach is, under approximate best response methods, one no longer maintains the theoretical properties of DO and a worthwhile avenue of exploration is to find auto-curricula that are more conducive to these approximation solutions.
Apart from following game theoretical principles, an appealing alternative approach one can consider is to automatically discover auto-curricull from data generated by playing games, which can be formulated as a meta-learning problem [13]. However, remains an open challenge whether is feasible to discover fundamental concepts (e.g.. NE) entirely based on data. If we can show that it possible to discover fundamental concepts from scratch, it opens the avenue to trying to discover fundamentally new concepts at a potentially rapid pace. Although encouraging results have been reported in single-agent RL settings showing that it is possible to meta-learn RL update rules, such as temporal difference learning [38, 56, 57J, and the learned update rules can generalise to unseen tasks, we believe discovering auto-curricula in multi-agen cases is particularly hard. Two reasons for this are that the discovered auto-curti cuttoocurriulum itself directly affects the development of the agent population, and each agent involves an entire training process, which complicates the meta-learning process.
Albeit challenging, we believe method capable of discovering auto-curricula without explicit game theoretic knowledge can potentially open up entirely new approaches to MARL. As a result, this paper initiates the study on discovering general general-purpose purposs MARL algorithms in two-player zero-sum games. Specifically, our goal is to develop an algorithm that learns its own objective (i.e., the auto-curricula) solely from environment interaction, and we offer meta-learning framework that achieves such a goal. Our solution framework - Neurul Curriicuruu (NAC) - has two promising properties. Firstly, it does not rely on human-designed knowledge about game theoretic principles, but instead lets the meta-learner decide what the meta-solution concept (i.e., who to compete with) should be during training. This property means that our meta-learner shares the ability of game theoretic principles in being able to accurately evaluate the policies in the population. Secondly, by taking the best-response computation into consideration, NAC can end to end offer more suitable auto-curricula within the approximate best-response scenario compared with previous approaches; this is particularly important since an exact best-response oracle is not always available in practice.
Our empirical results show that NAC can discover meaningful solution concepts alike NE, and based on that build effective auto-curricula in training agent populations. In multiple different environments, the discovered auto-curriculum achieves the same performance or better than that of PSRO methods [25, 3]. We additionally evaluate the ability of our discovered meta-solvers to generalise to unseen games of a similar type (c.g.. training on Kuhn Poker and testing on Ledue Poker), and show that the auto-curricula found on a simple environment is able to generalise to a more difficult one. To the best of our knowledge, this is the first work that demonstrates the possibility of discovering an entire auto-curriculum in solving two-player zero-sum games, and that the rule discovered from simple domains can be competitive with human desannde algorithms on challenging benchmarks.
2 Related Work
Whilst it is theoretically possible to solve for NE in two-player zero-sum games via linear program- ming (L.P) [34] in polynomial time [51], this is strictly limited approach. For example, when the action space become prohibitively large, or continuous, using LP becomes intractable; other approximation methods such as fictitious play (FP) [5], DO [33, 11] or PSRO [25, 32, 31] methods are required. These methods all follow iterative best-response dynamics where at each iteration, a best response policy is found against a previous aggregated policy (e.g.. DO/PSRO applies sub-game NE, FP applies time-average strategy). Under this general iterative framework, other solution concepts include Rectified NE [3], a Rank [35, 59] or no-regret algorithms [11]. In this paper, instead of following any existing game theoretic knowledge, we try to discover effective solution concepts solely through environment interactions via meta-learning techniques.
Meta-learning, also known as learning to learn, has recently gained increased attention for successfully improving sample efficiency in regression, classification and RL tasks. MAML [13] meta-learns

---

Game Environment G ~ P(G)
Forward Pass
Back-prop Gradients
Section
M
Crp TTy 1
Section 3.1
9, Pp
Section
(Neural) Meta-Solver fa(M.)
Best Response Oracle
MAN 9R
(p.
Seection 3--2
Seection 3.3
Figure 1: NAC. The top box illustrates the training process where we iteratively expand M, with best responses to fo (,,), and then calculate the exploitability (in red). The bottom box illustrates expanding the population by finding &BR The blue arrows show how the gradients pass backwards,
from the exploitability through the best-response trajectories. The gradient paths [1], [2] refer the two gradient terms in Eq. (8) and the gradient paths [3]. [4] refer to the two gradient paths in Eq. (7).
model parameters by differentiaaing the learning process for fast adaptation on unseen tasks. PROMP [42] theoretically analyses the MAML-RL formulation and addresses the biased meta-gradient issue. ES-MAMI. [48] bypasses the Hessian estimation problem by leveraging evolutionary strategies for gradient-free optimisation. RL [12] and L2RL [54] formulate the meta-learning problem as a second RL procedure but update the parameters a "slow" pace. Recently, there a trend to meta-learn the algorithmic components of RL algorithms, such as the discount factor [57]. intrinsic rewards [65, 64), auxiliary tasks [52, 66], objective functions for value/policy networks [4. 56, 22], off-policy update targets [62], and the bootstrapping mechanism [38]. Their success is built on the melu- meel--gaddeent technique, which leverages gradient descent on the sequence of gradient descent updates resulting from the choice of objective function. The meta-learned RL algorithms demonstrate promising generalisation capability in solving different tasks. Apart from meta mecta-gradients, evolutionary strategies (ES) have also been successfully applied [20]. Our paper, in comparison, has parallel goal to these prior arts: to discover MARL algorithms that are effective for solving various two-player zero-sum games, and to demonstrate their generalisation ability across different games.
So far, there have been very few attempts to conduct meta-learning in multi-agent settings [60]. MNMPG [46] applied meta-gradients for training credit assignment modules for better decomposing the value network [49, 61]. Meta-PG [1] was proposed as a meta-gradient solution to continuous adaptations for non-stationary environments. Building
the opponent modelling technique called LOLA [15, 14]. Mcta-MAPG [21] extends Meta-PG [i] to multi-agent settings by considering both the non-stationarity from the environment and from the opponent's 's learning process. Our work rather focuses on automatically discovering multi-agent auto-curricula through meta-learning, without explicit game theoretic knowledge, that leads general MARL algorithms for solving two-player zero-sum games.
3 Multi-Agent Meta-Learning Framework
In this section, we discuss our meta-learning framework NAC for discovering multi-agent auto- curricula in two-player zero-sum games. We follow the road-map set out by Fig. (1) which illustrates the flow of NAC. The relevant sections for each part of Fig. (1) are marked in pink.
3.1 The Meta-game
Consider two-player zero-sum games G2 drawn from some distribution P(G), where players have the state-action space S A. We start by introducing the notion of agent who is characterised by a policy Φ, where policy is a mapping Φ S x A + [0, 1] which can be described in both a tabular form or as neural network. The payoff between two agents defined to be M ( Φ (i.e., the game engine), and represents the utility to agent i, or alternatively, the negative utility to agent j.
Our population based framework revolves around iterative updates on the meta- game M. every
iteration E T, a Player is defined by a population of fixed agents 4; = Do U { ( ΦBRR ,..., BBR where Po is the initial random agent pool and the dBR are discussed further in Sec. (3.3). From here,
G encapsulates all of the information for Player take part in game (e.g., actions, reward functions).
3

---

for the sake of notation convenience, we will only consider the share the same p,. As such. the single population will generate a meta-game M., a payoff matrix between all of the agents in the population, with individual entries being (2;; Qz) Vos 6j E +,,
case where Players
3.2 The Meta-Solver
Based on M, the Player will solve for the meta-distribution गं, which is defined as an aggregated agent over the fixed agents in Φ.. These meta-solvers in recent work have stuck to ouman-designe
solution concepts such as a uniform distribution [25] or NE and its variants [3. 37, 28), whereas we introduce method to actively learn these distributions through solely interacting with the game. Specifically, we parameterise our meta-solver via neural network. This network so with parameters O is mapping fe M, + [0, 1J' which takes as input a meta-game M, and outputs meta-distribution TT = (M,). The output ,, a probability assignment to each agent in the population o, and, as we are in the single-opulation setting, we do not distinguish between different populations.
There are two characteristics that our network fo should have: firstly, should be able handle variable-length inputs as the size of M, is (t x t), and fe outputs a vector of size (t x 1), where the value of increments at every iteration. Secondly, fe should have both column-pernnutation invariance and row-permutation equivariance. Given an input M,, So will output the distribution T, = fo M,) for the row Player and it should be equivariant to any permutation of the row index, and be invariant to any permutation of the column index as neither of these actions should affect Te
Much work has been done on how maintain permutation invariance/equivariann networks such as Deepsets [63] for handling tasks defined on sets, or PointNet [39] for handling 3D point cloud data processing. Our first Multi-Layer Perceptron (MLP) based network is inspired by PointNet, which consists of three components: (1) An MLP over each element M for non-linear representation, (2) Column Mean-Poolin which will be concatenated to each row and (3) Row-wise MLP for the row- now-permutation equivariant meta distribution. We also offer two alternatives, inspired by fully Conv Id-based model [29] and GRU-based model [7]. We refer to Appendix for detailed architectures of our network f.(-).
for neural
for
invariant information aggregation,
3.3 Best Response Oracle
Once a meta-distribution π. E A +,_1/ is obtained, the goal is to solve for a best-response against TT to strengthen the population. Formally, we define
MiΦ (m,, 2.))
n M(, (.),,
(I)
to represent the payoff for agent & against the aggregated agent (aggregated by тt) of population + Consequently, we have that the best-response to an aggregated strategy is:
BR 141
arg
म. M2 db),
and the best-response appended to the population to form new fixed population, aiming to strengthen the population so as to become less exploitable. Depending on the sophistication of games, one may choose appropriate oracles. We consider different oracle implementations in Sec. (3.5).
3.4 The Learning Objective of Players
The goal of NAC is to find an auto-curricula that after T hest-response iterations returns a meta- strategy and population, (TT, p that helps minimise the exploitability, written as:
min Exp म. (0), 2 (0)), where Epp := max 21 (Ø, (TT, &r)),
(3)
+ πイ fo (M,). Φr 10 BR (0), 8 (0),
BR (0)
(4)
Crp(.) represents exploitability [9], measure of the incentive to deviate from the meta-strategy over TT,, Tr). When exploitability reaches zero, it means one can no longer improve performance.
RBR (0) in Eq. (4) shows that each best-response has dependency on 0 since &BR is influenced
'In the poluliiooolltion case, Eyp expresses the notion of each Player having a different population and final meta-strategy, in the
case only need to evaluate the deviation incentive for population.

---

explicitly by the curriculum at iteration and implicitly by all previous curricula. We believe such an objective maximises the generality of our framework on solving different types of zero-sum games.
NAC can use any oracle, however different considerations must be taken dependent on the choice. In the following sections will discuss the technicality of directly solving for the meta-gradients of with respect to gradient-descent (GD) oracle and an RL-based oracle. Additionally, we will provide an oracle-agnostic method based on zero-order gradients that allows us to ignore oracle trajectories via Evolutionary Strategies [43]. Pseudo-code' for these methods is shown in Alg, (I).
Algorithm Neural Auto- Auto-Curricule (NAC) statements in teal refer only to ES-NAC, statements in red only standard NAC.
Require: Game distribution p(G), learning rate a, time window T, perturbations n, precision a.
1: Randomly initialise policy pool Φo. Initialise parameters 0 of the meta solver fe-
2: for each training iteration
3: Store current model fe.
4: Sample ..,, en ~ (O, 7) and store n models ((0+e))- If using ES, include this step
5: for each stored model f do
6:
Sample games [G [= from p(G).
7:
for each game G₃ do for each iteration t do
8:
9:
Compute the meta meta-policy πT [00===[[M-- (M,)
10:
Compute the best response Φ3.R by Eq. (9) or Eq. (12).
11:
Expand the population . Φ.-1 U { end for Compute (Tp, 4P)) by Eq. (3)
12:
14:
end for
15:
Compute the meta-gradient gR via Eq. (6) Eq. (13)
16:
Update meta-solver's parameters 0' 0 a R Σ ga. end for
17:
18:
end for
3.5
Optimising the Meta-Solver through Meta-gradients
Based on the Player's 's learning objectives in Eq. (3), we can optimise the meta-solver as follows:
0" arg min J (0), where J(0)= EG-P(G) (rpp (T, G)].
(5)
Deriving the (geaa-)gradient of 0 is non-trivial, which we show in the below Remark (3.1).
Remark 3.1. For a given distribution of game p(G), by denoting exploitability at the final iteration
M (ΦBR (TT, Tr)) as Mir+1, the meta-ge gradient for 0 (see also Fig. 1) is
BR
8M1++ ØтT
0
VoJ(O) -Ea
,were
(6)
0
00
00
0Φr
00
8Tr
fo (MT)
f (Mr)
OM, 80r
00
04441
0ΦT+1
80
(7)
00
00
MMr
00
Onr
00
04
00
0ΦT
(
0ΦT
(8)
00
00
00
and Eq. (8) can be further decomposed by iteratively applying Eq. (7) iteration T 1 to 0.
The full proof is in Appendix Intuitively, in the forward process. the population adds T new agents.
In the backward process, the meta- meta-gradient traverses through the full T best-response iterations (each iteration may involve many gradient updates) and back-propagates through all trajectories. Therefore, the gradients of / need collecting from My to M,- Whilst this is critical in introduces computational troubles. Firstly,
ensuring that every agent influential in optimising due to the long trajerrrje dependency, computing meta-gradients becomes inefficient due to multiple Hessian- vector products. Secondly, the gradients are susceptible the same manner as RNNs [19]. To alleviate these issues, we introduce a truncated version similar to
pegloding/vanishinn gradients in
Psecdd--cde including details of the best-response oracles is shown in Appendix C
5

---

[38], where we back-propaaee propagate up to a smaller window size (i.e., < T) of population updates. We shall study the effect of the window size later in Figure Notably, the gradients of - /0,, and 0 / in Eq. (7) also depends on the type of best-response subroutines. In the next section, we demonstrate two types of oracles and show how the meta- meta-gradients are derived accordingly.
3.5.1 Gradient-Descent Best-Response Oracles
When the payoff function G' is known and differentiable, can approximate the best-response through gradient descent (GD). A one-step GD oracle example is written as:
Pe+1 = Φo + a 0M0 (Øo. (TT, 21))
Eebo
where Φo and a denote the initial parameters and learning rate respectively. The backward gradients of one-step GD share similarities with MAML [13], which can be written as:
d
2mm (do. (T, 22)) delf OebuOm:
8am (do. (Tr, 21))
(10)
0Φ:
We refer to Appendix B.1 for the specification of Remark (3.1) for gradient descent-based oracles.
Though Eq. (9) and Eq. (10) can be easily extended to multi-step GD case, it becomes easily intractable to take the gradient of a computational graph that includes hundreds of gradient updates [48, 40, 30J. To solve this problem, we offer another solution for efficient back back-propagation based on the implicil grudient method [40], which does not need the full trajectory as a dependency. The idea is that, when we arrive at the best response point such that 2DM ++11 (T,, 4b)) 08b 0, we can apply the implicit function theorem and derive the gradient by,
BR
d 0Φ:
8 0220(0 (T2, 2c)) aepe 1 a T
8220 @ (T., 2e))
(11)
0 0+:
See the proof in Appendix B.2. Eq. (11) allows for efficient back- pack-propagttion by ignoring the dependency trajectories. Note that the implicit gradient methods can theoretically be applied to compute the meta-gradient w.r.f RL oracles (next section), but empirically we had little success.
3.5.2 Reinforcement Learning Best-Response Oracles
The above GD-based oracles require the pay-off function (i.e., the game engine) to be differentiable. Yet, for complex real-world games such as StarCraft [53], we have rely on RL methods to approximate the best-response agent. Overall, the RL meta- veeta-gradient shares similar structure to that of the above. The major difference that we replace the GD terms with Policy Gradient estimator [55]. Considering the unbiased estimators for the first and the second-order we apply Differentiable Monte Carlo Estimator (DICE) [14] Eq. (9). DICE is an unbiased higher- order gradient estimator that is fully compatible with automatic differentiation. Thanks to DICE, for an RL-based oracle, by regarding the best-response agent eb as Φ1 and the aggregated agent (TT, D,) as Φ2 respectively, we obtain the follow equation:
peeta-poolicyygradiieee
Φ -u +
DIDIC
where J DICEE_
#-1
Σ k=
II W=O
The (at
The
(ak
sx $
rk
(12)
OΦo
(To (at. ( T
(a
where refers to the stop- nro-ggradient operator, r for the reward for agent 1, and H represents the trajectory length. We refer to Appendix B.3 for how DICE provides the unbiased first and second- order meta gradient, and the specification of Remark (3.1) for RL-based oracles. This RL-based formulation is limited in the fact that it is does not directly extend to SOTA RL techniques such as value-based methods [18], and therefore we next introduce a zero-order method that able to tackle the case of non-differentiable pay-off function with any best-response oracle.
3.6 Optimising the Meta-Solver through Evolution Strategies
Inspired by the generality of Evolutionary Strategies (ES) [43] in optimising black-box functions and ES-based MAML [48], we also propose an ES based framework that can cope with any best-response oracle and underlying game engine. We name our method ES-NAC.
The ES approach of [43] states that we have an objective function F(0) over a network parame- terised by 0, we can apply Gaussian perturbations to the parameters that a gradient estimate of the

---

objective function can be achieved by Vo F(O σe) = - B + oeje. In our framework, if we set the objective function F(O) (Tr, 2r) and गт = fo (Mr), we can have
an objective function as function of 0 which can be perturbed. This allows us to write the gradient of a surrogate objective of Eq. (5) as follows:
VoJo(0) = PGG
(TT, $r) G)
(13)
Additionally, we make use of control variates [27] to reduce the variance of the estimator whilst remaining unbiased, for example we apply forward finite differences [6] whereby the exploitability of the unperturbed meta-solver fo is subtracted from the perturbed meta-solver, that is
VoBe- + rc) = Ee (F(O + ae) - F(O))..
(14)
The key benefit of ES-NAC is that it is agnostic to the best-response oracle choice, as only the final exploitability is required. Unlike the implicit formulation we provided in Sec. (3.5.1), is not restricted by the fixed-point condition, which we note is difficult to attain for RL oracles, and therefore may be more widely applicable. This is particularly useful in practice since most games require hundreds of game simulations for each entry in M (e.g., StarCraft [53]), in which case lose the applicability of either GD or RL-bbased oracles. We note that Alg. (1) encapsulates ES-NAC when the number of perturbations 0, and that lines in teal refer only to the ES formulation.
Experiments
We validate the effectiveness of NAC on five types of zero-sum environments' with different levels of complexity. They are Games of Skill (GoS) [8], differentiable Lotto [3], non-transitive mixture game (2D-RPS) [37], iterated matching pennies (IMP) [15, 21) and Kuhn Poker [23]. All selected games are non-trivial to solve as effective solver has to consider both transitive and non-transitive dynamics in the policy space [8, 44]. The motivation behind our selections is to evaluate the performance of NAC under the different oracles proposed in Sec. (3.5) and Sec. (3.6). Specifically, we test the gradient descent-oracle (GD) in GoS, Lotto and 2D-RPS and the RL oracle in IMP. For ES-NAC, we conduct experiments on Kuhn poker [23] with two approximate tabular oracles (V1, V2), an exact tabular oracle" and a PPO [45] oracle. We conduct the experiments on multiple random seeds for NAC and the details of how Appendix E.3. More details of all of the applied oracles and their F, and details of the baseline implementations are in Appendix E.
conduct meta-testing
baseline algorithms and NAC are reported in
are in Appendix
We select the baselines to be vanilla self-play (i.e., best responding to the latest agent in the population) and the PSRO variants, including PSRO [25]. PSRO-Uniform [3] (equivalent to Fictitious Play [5]) and PSRO-IN [3]. Their implementations can be found in OpenSpiel [24]. We believe these methods offer strong benchmarks for NAC since they are all underpinned by game theoretic principles, and
NAC tries to discover solution algorithms purely from data. Results are presented in the form of answering five critical questions W.E. the effectiveness of NAC.
Question 1. How does NAC perform in terms of exploitability on different games?
Firstly, we are interested in whether NAC can learn an auto-curricula that can solve games effectively. In order to characterise performance, measure the exploitability, Eq. (3), of NAC and compare it against other baselines. Surprisingly, results in Fig. (2) suggest that, by learning an effective meta- solver, NAC is able to solve games without explicit game theoretic solution concepts. In particular, NAC performs at least as well as PSRO (only slightly worse than PSRO in IMP), and in multiple games outperforms PSRO. We notice that NAC performs better in the presence of approximate best- responses. One explanation is that Double Oracle relies upon a true best-response oracle to guarantee convergence, when it comes to PSRO where only approximate best responses are available. the principles of sub-game NE may not necessarily fit with PSRO anymore. In contrast, NAC considers the outcomes of approximate best-responses in an end-to-end fashion; therefore, the auto-curricula for each player tends to be adaptive, leading to the development of stronger population. Overall, we helieve these results suggest promising avenue of research for solving larger- scale games (e.g.. StarCraft [53] or XLand [50] ) with exact best responses available and no prior game theoretic solution concepts involved.
"To stay self-contained, we provide a detailed description for each game in Appendix E. TTriining performance for the exact tabular oracle provided in Appendix D.I
7

---

Skills(GD)
Differentiable plottGD)
2D-RPS-implicit(G)
Expi sxploitabiliyy
Iterated Matching Pennies(RL)
Kuhn PekertAppe tabular V1)
Kuhn Poker(Appr tabular V2)
Kuhn- Poker)PPO)
Explortablity
Iterations
Iterations
Iterations
Iterations
Self-play
PSRO-Unifom
PSRO
PSRO-rN
Ours
Figure 2: Exploitability results on five different environments with differing best-response oracles. NAC performs at least as well as the best baseline in all settings, and often outperforms the PSRO baselines. Settings of adopted oracles in each game can be found in Appendix F.
Question 2. What does the learned curricula (i.e., So (M:)) look like?
PSRO
Reration
Iteration
Iteration 10
Iteration
Figure Visualisations of curricula on 2D-RPS. Red points denote the meta-solver output, and darker refers to higher probability in т. The blue star denotes the latest best-response. To achieve low exploitability, one needs to climb up and explore each Gaussian. PSRO fails explore fully, where as NAC creates an effective curricula to explore all modes and assigns each of them high weights.
To address this question?, visualise the auto-currieula the 2D-RPS game between PSRO and NAC in Fig. (3), PSRO is successful in climbing up some Gaussians before iteration 7: however, it fails offer effective auto-curricula that lead it to discover other Gaussians, PSRO fails to select an auto-curricula that takes into consideration whether the best-response oracle capable of learning suitable best-response. This result is inline with [37] and we believe is because the approximate best responses may lead to local optimum in the policy space for PSRO-type methods. In contrast, NAC adaptively generates an auto-curricula which is more suitable for approximate best-responses, as evidenced by a wide spread of agents over the plane, and lower exploitability.
Question 3. Does back-propogation through multiple best-respouse iterations help the training?
As shown by the blue lines in Fig. (1), the backward meta- geradggt will propagate through multiple iterations of best-response processes. To demonstrate its effects, in Fig. (4c) we conduct ablation
We also visualise Kuhn-Poker policy for understanding how NAC works in Appendix D.2

---

Model Aolation Study on GOS
Model Alalation Study IMP
Window Size Ablation
Fanl Exploitability
Fian Exploitabilty
Explo tabliiy
towe)
NLF MUN. ConyGrerd GRU GRUA Us! 1510
Model
MLP MIPL CoreC GAU GRU4 Model
Led
PSRD
Iterations
Figure 4: (a), (b) The effect of different neural architectures on the exploitability in GoS and IMP games. (c) The effect of window size on the exploitability in 2D-RPS game.
Ours
PSRO
PSRO-Uniform
Leduc Seoduc-xxaBe Exact BR
Leduc - Approximate BR
AlphaStar Meta-Game
GoS - Varied Dimensions
24
1.9
Final Expleitabilt billit
Exploitabilit
20
Iterations
Iterations
Iteeatioon
305
Dimension
7:8
100
1000
Figure 5: (a) Exploitability when trained on Kuhn Poker with an exact tabular BR oracle using ES- NAC and tested on Ledue Poker. (b) Same as (a) with approximate tabular BR V2 (c) Exploitability when trained on GoS with GD oracle and tested on the AlphaStar meea-gamee from [8] (d) Final exploitability when trained on 200 Dimension GoS and tested variety of dimension size GoS.
study on NAC by varying the how many best-response iterations (i.e., the window size) we consider, by controlling how many agents are added into the population before computing the meta- veta-gradient. window size of 0 refers to the setting where we completely detach the gradients of the best-response process. We can see that NAC achieves lower exploitability when considering multiple best- response iterations, which reflects the effectiveness of NAC in offering a more suitable and appropriate curricula to strengthen the whole population.
Question 4. How is NAC affected by the architecture and capacity of meta-solver?
In Sec. (3.2), provide several neural architectures for the meta-solver. Thus, to understand the effect of these different architectures, we conduct an ablation study on GoS and IMP. We specify six different models by varying both the architecture and the size. Results in Fig. (4a, 4b) show that, firstly, the permutation invariiance/equivariance models achieve great performance. Secondly, the effect of the meta-solver's architecture is heavily dependent on the game. The performance all three models are comparable for GOS while only MLP and GRU work well for IMP. Different games may need different meta-solver's architecture and GRU-based meta-solver tend to work better. In addition, the increase of network capacity does not correspond to performance improvement. We refer the reader Appendix (F) for details of our model choices for different games.
not a necessary property. as the GRU-based
Question 5. What is the generalisation ability of the neural meta-solver by NAC?
The most promising aspect of NAC is that the neural auto-curricula (i.c., meta-solvers) have the ability generalise different out-of-distribution games. This is particularly impactful, as allows for training on simpler games and then deploying them on larger, more difficult games. We test the generalisation capability of NAC in two settings. First, we take our meta-solver trained over 200 dimensional GoS and test on new unseen GoS of varying dimension. We consider this to be the most direct way of ascertaining whether the neural meta-solvers are able to generalise to larger, more difficult games, and whether the in-task performance still holds out-of-task, Fig. (5d) plots the final exploitability after 20 PSRO iterations against the dimension the GoS, and noticeably, NAC still outperforms the PSRO basclines in all dimensions larger than the training dimension. Additionally,

---

we test our trained meta-solver on the AlphaStar meta geete-amme generated by [8]* in Fig. (5c), which is also considered to be a form of a GoS. Interestingly, our meta-solver is able perform well on GoS that is outside of the task distribution and therefore has different type of underlying dynamics.
Secondly, we introduce example of meta-solver showing the ability to scale-up to different games, namely we train on the Kuhn Poker environment (2 pure strategies) and test on the Leduc Poker environment (3936 pure strategies). As shown in Fig. (5a, 5b) the trained meta-solver is able to outperform the PSRO algorithms when used on Ledue Poker, which suggests NAC enjoys effective generalisation abilities for both an exact best-response oracle and an approximate best-response oracle. We hypothesise that, whilst Ledue Poker is different from Kuhn Poker, the "Poker" nature of both games means they encapsulate similar dynamics, allowing our meta-solver to perform favourably.
5 Conclusion
We introduce method for discovering auto-curricula two-player 7ero-sum games based meta-learning. To our best knowledge, we are the first to show that it entirely possible to perform as well as solutions underpinned in game-theoretic concepts that are designed through human insights, without any active design of the auto-curricula itself. In particular, we show that our NAC method can learn in small games and generalise to larger games, more difficult games that follow a similar underlying structure. We believe this initiates an exciting and promising research area in which large-scale difficult games can be solved effectively by training on simplified versions of the game.
Author Contributions
We summarise the main contributions from each of the authors follows:
Xidong Feng: Idea proposing, algorithm design, code implementation and experiments running (on 2D-RPS, 2D-RPS-Implici and IMP), and paper writing.
Oliver Slumbers: Algorithm design, code implementation and experiments running (on Gos, Blotto, Kuhn-Poker), and paper writing.
Ziyu Wan: Code implementation and experiments running for RL based NAC in Appendix D.4.
Bo Liu: Experiments running for Kuhn-Poker.
Stephen McAleer: Project discussion and paper writing.
Ying Wen: Project discussion.
Jun Wang: Project discussion and overall project supervision.
Yaodong Yang: Project lead, idea proposing, experiment supervision, and whole manuscript writing. The work was done King's College London.
References
[1] Maruan Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. arXiv preprint
2017..
[2] Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint 1rXiv:190.005528 2019.
[3] Balduzzi, M Garnelo, Y Bachrach, W Czarnecki J Pérolat, M Jaderberg, and T Graepel. Open-ended learning in symmetric zero-sum games. In ICML, volume 97, pages 434-443. PMLR, 2019.
[4] Sarah Bechtle, Artem Molchanoy, Yevgen Chebotar, Edward Grefenstette, Ludovic Righetti, Gaurav Sukhatme, and Franziska Meier. Meta learning via learned loss. In 2020 25th Interna- tional Conference on Pattern Recognition (ICPR), pages 4161-4168. IEEE, 2021.
We provide the results the other tens of meta-games from [8] in Appendix D.3
10

---

[5] George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-37, 1951.
[6] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization, 2018.
[7] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv: 1412.3555,
2014.
[8] Wojciech Marian Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafici, David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. arXiv preprint arXiv:2004.00 09468, 2020.
[9] Trevor Davis, Neil Burch, and Michael Bowling. Using response functions to measure strategy strength. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
[10] Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang. On the complexity of computing markov perfect equilibrium in general-sum stochastic games. arXiv preprint arXiv:2109001995 2021.
[11] Le Cong Dinh, Yaodong Yang, Zheng Tian, Nicolas Perez Nieves, Oliver Slumbers, David Henry Mguni, and Jun Wang. Online double oracle. arXiv preprint arXiv:2103.07788 2021.
[12] Yan Duan, John Schulman, Xi Chen, Peter L. Bartlett, llya Sutskever, and Pieter Abbeel. RI: Fast reinforcement learning via slow reinforcement learning. arXiv preprint 1.1.0797, 2016.
[13] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126 1226-1336 1135. PMLR, 2017.
[14] Jakob Foerster, Gregory Farquhar, Maruan Al-Shedivat, Tim Rocktäschel, Eric Xing, and Shimon Whiteson. Dice: The infinitely differentiable monte carlo estimator. In International Conference on Machine Learning, pages 1529-1538. PMLR, 2018.
[15] Jakob N Foerster, Richard Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-learning awareness, arXiv preprint 17Xi::770.04322 2017.
[16] Robert S Gibbons. Game theory for applied economists. Princeton University Press, 1992.
[17] Sergiu Hart. Discrete colonel blotto and general lotto games. International Journal of Game Theory, 36(3):441-460) 2008
[18] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improve- ments in deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[19] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 173 1997.
[20] Rein Houthooft, Richard Y Chen, Phillip Isola, Bradly C Stadie, Filip Wolski, Jonathan Ho, and Pieter Abbeel. Evolved policy gradients. arXiv preprint
2018.
[21] Dong-Ki Kim, Miao Liu, Matthew Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, and Jonathan P How. A policy gradient algorithm for learning to learn multiagent reinforcement learning. arXiv preprint a000022011.00382. 2020.
[22] Louis Kirsch, Sjoerd van Steenkiste, and Juergen Schmidhuber. Improving generalization in meta reinforcement learning using learned objectives. In International Conference on Learning Representations, 2019.

---

[23] Harold W Kuhn. 9. simplified two-person poker. In Contributions to the Theory of Games (AM-24), Volume I. pages 97-104. Princeton University Press, 2016.
[24] Mare Lanctot, Edward Lockhart, Jean- Bann-BBptstte Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, al. Openspiel: A framework for reinforcement learning in games. arXiv preprint 1xXiv:/908.0944 2019.
[25] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, and Thore Graepel. A unified came-theoreti approach to multiagent reinforcement learning, 2017.
[26] Joel Z Leibo. Edward Hughes, Mare Lanctot, and Thore Graepel. Autocurricula and the emergence of innovation from social interaction: manifesto for multi-agent intelligence research. arXiv e-prints, pages arXiv-1903, 2019.
[27] Hao Liu, Richard Socher, and Caiming Xiong. Taming maml: Efficient unbiased meta- reinforcement learning. In International Conference on Machine Learning, pages 4061-4071. PMLR, 2019.
[28] Xiangyu Liu, Hangtian Jia, Ying Wen, Yaodong Yang, Yujing Hu, Yingfeng Chen, Changjie Fan, and Zhipeng Hu. Unifying behavioral and response diversity for open-ended learning in zero-sum games. arXiv preprint arXiv:2106.04958, 2021.
[29] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation, 2015.
[30] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference Artificial Intelligence and Statistics, pages 1540 1552. PMLR, 2020.
[31] Stephen McAleer, John Lanier, Pierre Baldi, and Roy Fox. XDO: A double oracle algorithm for extensive-form games. Reinforcement Learning in Games Workshop, AAAI, 2021.
[32] Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi. Pipeline PSRO: A scalable approach for finding approximate nash equilibria in large games. In Advances Neural Information Processing Systems (NeurIPS), 2020.
[33] H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 536-543, 2003.
[34] Oskar Morgenstern and John Von Neumann. Theory games and economic behavior. Princeton university press, 1953.
[35] Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Marc Lanctot, Edward Hughes, et al. generalized training approach for multiagent learning. In International Conference on Learning Representattons, 2019.
[36] John F Nash et al. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48-44) 49, 1950.
[37] Nicolas Perez Nieves, Yaodong Yang. Oliver Slumbers, David Henry Mguni, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. arXiv preprint arXiv:2103.07927, 2021.
[38] Junhyuk Oh, Matteo Hessel, Wojciech M Czarnecki, Zhongwen Xu, Hado van Hasselt, Satinder Singh, and David Silver. Discovering reinforcement learning algorithms. arXiv preprint 2xXiv:2007.08799 2020.
[39] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
12

---

[40] Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients. 2019.
[41] Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off-policy meta-reinforcemmntt learning via probabilistic context variables. In International conference on machine learning, pages 5331-5340. PMLR, 2019.
[42] Jonas Rothfuss, Dennis Lee, Ignasi Clavera, Tamim Asfour, and Pieter Abbeel. Promp: Proximal meta-policy search. arXiv preprint urivv1880.066884 2018.
[43] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Πly Sutskever. Evolution strategies as scalable alternative to reinforcement learning, 2017.
[44] Ricky Sanjaya, Jun Wang, and Yaodong Yang. Measuring the non-transitivity in chess, 2021.
[45] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint orXiv:177706644 2017.
[46] Jianzhun Shao, Hongchang Zhang, Yuhang Jiang. Shuncheng He, and Xiangyang Ji. Credit assignment with meta-policy gradient for multi-agent reinforcement learning. arXiv preprint ftti::200..19577. 2021.
[47] Avi Singh, Huihan Liu, Gaoyue Zhou, Albert Yu, Nicholas Rhinehart, and Sergey Levine. Parrot: Data-driven behavioral priors for reinforcement learning. arXiv preprint arXiv:2011.10024 2020.
[48] Xingyou Song, Wenbo Gao, Yuxiang Yang, Krzysztof Choromanski, Aldo Pacchiano, and Yunhao Tang. Es-maml: Simple hessian-free meta learning. arXiv preprint 2019.
[49] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv: 1706. 05296, 2017.
[50] Ended Learning Team, Adam Stooke, Anuj Mahajan. Catarina Barros, Charlic Deck, Jakob Bauer, Jakub Sygnowski, Maja Trebacz, Max Jaderberg, Michael Mathieu, et al. Open-ended learning leads to generally capable agents. arXiv preprint 2rXiv:2107. 12808, 2021.
[51] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 259-278, SIAM, 2020.
[52] Vivek Veeriah, Matteo Hessel, Zhongwen Xu, Janarthanan Rajendran, Richard L Lewis, Junhyuk Oh, Hado van Hasselt, David Silver, and Satinder Singh. Discovery of useful questions as auxiliary tasks. In NeurlPS, 2019.
[53] Oriol Vinyals, Igor Babuschkin, Wojeiech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level starcraft using multi-agent reinforcement learning. Nature, 575(7782):350-355 354, 2019.
[54] Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning to reinforcement learn. arXiv preprint 16 2016.
[55] Ronald J Williams. Simple statistical gradient- following algorithms for connectionist reinforce- ment learning. Machine learning, 8(3-4):229 226,, 1992.
[56] Zhongwen Xu, Hado van Hasselt, Mattco Hessel, Junhyuk Oh. Satinder Singh, and David Silver. Meta-gradient reinforcement learning with an objective discovered online. arXiv preprint MxXiv:2007.0843: 2020.
[57] Zhongwen Xu, Hado van Hasselt, and David Silver. Meta-gradient reinforcement learning. arXiv preprint
13

---

[58] Yaodong Yang, Jun Luo, Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou Ammar, Jun Wang, and Matthew Taylor. Diverse auto-curriellum is critical for successful real- world multiagent learning systems. In Proceedings of the 20th International Conference on Autonomous Agents and MulliAgent Systems, pages 51 51-56, 2021.
[59] Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, and Haitham Bou Ammar. ara-rank: Prac- tically scaling a-rank through stochastic optimisation. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1575-1583, 2020.
[60] Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprini arXiv:201 000::2011.0058.0 1.00583, 2020.
[61] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-learning. In International Conference on Machine Learning. pages 10757-10766. PMLR, 2020.
[62] Tom Zahavy, Zhongwen Xu, Vivek Veeriah, Matteo Hessel, Junhyuk Oh, Hado van Has- selt, David Silver, and Satinder Singh. A self-tuning actor-critic algorithm. arXiv preprint arXiv:2002. 12928, 2020.
[63] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. arXiv preprint arXiv: /703.00 00000061100 14, 2017.
[64] Zeyu Zheng, Junhyuk Oh, Matteo Hessel, Zhongwen Xu, Manuel Kroiss, Hado Van Hasselt, David Silver, and Satinder Singh. What can learned intrinsic rewards capture? In International Conference on Machine Learning, pages 11466-11466 1446. PMLR, 2020.
[65] Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. Advances in Neural Information Processing Systems,
2018.
[66] Wei Zhou, Yiying Li, Yongxin Yang, Huaimin Wang, and Timothy Hospedales. Online meta- critic learning for off off-policy actor-critic methods. Advances in Neural Information Processing Systems, 33, 2020.
14


Reviews:
[{"review_id": "lKnCg_CHw4c", "reviewer": "Reviewer_tp6z", "summary": "The authors introduce LMAC, a meta-learning framework that learns to iteratively generate a strong population of agents for a game sampled from some distribution over games. To this end they propose to train a network that predicts a meta-distribution from a given payoff matrix between the agents in the population. This meta-distribution can then be used to train a new best-response agent to add to the population. In the paper they calculate this best response either using gradient descent or reinforcement learning. The choice of meta-solver is also flexible: the authors derive both meta-gradients as well as an evolutionary strategy. They report results on a range of games (from Games of Skill, to Lotto, non-transitive games to Poker).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives:\n* Overall the idea is novel and very interesting.\n* The paper is well and clearly written, the motivation is clear and the relevant related work is cited.\n* The results of the experiments seem promising and the authors compare against appropriate baselines.\n\nConcerns:\n* Overall I have no major concerns with this paper, only a minor concern/question: the authors use different combinations of meta-solvers and best response oracles for each game. However, the particular choice for each combination is not explained (I assume that the combination of choice is the one that works best for each game, but if this is the case why is this combination better?). An experiment that could help give a bit of an intuition about this would be to test the different oracles and meta-solvers on the same game and see the effect they have.\n\n\nSuggestions:\n* Given that the best response algorithms are independent of the meta-solver I would introduce sections 3.5.1 and 3.5.2 outside of 3.5. It would make it more clear that they are used by the evolution strategies as well.\n* Figure 2 is in my opinion initially not very clear. The authors do specify which best response algorithm they use in the title, but not what the meta solver is.\n* The order of the subfigures is sometimes a bit unintuitive. In Figure 4 © is mentioned first in the text, so I would put that one first. In Figure 5, the subfigures are discussed in the opposite order as they appear in the figure, so I would change that as well.\n* In the experiments in Figure 5, PSRO does really well at generalisation as well, it would be nice if the authors would add a few words about this. \n\nNits:\n* In line 305 it’s ‘effect’ not ‘affect’.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The Authors discussed this appropriately.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns about this work from my side.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours."}, "extra_text": {}}, {"review_id": "CPtuM7L5XI", "reviewer": "Reviewer_me4m", "summary": "In the context of two-player zero-sum game, this work introduces the Learned Multi-Agent Auto-Curriculum (LMAC) approach, a meta-learning framework that successfully automates the auto-curicula design, i.e., the update rule of the opponent mixture during training, using data from game interactions. Empirical results also demonstrate that LMAC is able to find auto-curricula that can generalise to more complex environments.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThis work opens the door to automatic auto-curricula generation, presenting promising results in this direction for 2-player zero-sum settings.\n\nQuality: \nThis work lies outside my main area of expertise, but, as far as I can tell, the work is technically sound, with no evident issues and claims are sufficiently supported by the experimental results.\n \nClarity:\nThe submission is clearly written and well organised. It provides sufficient details in the paper plus the supplementary material, as well as the code implementation. \n\nSignificance: \nI believe the results are significant and interesting. LMAC performs on par with methods using game theoretic solution concepts. Moreover, the LMAC meta-solver generalises surprisingly well to larger games. \n\nMinor remarks:\n\n- Line 195 - wrong notation for payoff function\n- inconsistency for the game distribution notation: p(G) vs P(G)\n- Line 150, perhaps I missed it, but what is $\\delta_{|\\Phi_{t-1}|}$?\n- Figure 4, typo for y-axis 'Fianl'", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No statement in this regard.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical considerations.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7Ek1BEAtMmT", "reviewer": "Reviewer_1fYy", "summary": "This paper presents an auto-curriculum method for solving zero-sum games. Previous methods rely on existing methods such as fictitious play, iterated best response, or double oracle to define the set of opponents (i.e., meta strategy) an agent needs to train with. The present work describes Learned Multi-Agent Auto-Curriculum (LMAC), a system that learns the meta-strategy in an end-to-end approach. Empirical results on a set of zero-sum games show that LMAC can be competitive with existing methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Learned Multi-Agent Auto-Curriculum (LMAC) is a complex system that incorporates an interesting and promising idea: learn end-to-end the concept used to define the meta strategy in the context of PSRO. Instead of relying on existing approaches such as fictitious play and double oracle, LMAC learns how to solve the meta game with an end-to-end procedure. A neural model is used to choose the probability distribution over the strategies in the meta game and is trained to minimize the exploitability of the learned strategy. The idea is interesting and promising because it removes the responsibility of deciding which approach to use from the system designer; the system learns how to solve the meta game with gradient descent (or other methods for optimization such as evolutionary methods). \n\nPerhaps the major weakness of the paper is the somewhat mixed results. For some domains LMAC produces less exploitable strategies, for other domains previous approaches perform better. Although the idea is interesting, from the current set of experiments, it seems that the methods that rely on existing game theoretic knowledge are good enough to learn state-of-the-art strategies. Despite the somewhat weak results, I believe the idea is interesting enough for publication. In particular, the ideas presented in this paper might foster more research in this already active area. \n\nThe weakness mentioned in the paragraph above is accentuated by the fact that the paper doesn't fully explore the types of solutions LMAC learns for the meta game. For example, it is clear what game theory approaches such as double oracle, fictitious play, and iterated best response do to the meta game. What is LMAC doing exactly? Figure explores this question in the 2D-RPS domain, but it would be interesting to observe what LMAC does in other games such as Leduc Poker, where it behaves very similarly to fictitious play. Is there a reason for this to happen? Perhaps LMAC learns something similar to a uniform distribution?  \n\nThe paper is already dense (I had to read the paper twice to make sure I understood what was going on), so I understand why some of the results and discussions didn't make it to the paper. Some parts could be removed from the main text. For example, I am not sure it is important to spell out the meta-gradient of the system. The forward pass of the system, the one that goes through several iterations of the process in which the meta game is augmented with a strategy, is easy to understand. The backward pass, where the gradient is needed, is easily implemented by modern machine learning frameworks with automatic differentiation. Figure 1 is very helpful and informative, but it would be even more helpful if it only described the forward pass of the model. The details of the backward pass and gradient computation don't need to be explained. With that in mind, Remark 3.1 could be moved entirely to the supplementary material.\n\nThe paper states that LMAC learns how to play zero-sum games without game theoretic knowledge. I think this claim is not correct. The model is trained to minimize the strategy's exploitability and it uses a learning algorithm to approximate a best response to a mixture of the meta game. Moreover, the meta game grows in each iteration with the best responses that the algorithm approximates. To me, these are game theoretic concepts that are at the core of LMAC. \n\nOTHER QUESTIONS/SUGGESTIONS\n\nQuestions marked with a star (*) are those I would like to see an answer for. \n\n1) LMAC assumes that the game is symmetric because it considers a single population? Does it generalize to asymmetric games? \n\n2) The paper mixes terminology from the RL and Game Theory literature (e.g., it uses reward, payoff, and utility interchangeably). Please use a single term for each concept. \n\n3) I find it confusing to define a player as a population of agents (see 121).\n\n4) \\pi^k_t was defined. Is it the probability of playing the k-th agent at iteration t? \n\n5) The precision \\sigma in Algorithm 1 isn't explained in the text.\n\n6) Algorithm has a \"require\" statement but no \"ensure\" statement. \n\n7) (*) How is the exploitability in line 13 of the pseudocode actually computed? Do you need to run the oracle algorithm to approximate the exploitability? \n\n8) G is the game, not a payoff function (line 195)\n\n9) (*) Is the expectation in Equation 13 approximated with the n samples from line 4 of the pseudocode? \n\n10) How is the exploitability computed for the plots? \n\n11) (*) PSRO is a framework. It isn't clear which version of PSRO is being used in the experiments. \n\n12) Figure 3 is about 2D-RPS, but which version? Implicit or not implicit? \n\n13) (*) Figure 4(c) shows that window of size 5 performs better, but it is also largest window tried. When does it break? The plot should include larger windows. \n\n14) (*) Figure 5 shows how the model learned with one version of a game transfers to another similar game. How about training on a game and testing on a completely different one (e.g., train on GoS and evaluate on Poker)? How about training on a large number of distinct games? What does it learn? Something similar to the uniform distribution? Or a distribution that is similar to what double oracle returns? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact aren't discussed in the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "3QBaez5cWuB", "reviewer": "Reviewer_P5GY", "summary": "This paper proposes LMAC, an auto-curricula mechanism without human design by optimizing the meta-solver through meta-gradients. The main claims are also verified by the conducted experiments.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality and significance:\nBuilding upon PSRO, the proposed algorithm is among the first works that discover the MARL auto-curricula in two-player zero-sum games.\n\nClarity:\nThe paper is clearly written.\n\nComments:\n\n1. In experiments Fig. 4 and 5, the curves are not convergent in the plots. Could you run both LMAC and the baselines for a longer iteration number? In Fig. 5, the improvements over PSRO are not obvious.\n\n2. As the authors mentioned in related work, the proposed algorithm is also closely related to MARL with evolutionary strategies and meta-learning RL algorithms. But the experimental analysis and comparisons are only between LMAC and PSRO. I expect to see more SOTA baseline algorithms to convince the readers that the auto-curricula of LMAC indeed helps.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some limitations of the formulations. And no social impact is provided.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a method to use meta-learning to automatically discover curricula (LMAC), in the form of the meta-solver component of the Policy-Space Reponse Oracles (PSRO) framework of Lanctot et al, 2017. All of the reviewers agree that this is a novel and interesting direction for the game-theoretic approaches to multiagent reinforcement learning in two-player zero-sum games. The reviews also agreed on the quality of the clarity of exposition in writing/presentation. The result showing transfer from Kuhn to Leduc poker (which is roughly one or several hundred times larger depending on the implementation) is especially promising, but it is also between two similarly-structured poker-like games. As pointed out by the reviewers, what remains unclear is precisely what kind of strategies LMAC is learning and more specifically why they help for generlization, and any specific reasons for the mixed results across domains. Also, as remarked by 1fYy, the use of exploitability to drive the meta-solver loss is inspired by von Neumann's minimax theorem (or definition of Nash equilibrium) hence qualifies as game-theoretic knowledge, so the authors need to rephrase this claim. The paper could also benefit significantly from several other word changes pointed out in the reviews.
Decision: Accept (Poster)