MAESTRO: Open-Ended Environment Design for Multi-Agent Reinforcement Learning
Authors: Mikayel Samvelyan
Akbir Khan
Michael D Dennis
Minqi Jiang
Jack Parker-Holder
Jakob Nicolaus Foerster
Roberta Raileanu
Tim Rocktäschel
Venue: ICLR 2023 poster (2023)
Keywords: reinforcement learning
multi-agent learning
unsupervised environment design

Abstract: Open-ended learning methods that automatically generate a curriculum of increasingly challenging tasks serve as a promising avenue toward generally capable reinforcement learning agents. Existing methods adapt curricula independently over either environment parameters (in single-agent settings) or co-player policies (in multi-agent settings). However, the strengths and weaknesses of co-players can manifest themselves differently depending on environmental features. It is thus crucial to consider the dependency between the environment and co-player when shaping a curriculum in multi-agent domains. In this work, we use this insight and extend Unsupervised Environment Design (UED) to multi-agent environments. We then introduce Multi-Agent Environment Design Strategist for Open-Ended Learning (MAESTRO), the first multi-agent UED approach for two-player zero-sum settings. MAESTRO efficiently produces adversarial, joint curricula over both environments and co-players and attains minimax-regret guarantees at Nash equilibrium. Our experiments show that MAESTRO outperforms a number of strong baselines on competitive two-player games, spanning discrete and continuous control settings.

Published as a conference paper at ICLR 2023
MAESTRO: OPEN-ENDED ENVIRONMENT DESIGN FOR MULTI-AGENT REINFORCEMENT LEARNING
Mikayel Samvelyan" !2 Akbir Khan Michael Dennis Minqi Jiang Jack Parker-Holder
Jakoh Foerster' Roberta Raileanu' Tim Rocktäschel
l Meta AI University College London UC Berkeley UUniversity of Oxford
samvelyan@meta. com
ABSTRACT
Open-ended learning methods that automatically generate curriculum of increas- ingly challenging tasks serve as a promising avenue toward generally capable reinforcement learning agents. Existing methods adapt curricula independently over either environment parameters (in single-agent settings) or co-player policies (in multi-ageo agent settings). However. the strengths and weaknesses of co-players manifest themselves differently depending on environmental features. is thus crucial to consider the dependency between the environment and co-player when shaping a curriculum in multi-agent domains, In this work, we use this insight and extend Unsupervised Environment Design (UED) to multi-agent environments. We then introduce Multi-Agent Environment Design Strategist for Open- Open-Ended Learning (MAESTRO), the first multi-agent UED approach for two-player zero-sum settings. MAESTRO efficiently produces adversarial, joint curricula over both envi- ronments and co-players and attains minimax-regret guarantees at Nash equilibrium. Our experiments show that MAESTRO outperforms number of strong baselines on competitive two-player games, spanning discrete and continuous control settings]
INTRODUCTION
The past few years have seen series of remarkable achievements in producing deep reinforcement learning (RL) agents with expert (Vinyals et al. [019 Berner et al. [2019] Wurman et al. (202) and superhuman (Silver et al., 2016 Schrittwieser et al. 2020) performance in challenging competitive games. Central to these successes are adversarial training processes that result in curricula creating new challenges at the frontier of an agent's 's capabilities (Leibo et al., 2019; Yang et al. (021). Such automatic curricula, or autocurricula, policies (Open Ended Learning Team et al., 2021), as well as induce an open-ended learning process (Balduzzi et al. 2019 Stanley al. 2017) that continues endlessly robustify an agent.
improve the sample efficiency and generality of trained
Autocurricula have been effective in multi-agent RL for adapting to different co-play co-players in competitive
games (Leibo al., 2019 Garnelo et al.) 2021 Baker et al.) 2019: [ansal et al. 2018 Feng et al.
2021). where it is crucial to play against increasingly stronger opponents (Silver et al. 2018) and
avoid being exploited by other agents (Vinyals al. 2019). Here, algorithms such as play (Silver
et al. 2018 Tesauro 1995) and fictitious self-play (Brown 1951 Heinrich et al. 20155 have proven
especially effective. Similarly, in maglle-geentt.. RL, autocurricula methods based on Unsupervised Environment Design (UED, Dennis et al. 2020) have proven effective in producing agents robust to wide distribution of environments (Wang et al. 2019 2020 Jiang al.) [221a]] (Parker- et al., 2022). UED seeks to adapt distributions over environments to maximise some metrics of interest. Minimax-regret UED seeks to maximise the regres of the learning agent, viewing this process as a game between teacher that proposes challenging environments and a student that learns to solve them. At a Nash equilibrium of such games, the student policy provably reaches a minimax-regred policy over the set of possible environments, thereby providing strong robustness guarantee.
However, prior works in UED focus on single-agent RL and do not address the dependency between the environment and the strategies of other agents within it. In multi-agent domains, the behaviour of other agents plays a critical role in modulating the complexity and diversity of the challenges faced by learning agent. For example, an empty environment that has blocks to hide behind might be most
Videos of MAESTRO agents available maestro. samvel wan.ann... com

---

Published as a conference paper at ICLR 2023
Student Agent
Generate new envronment
Evaluata
Train
Environment Generator
Sample agent fort
Updato agent's buffer
Periodically
Priottse hich regret agant-
evaliction
using regret
Ru agent's coples
environment poins
Co-Player Population
Environment
Figure 1: A diagram of MAESTRO. MAESTRO maintains a population of co-players, each having an individual buffer of high-regret environments. When new environments are sampled, the student's s regret is calculated with respect to the corresponding co-player and added to the co-player's 's buffer. MAESTRO continually provides high-regret environment/co-play pairs for training the student.
challenging when playing against opponent policies that attack head-on, whereas environments that are full of winding hallways might be difficult when playing against defensive policies. Robust RL agents should be expected to interact successfully with wide assortment of other rational agents in their environment (Yang et al. 202T Mahajan et al. (022). Therefore, to become widely applicable, UED must be extended include multi-agent dynamics as part of the environment design process.
We formalise this novel problem as an Underspecified Partially-Observablee Observable Stochastic Game (UP- OSG), which generalises UED to multi-agent settings. We then introduce Multi-A Agntt Environment Design Strategist for Open-Ended Learning (MAESTRO), the first approach to train generally capable agents in two-player UPOSGs such that they robust to changes in the environment and co-player policies. MAESTRO a replay-guided approach that explicitly considers the dependence between agents and environments by jointly sampling over environment/co-plaeer pairs using a regret-based curriculum and population learning (see Figure D. In partially observable two-player zero-sum games, we show that at equilibrium, the MAESTRO student policy reaches Bayes-Nash Equilibrium with respect to regret- maximiinan distribution over environments. Furthermore, in fully observable settings, it attains a Nash- Equilibrium policy in every environment against every rational agent.
We assess the curricula induced by MAESTRO and variety of strong baselines in two competitive two-player games, namely sparse-reward grid-based LaserTag environment with discrete actions (Lanctot et al. (017) and dense-reward pixel-based MultiCarRacing environment with continuous actions (Schwarting et al. 2021). In both cases, MAESTRO produces more robust agents than baseline autocurmcluum methods out-of-distribttion (OOD) human-designed environment instances against unseen co- players. Furthermore, we show that MAESTRO agents, trained only on randomised environments and having never seen the target task, can significantly outperform specialist agents trained directly on the target environment. Moreover, in analysing how the student's regret varies across environments and co-players, find that joint curriculum, produced by MAESTRO, is indeed required for finding the highest regret levels, as necessitated by UED.
In summary, we make the following core contributions: (i) we provide the first formalism for multi- agent learning in underspecified environments, (ii) we introduce MAESTRO, a novel approach to jointly learn autocurricula over environment/co-playe pairs, implicitly modelling their dependence, (iii) we prove MAESTRO inherits the theoretical property from the single-agent setting of imple- menting a minimax minimax-regret policy at equilibrium, which corresponds to Bayesian Nash or Nash equilibrium in certain settings, and (iv) by rigorously analysing the curriculum induced by MAESTRO and evaluating MAESTRO agents against strong baselines, we empirically demonstrate the importance of the joint curriculum over the environments and co-players.
2 PROBLEM STATEMENT AND PRELIMINARIES
In single-agent domains, the problem of Unsupervised Environment Design (UED) is cast in the framework of an underspecified POMDP (Dennis et al. 2020), which explicitly augments standard POMDP with a set of free parameters controlling aspects the environment subject to the design process. We extend this formalism the multi-agent setting using stochastic games (Shapley 1953).
2

---

Published as a conference paper at ICLR 2023
KC 23
(a) Start of training
(b) Middle of training
(c) End of training
(d) Zero-shot evaluation
Figure 2: Emergent complexity of autocurricula induced by MAESTRO. Examples of partially observable environments provided to the MAESTRO student agent at the (a) start, (b) middle, and (c) end of training. Levels become more complex over time. LaserTag levels (top row) increase in wall density and active engagement between the student and opponent. MultiCarRacing tracks (bottom row) become increasingly more challenging with many sharp turns, (d) Example held-out human- demanndeeigned LaserTag levels and Formula benchmark tracks Jiang et al. 2021a) used for OOD evaluation. For the full list of evaluation environments see Appendix [
An Underspecified Partially Observable Stochastic Game (UPOSG) is given by the tuple M (n, 0,,, R, 7). A. O, and S denote the action, observation, and state spaces, respectively. θ is the set of the environment's free parameters, such as possible positions of walls in maze or levels of game. These parameters can be distinct at every time step and are also incorporated into the transition function T 5 A 6 (S), where A A is the joint action of all agents. Each agent draws individual observations according to the observation function I :S x N - O and obtains reward according to the reward function R S x A N I, where N {1, ................................ n). The discount factor is denoted by y. Each configuration of the parameter A E θ defines specific instantiation of the environment Mg. which is often referred to as level (Jiang et al./ |021a]] Parker-Holder et al., 2022). In this work, we will simply refer to a specific instance 0 as an environment when clear from the context. We use -i to notate all agents except i: π = ( F5- 1, T++ .... TN ). For an agent with stochastic policy n; O A - [0, 1). we define the value in Ma with co-players nh as v (miy - E 7'ri] where rf are the rewards achieved by agent when following policy x, in Ma. The goal is to sequentially provide values for θ and co-players π- to agent i during training so that the policy मं robust to any possible environment and co-player policies. i.e. arg min,, maxo. (V*(T", x==)) (T;; π Rri)), where x² is the optimal policy on O with co-players π -ii UPOSGs are general by nature and allow for cooperative, competitive, and mixed scenarios. Furthermore, θ can represent different game layouts, changes in observations, and environment dynamics. When n = I, UPOSGs are identical to UPOMDPs for single-agent tasks. In the remainder of this work, we concentrate on competitive settings with agents.
2.1 UED APPROACHES IN SINGLE-AGENT RL
A curriculum over the environment parameters 0 can arise from a teacher maximising a utility function Uz(m, 0) based on the student's policy æ. The most naive form of UED is domain randomisation (DR,
Jakobi 1997 Sadeghi & Levine 2017), whereby environments are sampled uniformly at random, C. Recent UED approaches use regret as the objective
corresponding a constant utility 0 [
for maximisation DDnnis al. 2020 Gur et al. 2021): U,,( 0) = max, (REGRET" (IT π m*}} max [o()], where T is the optimal policy on 6.
Empirically, regret-based objectives produce curricula of increasing complexity that re- sult in more robust policies. Moreover, if the learning process reaches Nash equilib- rium, the student provably follows minimax-regret policy (Dennis et al., 2020): [REGRET" (T.A }B)}}. where II and @ are the strategy sets of the student and the teacher, respectively. While this is an appealing property, the optimal policy x" is unknown in practice and must be approximated instead.
E
arg min, n En [maxg,r
Prioritized Level Replay (PLR, Jiang et al., 2021a b) continually curates an environment buffer con- taining the environments generated under domain randomisation with the highest learning potential, e.g., as measured by estimated regret. PLR alternates between evaluating new environments for learn- ing potential and performing prioritised training of the agent on the environments with the highest learning potential so far found. By training the student only on curated high-regret environments, PLR provably results in a uiiima--regre student policy at Nash equilibrium. MAESTRO makes use of PlR-style curation of environment buffers discover high-regret environments during training.
3

---

Published as a conference paper at ICLR 2023
2.2 CO-PLAYER AUTOCURRICULA IN COMPETITIVE MULTI-AGENT RL
The choice of co-players plays a crucial role for training agents in multi-agent domains (eibo et al. 2019). simple but effective approach self-play (SP, Silver al. 2018). whereby the agent always plays with copies of itself. In competitive two-player games, SP produces a curriculum in which opponents match each other in skill level. However, SP may cause cycles in the strategy space when agents forget how to play against previous versions of their policy (Garnelo al., 2021).
Fictitious Self-Play (FSP, Heinrich et al. 2015) overcomes the emergence of such cycles by training an agent against uniform mixture of all previous policies. However, FSP can result in wasting large number of interactions against significantly weaker opponents.
Prioritized Fictitious Self-Play (PFSP, Vinyals et al. 2019) mitigates this potential inefficiency by matching agent A with a frozen opponent from the set of candidates with probability J(P A beats B)) Ecee F(P(A beats CJ}. where defines the exact curriculum over opponents. For example, fhara(z) =
(1 - x) 2T,, where E 1R,, forces PESP to focus on the hardest opponents.
3 METHOD
3.1 AN ILLUSTRATIVE EXAMPLE
To highlight the importance of curricula over the joint space of environments and co-players, we provide an il- lustrative example of simple two-player game in Ta- ble D Here, the goal of the regret-maxines maximmiixiii teacher to select an mnvironment/co-playee dent. Ignoring the co-player and selecting the highest regret environment leads to choosing 03. Similarly, ig- noring environments and selecting the highest regret co- player leads to TC. This yields suboptimal pair (0s. TC) with REGRET((3, TT) 0.4, whereas teacher over the joint space yields the optimal pair (0,, TA) with REGRET((;, AA 0.6. Thus, naively treating the environment and co-player independent can
Table 1:
An illustrative two-player game. Rows correspond to co-player poli- Columns
cies and II = [5 indicate different environments and θ = (0,, 62, 0s, 0a). The payoff matrix repre- sents the regret of the student pair (0, n²)
pair for the stu-
02
0g
8,
Es_e
T
0.6
0.1
0.4
0.2
0.325
48
0.1
0.5
0.4
0.3
0.325
mc
0.2
0.4
0.4
0.4
0.35
ET-n
0.3
0.33
0.4
0.3
yield a sub-optimal curriculum. Such overspecialisation toward a subset of environmental challenges
the expense of overall robustness commonly emerges in multi-agent settings (Garnelo et 2021)
3.2 MULTI-AGENT ENVIRONMENT DESIGN STRATEGIST FOR OPEN-ENDED LEARNING
In this section, we describe a new multi- agent UED approach called Multi-Agent Environment Design Strategist for Open-
Algorithm 1: MAESTRO
Input: Environment generator θ
2 Initialise: Student policy x, co-player population
Ended Learning (MAESTRO) which in- duces a regret-basee autocurricula jointly environments and co-players.
Initialise: Environment buffers Vn' A(T') :=
for (1, do
5
for many episodes do
MAESTRO is a replay-guided approach (Tiang al.) 2021a) that relies vironment generator to continuously cre-
5' ~ 2
> Sample co-player via Eq
Sample replay decision replaying then
D sce Section 3.2.2
8 ~ A(T') Sample a replay environment
new environment instances. Rather
Collect trajectory 7 of using (0, x²)
than storing a single environment buffer,
Update with rewards R(7)
as done by PLR, MAESTRO maintains
else
population of policies B with each pol- icy assigned its own environment buffer. 14 In each environment 0 produced by the generator, MAESTRO evaluates the stu- dent's performance against a non-uniform mixture of co- ro-player policies in B. High- regret environment/co-plen -llyyer pairs then stored, along with the student agent's regret estimate for that pair, in the corresponding co- player's environment buffer.
0 ~ +
Sample random environment Collect trajectory 7 of n using (0, x')
Compute regret score S Regret x²) Update A(T') with using score S
B < B U { A(T!') := =0
> frozen weights
4

---

Published as a conference paper at ICLR 2023
MAESTRO maintains dynamic population of co- co-players of various skill levels throughout training (Czarnecki et al. 2020). Figure pressnnss the overall training paradigm of MAESTRO and Algorithm provides its pseudocode. We note that when applied to fixed singleton environment, MAESTRO becomes a variation of PFSP (Vinyals et al. 2019), where the mixture of policies from the population is computed based the agent's is regret estimate, rather than the probability of winning.
3.2. 1 MAINTAINING A POPULATION OF CO-PLAYERS
A key issue of using replay-guided autocurricula for multi-agent settings is nonstationarity. Specif- ically, using PLR with SP results in inaccurate regret estimates over envirommentcco-plage pairs, as the co-player policies evolve over training. MAESTRO overcomes this issue by maintaining population of past policies (Lanctot et al. 2017). This approach confers several key benefits. First, re-encountering past agents helps avoid cycles in strategy space (Balduzzi et al. 2019; Garnelo ict (al.)2202) Second, MAESTRO maintains accurate regret estimates in the face of nonstationarity by employing separate environment buffer for each policy in the population. Third, MAESTRO always optimises a single policy throughout training, rather than a set of distinct policies which can be computationally expensive.
3.2.2 CURATING THE ENVIRONMENT/CO-PLLEEE PAIRS
To optimise for the global regret over the joint environment/co. penoopeee/occoppyeeerre space, a MAESTRO student is trained to best respond to a non- uniform mixture of policies from a population by prioritising training against co-players with high-regret environments in their buffers:
CO-PLAYER HR E arg max max x'E "EA(TT)
(0,
where 2 is the co-player population, ((r') is the environment buffer of agent T', and Regret is the estimated regret of student for the pair (0, x²). To ensure that the student learns to best respond to high-regret co-players as well as to the entire population B we enforce all members of B to be assigned a minimum probability N For instance, if Equation ( returns a single highest-regret co- player, then the resulting prioritised distribution assigns a weight of N-M(N1) to the highest-regret A to the remaining co-players. For each co-player x' E B, MAESTRO co-player and weight of N maintains a PLR environment buffer A(z') with the top- high-regret levels. Once the co-player is sampled, make a replay decision: with probability p. we use a bandit to sample training environment from A(=') and with probability 1 - p. we sample a new environment for evaluation from the environment generator. Similar to Robust PLR (Jiang al. 2021a), only update the student policy on environments sampled from the environment buffer. This provides MAESTRO with strong robustness guarantees, which we discuss in Section 3.3
3.3 ROBUSTNESS GUARANTEES OF MAESTRO
We analyse the expected behaviour of MAESTRO if the system reaches equilibrium: does MAESTRO produce a sggret-maximsiigg distribution over environments and co-players and the policy optimal with respect to these distributions? We cast this problem in terms of Bayesian Nash equilibrium (BNE) behaviour individual environments. BNE is an extension of Nash equilibrium (NE) where each co-player j has an unknown type parameter 65, which affects the dynamics of the game and is only known to that player. The distribution over these parameters GN is assumed to be common knowledge. Equilibria are then defined as the set of policies, conditioned on their unknown type, each being a best response to the policies of the other players. That is, for policy gΙ of any player
Jj E arg max R,ell,
E ((),
(2)
0N ENE
In MAESTRO, we can assume each co-player is effectively omniscient, as each is co-evolved for maximal performance against the student in the environments it is paired with in its high-regret environment buffer. In contrast, the student has conferred no special advantages and has access to only the standard observations. We formalise this setting as a -i-knowing game. This game corresponds to the POSG with the same set of players, action space, rewards, and states as the original UPOSG, but with sampled at the first time step and provided to co-players -i as part of their observation.
"ampling is based environment's regret score, staleness, and other features following (Jiang et al. 202
5

---

Published as a conference paper at ICLR 2023
Definition 1. The -i-knowing- sarhowiingggmmeeeee of UPOSG M An, = XIEN O,S,TIII
XiEN I, R Xie Ri; 7) with parameter distribution 0 is defined to be the POSG K = =nn' A,A' = A, = O; + (0 if E -i). = =, T = I + (0 E -i,, R2 = R4.7)
where 0 is sampled from the distribution 8 on the first time step.
We thus arrive at our main theorem, followed by a convenient and natural corollary for fully observable settings. We include the full proofs in Appendix [
Theorem 1. two-player zero-sum settings, the MAESTRO student at equilibrium implements a Bayesian Nash equilibrium of the -i-knowing game, over regret-maximising distribution of levels. Corollary In fully-observable two-player zero-sum settings, the MAESTRO student at equilibrium implements Nash equilibrium in each environment in the support of the environment distribution.
Informally, the proof of the Corollary I follows from the observation that the -i-knowing game in a fully observable setting is equivalent to the original distribution of environments, there is no longer an information asymmetry between the student and co- co-players. Moreover, the NE strategy on this distribution of environment instances would be NE strategy on each instance individually, given that they are fully observable. This argument is formalised in Appendix A
4 EXPERIMENTAL SETTING
Our experiments aim understand (1) the interaction between autocurricula over environments and co- co-players in multi-agent UED, (2) its impact on zero-shot transfer performance of student policies to unseen environments and co-players and (3) the emergent complexity of the environments provided to the student agent under autocurricula. To this end, we evaluate methods in two distinct domains: discrete control with sparse rewards, and continuous control with dense rewards. We assess student robustness in OOD human-designed environments against previously unseen opponents. Given its strong performance and usage in related works, PPO (Schulman et al. 2017) serves as the base RL algorithm in our experiments. We provide full environment descriptions in Appendix B and detail our model architecture and hyperparameter choices Appendix C
Baselines and Ablations We compare MAESTRO against two key baselines methods producing autocurricula over environments: domain randomization (DR:Jakobi) 1997). and (Robust) PLR (Jiang
al. 2021a), a state-of-the-ar UED baseline. For co-player curricula, we consider SP, FSP, and PFSP, popular methods that underlie breakthroughs such as AlphaGo (Silver el al. 2016) and AlphaStar (Vinyals et al.) 2019). Since these baselines independently produce curricula either over environments or over co-players, our choice of baselines results in a combination of 6 joint curriculum baselines over the environment/co- player space. We present further ablations investigating the importance of MAESTRO's co- co-player selection mechanism in Appendix D
4.1 ENVIRONMENTS
LaserTag is grid-based, two-player zero-sum game proposed by Lanctot et al. (2017) where agents aim tag each other with laser beams. Success in LaserTag requires agents to master sophisticated behaviours, including chasing opponents, hiding behind walls, keeping clear of long corridors, and mazc-solving. Each agent observes the 5 x 5 grid area in front of and can turn right or left, move forward, and shoot. Upon tagging an opponent, the agent and the opponent receive a reward of 1 and 1, respectively, and the episode terminates. LaserTag training environments are generated by randomly sampling grid size, wall locations, and the initial locations and directions of agents.
MultiCarRacing (MCR, Schwarting al. 2021) is a nigh-dimensional, pixel- continuous control environment with dense rewards. Two agents compete by driving full lap around the track. Fach track consists of n tiles. Agents receive a reward of 1000/n or 500/n for reaching a tile first or second, respectively. Agents receive top-down, egocentric 96 x 96 x 3 partial observation and can collide, push, or block each other, allowing for complex emergent behaviour and non- transiine dynamics. The action space is 3-dimensional, controlling changes in acceleration, braking, and steering. All training tracks used for training agents are generated by sampling 12 random control points defining Bézier curve forming the track.
Figure 2 shows example LaserTag and MCR environments, including human-designa OOD test environments. MCR test environments are the Formula 1 CarRacing tracks from (Tiang al. 2021a)

---

Published as a conference paper at ICLR 2023
5 RESULTS AND DISCUSSION
5.1 CROSS-PLAY RESULTS
To assess the robustness of the approaches, we evaluate all pairs of methods in cross-play on OOD human-designed environments (13 LaserTag levels and 21 Fl tracks for MCR), For each pair of methods, we perform cross-play between all pairs of random seeds (10 x 10 for LaserTag and 5 x for MCR) all environments. Full results are included in Appendix D22
Figure 3 shows the cross-play results on LaserTag throughout and at the end of training. To estimate the robustness of each method unseen environments, evaluate round-robin (RR) tournament results where each baseline is matched against every other baseline. More robust agents should attain higher RR returns across all other agents. We round-robin returns. Although SP-based methods achieve an early performance lead due to more frequent policy updates, MAESTRO quickly outperforms them due its curriculum that prioritises challenging environment/opponen pairs.
that MAESTRO outperforms all baselines in
LaserTag Eval [13 Tasks]
LaserTag- Eval [13 Tasks]
LaserTag-Eval [13 Tasks]
1.0
sR Penurn
0.05
Hormalize
RR
-0.05
0.10
4GK
40K
Updates
MAESTRO
PLR+SP
PLR+FSP
PLR+PFSP
DR-SP
DR+FSP
DR+PFSP
Figure 3: LaserTag Cross-Play Results. (Left) normalised and (Middle) unnormalised RR returns during training. (Right) RR returns at the end of training (mean and standard error over seeds).
Figure reports the MCR results the challenging Fl tracks. Here, MAESTRO policies produce the most robust agents, outperforming all baselines individually across all tracks while also spending less time the grass area outside of track boundaries. PLR- b-sdd baselines outperform DR, underscoring the benefits of a curriculum over environments on this task. Nonetheless, MAESTRO'S 's superior performance highlights the importance of joint curriculum environments and co-players.
Formula [21 Tasks]
Formula [21 Tasks]
Formula [21 Tasks]
1000-
420
0.8-
300
000
2.4
200
400-
3.0
MAESTRO
PLR+SP
PLR+FSP
PLR+PFSP
DR.SP
DR+
DR+PFSP
Figure 4: MultiarRaacing Cross-Play Results. (Left) RR returns (Middle) Cross-play win rate and (Right)
grass time hetween MAESTRO and haselines (mean and standard error over 5 seeds).
5.2 IMPORTANCE OF THE CURRICULUM OVER THE ENVIRONMENT/CO-PLATE SPACE
co-playerxenvinommen regret landscape of MAESTRO student agent mandoml-ssapples environments against each co-player from MAESTRO'S 's population at the end of training (as done in the motivating example in Section 3.1). We observe that high regret estimates depend on both the choice of the environment and the co-player. Most importantly, maximising mean regrets over environments and co-players independently does not lead maximum regret the joint space, highlighting the importance of the curricula over the joint environment/co-playe space.
Figure 5
shows the co-playerx environment
5.3 EVALUATION AGAINST SPECIALIST AGENTS
While we show that MAESTRO outperforms baselines trained on a large number of environments, are also interested in evaluating MAESTRO against specialist agents trained only single, fixed environments. Figure showws that, despite having never seen the target environments, the MAESTRO agent beats specialist agents trained exclusively them for the same number of updates. This is
7

---

Published as a conference paper at ICLR 2023
Landsrane
MultiCarRacing
60
83
635
En
Enitomment
inviroment
Figure 5: Regret landscapes Laser'Tag and MultiCarRacing, Shown regret estimates of the student on 16 random environment (columns) against each policy from MAESTRO'S co-player population (rows). Highlighted in red are the regret estimates of the co-player and environment with the highest mean values when considered in isolation, whereas in green we highlight the overall highest regret mivironment/co-playe pair.
possible because the MAESTRO agent was trained with autocurriclum that promotes the robustness of the trained policy, allowing it to transfer better to unseen opponents on OOD environments. These results demonstrate the potential of multi-agent UED in addressing key problems in multi-agent RL,
such as exploration [Lennardos et al. 2021 and co-player overfitting Lanctot et al. 2017)
LaserTag Tasks]
LaserTag Tasks]
Formulag Tasks]
Formuls Tesks]
Roys Recarn
0.50
Cross Paa Rate
0.5
0.-
Cooss Pay Seturn
Ray
300
200
MAESTRO SP Soedalist PSP Specializt
Tik
Student Updates
Figure 6: Cross-Play vs Specialists. Cross-play evaluation against specialist agents trained directly on the target task. We use different specialist agents for each fixed environment. Shown averaged metrics across target LaserTag levels and 3 Formula tracks, Full results individual environments included Appendix E.
5.4 EMERGENT CURRICULUM ANALYSIS
We analyse the curriculum over environments induced by MAESTRO and compare it with the curricula generated by the baselines. Figure demonstrates that, as training progresses, MAESTRO provides agents with LaserTag environments with increasing density of walls, which contributes gradual increase in environment complexity. Initially, the size the grid also increases as the teacher challenges the student to navigate the mazes. However, after more adept opponent agents enter the population, larger mazes yield lower regret. Instead, MAESTRO starts prioritising smaller grid sizes compared other baselines. Smaller environments with high wall density challenge the student to navigate maze structures while succeeding in more frequent multi-agent interactions against increasingly more capable opponents throughout an episode. Figure 2c illustrates such challenging environments, which, due to the smaller grid, require the student to engage with the opponent earlier the episode. PLR-based methods also prioritise high wall density but not shrink the grid size to prioritise competitive interactions to the same extent as MAESTRO.
LaserTag Train
LaserTag Train
Train
MCR
34.
2.02
15000
0.16
20
Und
9,935
0.14
2,43
16000
* Student Updates
Studest Lpdatts
Student Uppatess
Student Undates
Student Undetes
MAESTRO
PLR+SP
PLR+FSP
PLR+PESP
DR+SP
DR+FSP
DR+PESD
Figure 7: Characteristics of emergent autocurrieula in LaserTag and MultiCarRacing
We observe similar emergent complexity in the MCR domain. Here the PLR-based baselines and MAESTRO all prioritise tracks that have a high number of notches (i.e. the non-convex parts of the track) and enclosed areas. Here, in the LaserTag domain, MAESTRO gradually shrinks the track amplitude, which corresponds to a lower intensity of the winding portions of the track. Such tracks may contain more segments where competitive interactions can play out without sacrificing overall episodic return, thus inducing policies more adept at the competitive aspects of this domain. Figure 2 illustrates randomly sampled environments curated by MAESTRO at different stages of training.
8

---

Published as a conference paper at ICLR 2023
6 RELATED WORK
Unsupervised Environment Design (UED, Dennis et al. 2020) is family of methods that provide
an agent with a sequence of environments for training robust policies. The simplest UED approach
is Domain Randomisation (DR, Jakobi 1997 Sadeghi & Levine, 2017) which has demonstrated
strong empirical performances in domains such as robotics (Tobin et al. 2017|pames ct al., 2017)
and magnetic control of tokamak plasmas (Degrave al. 2022). PAIRED (Dennis et al. [020 Gur
let al. (021)) trains an environment generator that maximises the student's 's regret, approximated as the difference in return between the student and an antagonist agent. Prioritized Level Replay (PLR,
Jiang et al. 202 la b) curates environment instances (i.e., levels) for training. by performing a random search of domain randomised levels for those with high learning potential, e-g.. as measured by estimated regret. ACCEL (Parker-Holdee et al.] (022) is a replay-guided UED approach that extends PLR by making edits to high-regret environments. Several methods generate curricula by adapting the environment parameters in response to the agent's performance (Portelas et al., (2099] Matiisen jet al. 2020 Klink et al. 2019 Fimer et al. 202T). This adaptation is largely heuristic-driven, without the robustness guarantees shared by minimax- UED methods. Notably, all these methods focus on single-agent RL, while MAESTRO is designed for the two-player multi-agent setting.
Many prior works study curricula over opponents in two-player zero-sum settings. The most naive approach, self-play (SP), consists of pitting the agent against a copy of itself. Combined with search, SP has led to superhuman performances in board games such as Backgammon (Tesauro 1995). Chess and Go (Silver et al. 2016). Zinkevich et al. (2007) use self-play with regret minimisation for achieving Nash equilibrium, an approach that led to superhuman performance in Poker (Brown) & Sandholm 2018 2019). Fictitious self-play (FSP) learns a best-response to the uniform mixture of all previous versions of the agent (Brown) 1951 Leslie Collins 2006 Heinrich al.. 2015).
Prioritised fictitios self-play (PFSP, Vinyals et al. (019)) trains agents against non-uniform mixture of policies based on the probability of winning against each policy. PFSP is a practical variant of Policy-Space Response Oracles (PSRO. Lanctot et al., (017), general population learning framework, whereby new policies are trained as best responses to a mixture of previous policies. MAESTRO is related to PSRO but adapted for UPOSGs. In MAESTRO, the population meta-strategy is based on the student's regret when playing against policies on environments observed during training. Unlike our work, these prior autocurriulaa methods for competitive multi-agent environments do not directly consider variations of the environment itself.
Several prior works have applied DR in multi-agent domains. Randomly modifying the enviromment has proven critical for the emergence of complex behaviours in Hide-and-Seche (Baker et al., 2019).. Capture the Flag (Jaderberg al. 2019). and StarCraft II Unit Micromanagement (Ellis et al. 2022). In XLand (Open Ended Learning Team et al.) 2021). a curriculum is provided over both environments and tasks to create general learners. This work differs from ours in multiple aspects. Open Ended Learning Team et al. (2021) uses handcrafted heuristics and rejection sampling for selecting environments for training and evaluating agents, while MAESTRO automatically selects environments based on regret rather than hand-coded heuristics. Furthermore, unlike the autocurricula used in XLand, MAESTRO does not rely on population- based training, computationally expensive algorithm for tuning the autocurriculum hyperparameters.
7 CONCLUSION AND FUTURE WORK
In this paper, we provided the first formalism for multi-agent learning in underspecified environments. We introduced MAESTRO, an approach for producing an autocurriculum over the joint space of environments and co-players. Moreover, we proved that MAESTRO attains minimax-regrel robustness guarantees at Nash equilibrium. Empirically MAESTRO produces agents that are more robust to the environment and co-player variations than a number of strong baselines in two challenging domains. MAESTRO agents even outperform specialist agents in these domains. Our work opens up many interesting directions for future work. MAESTRO could be extended to n-player games, as well as co- operative and mixed settings. Furthermore, MAESTRO could be combined with search-based methods in order to further improve sample efficiency and generalisation. Another interesting open question is identifying conditions whereby such an algorithm can provably converge to Nash equilibrium in two two-player zero-sum settings. Finally, this work is limited to training only a single policy for each of the multi-agent UED approaches. Concurrent and continued training of several unique policies in underspecified multi-agent problems could be a generally fruitful research direction.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We extend our gratitude to Christopher Bamford for his assistance with the Griddly sandbox frame- work (Bamford et al. 2020 2022) used for our LaserTag experiments. We thank Max Jaderberg. Marta Garnelo, Edward Grefenstette, Yingchen Xu, and Robert Kirk for insightful discussions and valuable feedback on this work. We also thank the anonymous reviewers for their recommendations on improving the paper. This work was funded by Meta AI.
REFERENCES
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula, 2019. /RRLttts:///ax
axg/abb/1909.. 07528
David Balduzzi, Marta Gamello, Yoram Bachrach, Wojeiech Czamecki, Julien Perolat, Max Jaderberg. and Thore Graepel. Open-ended learning in symmetric zero-sum games. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Learning, volume 97 of Proceedings of Machine Learning Research, pp. 434 443. PMLR, 09-15 (tress//91//aaauuz2119 html
Machine
Jun 2019. bttpst http:tttpps//pppceeeegggoooo/e/e
mlr wwtpppppssssppepteepee wwtp//99//aaa./..
Chris Bamford, Shengyi Huang, and Simon Lucas. Griddly: A platform for ai research in games, 2020. URL
Christopher Bamford, Minqi Jiang, Mikayel Samvelyan, and Tim Rocktäschel. GriddlyJS: A web IDE for reinforcement learning. Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. htlpsttss: /ooperevvii net. forum?
1d==macJvvi UR _
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition. In International Conference on Learning Representations, 2018. URL htt.ttpss//ppeeeeieee... net/ for wtteee//oorummmm=y0o0allll
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang. Filipp Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. CoRR, abs/1912.0666 2019.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376. 1951.
Noam Brown and Tuomas Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 2018.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456): 2019. doi: 10. 10.1116//ciemcc.aay24444 3bs/10.1126/ccienese
http:t/:::/ hota::/wwa /tt::///wwwww/// www.siinn.nnnneeeeeeeeeeeeeeeeee
Wojeiech M Czarnecki, Gauthier Gidel, Brendan Tracey, Karl Tuyls, Shayegan Omidshafici. David Balduzzi, and Max Jaderberg. Real world games look like spinning tops. Advances in Neural Information Processing Systems, 33:17443-17454 2020.
Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan D. Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki, Diego de Las Casas, Craig Donner, Leslie Fritz, Cristian Galperti, Andrea Huber, James Keeling, Maria Tsimpoukelli, Jackie Kay, Antoine Merle, J-M. Moret, Seb Noury, Federico Pesamosca, David G. Pfau, Olivier Sauter, Cris- tian Sommariva, Stefano Coda, B. Duval, Ambrogio Fasoli, Pushmeet Kohli, Koray Kavukcuoglu, Demis Hassabis, and Martin A. Riedmiller. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602:414 419, 2022.
10

---

Published as a conference paper at ICLR 2023
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In Advances in Neural Information Processing Systems, volume 33, 2020.
Theresa Eimer, André Biedenkapp, Frank Hutter, and Marius Lindauer. Self-paced context evaluation for contextual reinforcement learning. In The International Conference on Machine Learning. 2021.
Benjamin Ellis, Skander Moalla, Mikayel Samvelyan, Mingfei Sun, Anuj Mahajan, Jakob N. Fo- erster, and Shimon Whiteson. SMACv2: An improved benchmark for cooperative multi-agent reinforcement learning, 2022. URL BtlL:ttss:// www.w.owoooo.....ooo abs////////// 2212. 22122.74822
Xidong Feng. Oliver Slumbers, Ziyu Wan, Bo Liu, Stephen McAleer, Ying Wen, Jun Wang, and Yaodong Yang. Neural Auto-Curriela in Two-Player Zero-Sum Games. In Ad- vances in Neural Information Processing Systems, volume 34, pp. 3504-3517. Curran Asso- ciates, Inc., 2021. URL httppps://prcceeed neurips CC hateer//22/hhhaaaai [ecTbbeeee2257705556000eeeeee aateeeeeaaaaaaaataaaaaaa Abst ract. html
Marta Garell,, Wojciech Marian Czameeki, Siqi Liu, Dhruva Tirumala, Junhyuk Oh, Gauthier Gidel, Hado van Hasselt, and David Balduzzi. Pick your battles: Interaction graphs as population-level objectives for strategic diversity, 2021. URL https: arwiv. wwtp./.rrrgaabb/1...0/ 04041
Izzeddin Gur, Natasha Jaques, Yingjie Miao, Jongwook Choi, Manoj Tiwari, Honglak Lee, and Aleksandra Faust. Environment generation for zero-shot compositional reinforcement learning. In Advances in Neural Information Processing Systems, 2021.
Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive-form games, In International conference on machine learning, pp. 805-813. PMLR, 2015.
Max Jaderberg, Wojeiech M. Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Cas- tañ eda, Charles Beattie, Neil C. Rabinowitz, Ari S. Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel. Human-level performance in 3d multiplayer games with population-bal reinforcement learning. Science, 364(6443):859--86)) 865, may 2019.
Nick Jakobi. Evolutionary robotics and the radical envelope-of-noise hypothesis. Adaptive Behavior, 6(2):325-368, 1997.
Stephen James, Andrew J. Davison, and Edward Johns. Transferring end-to-end visuomotor control from simulation real world for multi-stage task. In Ist Conference on Robot Learning, 2017.
Minqi Jiang, Michael Dennis, Jack Parker- Holddr,, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Replay-guided adversarial environment design. In Advances in Neural Information Processing Systems. 2021a
Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized level replay. In The International Conference on Machine Learning. 2021b.
Pascal Klink, Hany Abdulsamad, Boris Belousov, and Jan Peters. Self- paced contextual reinforcement learning. In Conference on Robot Learning. 10 2019.
Mare Lanctot, Vinicius Zambaldi, Audrumas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Perolat, David Silver, and Thore Graepel. A unified theeethi approach to multiagent reinforcement learning, 2017. URL htt /ttp://aavvvvii hawpr////bb//.. 711 00832
Joel Z. Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas, 2017. URL https::/arxiv..rrt abs/1702.03000
Joel Z. Leibo, Edward Hughes, Marc Lanctot, and Thore Graepel. Autocurriulaa and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research. ArXiv, Abs/1903.00742,, 2019.
11

---

Published as a conference paper at ICLR 2023
Stefanos Leonardos, Georgios Piliouras, and Kelly Spendlove. cuploration-exploitttaiee in multi- agent competition: Convergence with bounded rationality. A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan Advances in Neural Information Processing Systems, 2021. URL ht.tps://ppent
ew net forum? dio.ii...iiiiii--. IRRe)
David S Leslie and Edmund J Collins. Generalised weakened fictitious play, Games and Economic Behavior, 56(2):285 298,, 2006.
Xiaoteng Ma. Car racing with pytorch. 2019. URL http:////ggtthbb..c.///aaaaa/ape
car caring
Anuj Mahajan, Mikayel Samvelyan, Tarun Gupta, Benjamin Ellis, Mingfei Sun, Tim Rocktäschel, and Shimon Whiteson. Generalization in cooperative multi-agent systems. arXiv preprint arXiv:2202.00114, 2022.
Tambet Matiien, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. IEEE Trans. Neural Networks Learn. Syst. (1(1):3733-33773 3740, 2020.
Open Ended Learning Team, Adam Stooke, Anuj Mahajan, Catarina Barros, Charlie Deck, Jakob Bauer, Jakub Sygnowski, Maja Trebacz, Max Jaderberg, Michaël Mathieu, Nat McAleese, Nathalie Bradley-Schmicg, Nathaniel Wong, Nicolas Porcel, Roberta Raileanu, Steph Hughes-Fitt, Valentin Dalibard, and Wojciech Marian Czamecki. Open-ender learning leads to generally capable agents. CoRR, abs/2107. 12088, 2021.
Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan, Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Evolving curricula with regret-based environment design, 2022.
http::::/aaxxvv.../ wwtp 220./22232..2 01302
Rémy Portelas, Cédric Colas, Katja Hofmann, and Fierre-Yver Oudeyer. Teacher algorithms for curriculum learning of deep RL in continuously parameterized environments. In Leslie Pack Kael- bling, Danica Kragic, and Komei Sugiura (eds.), 3rd Annual Conference on Robot Learning, CoRL 2019, Osaka, Japan, October 30 November 1, 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pp. 835-853. PMLR, 2019.
Fereshteh Sadeghi and Sergey Levine. CAD2RL: real single-image flight without a single real image. In Nancy M. Amato, Siddhartha S. Srinivasa, Nora Ayanian, and Scott Kuindersma (eds.), Robotics: Science and Systems XIII, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, July 12-16, 2017 2017.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588 (7839):604 609, dec 2020.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. ArXiv, abs/l107.06330 2017.
Wilko Schwarting, Tim Seyde, Igor Gilitschenski, Lucas Liebenwein, Ryan Sander, Sertac Karaman, and Daniela Rus. Deep latent competition: Learning to race using visual control policies in latent space, 2021.
L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 199)) 1100, 1953. doi: 10. 00.1073/paa.39.10..00 URL httt::ttt///wwt pnas org/oooooooooooooooooooo abbs//bb 1073/pnas 39. 10. 1095
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham. Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap. Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529:484 489, 2016.
12

---

Published as a conference paper at ICLR 2023
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419); 1:0:-1144144 2018. doi: 10.1 26/science. aar6404.
Kenneth O Stanley, Joel Lehman, and Lisa Soros. open-endedness: The last grand challenge you 've never heard of. While open- enneenndssssss could be force for discovering intelligence, it could also be a component of Al ütseff, 2017.
Gerald Tesauro. Temporal difference learning and td-gammon. Commun. ACM, 38(3):58-68, mar 1995. ISSN 0001-0782.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017, pp. 23-30. IEEE, 2017.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, Laurent Sifre. Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom L. Paine, Çaglar Gülçehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap, Koray Kavukeuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nat., 575(7782): 350-354, 2019. doi: 10.1038/s41 186-01999-99 586-019-1724-2.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O. Stanley. Paired open-ended trailblazer (POET); endlessly generating increasingly complex and diverse learning environments and their solutions. CoRR, abs/1901.10 0173,, 2019.
Rui Wang. Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeffrey Clune, and Kenneth Stanley. Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 9940-9951. PMLR, 13-18 Jul 2020.
Peter R. Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas J. Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, Leilani Gilpin, Piyush Khandelwal, Varun Kompella, HaoChih Lin, Patrick MacAlpine, Declan Oller, Takuma Seno, Craig Sherstan, Michael D. Thomure, Houmehr Aghabozorgi, Leon Barrett, Rory Douglas, Dion Whitehead, Peter Dürr, Peter Stone, Michael Spranger, and Hiroaki Kitano. Outrac- ing champion Gran Turismo drivers with deep reinforcement learning. Nature 602(7896):223-228 February 2022. ISSN 1476-4687.
Yaodong Yang, Jun Luo, Ying Wen, Oliver Slumbers, Daniel Graves, Haitham Bou-Ammar, Jun Wang, and Matthew E. Taylor. Diverse auto-curriculum is critical for successful real-world multiagent learning systems. In Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (eds.), AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021. pp. 51-56. ACM, 2021.
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. Regret min- imization in games with incomplete information. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran As- sociates, Inc., 2007. URL https: URUjsttpss///rroeedddao www.nnuuriiiooo htt.ppp.ccppppp.eppp 2007/file/ ( 01no633866..aa112222246666663333
pdf
13

---

Published as a conference paper at ICLR 2023
A THEORETICAL RESULTS
is useful to understand the long-term behaviour of MARSTRO the student and teacher agents reach optimality. In this section, we will formally characterise this equilibrium behaviour, showing MAESTRO achieves a Bayesian Nash equilibrium in a modified game, which we call the -i-knowing game, in which the other player has prior knowledge of the environment and can design their policy accordingly. We will do this by first defining the -i-knowing game, showing that the policies the MAESTRO student learns in equilibria represent Bayesian Nash equilibrium strategies in this game, and then specialising this result to a corollary focused on fully observable games where MAESTRO finds Nash equilibrium for all environments in support of the teacher distribution.
We will define the - -i-knowing- game, given UPOSG M, with parameter distribution A as POSG constructed as modification of the original game where the distribution over parameters is determined by 0, and the agents other than i know the true parameters of the world. This simulates the setting where the co-player is specialist for the particular environment, who has played the game many times. More formally:
Definition 1 The -i-knowing-gue gaamiinggggggegeee of UPOSG M An, XiENO;, O, X R Xie Xi R2,7) with parameter distribution 0 is defined to be the POSG K = (n' A, = A, = O (0 if -i). T = I + [0 if E -),, R2 = where 0 is sampled from the distribution @ on the first time step. That is, POSG with the same set of players, action space, rewards, and states as the original UPOSG, but with 0 sampled once at the beginning of time, fixed into the transition function and given to the agents -i as part of their observation.
We use K (TT; n ; ()) to refer to the utility function in the -i-knoning game, which can be written in terms of the utility function of the original UPOSG
UK (T: n 0) = T. 0~0
(0),
where (0) is the policy for players -i in the i-kkooinng game conditioned on O. Given this definition, we can prove the main theorem, that the equilibrium behaviour of MAESTRO represents a Bayesian Nash equilibrium of this game.
Theorem 1. In two-player zero-sum settings, the MAESTRO student equilibrium implements Bayesian Nash equilibrium of the -i-knowing game, over a regret-maximising distribution of levels.
Proof. Let Ti, jM be a pair which is in equilibrium in the MAESTRO game. That is:
Ty arg maxt E [U(m; 0. :~MM
(3)
@M arg max
E [Um Um;
(MEA +) 8.T-INON
where ग. is an optimal policy for player given -- and 0, while (S)) denotes the set of distributions over S. Then we can define Regret to be the marginal distribution over 0 from samples 0, π gM
Define (0) as the marginal distribution over m sampled from وM conditioned on 0 for 0 in the support of GM and - best response 0 and n; otherwise.
We will show that xT) is Bayesian Nash equilibrium on -i-knowing game of M with a regret-maximizing distribution over parameters D Regret We can show both of these by unwrapping and re- re-wrapping our definitions.
First to show म; E arg max {
E x,Ell, DRegett
UK n (
m arg maxt EH
U (,
Regrer
m. E arg max mlll
E 0 0.
(mm;="((()):0)
(6)
nT arg max Ell,
E f
[UTTA==(1]]
14

---

Published as a conference paper at ICLR 2023
Which is known by the definition of Nash equilibrium in the MAESTRO game, in Equation
Similarly, show that have n arg max n = RRegre
E
IU (T: (m;m=;;11) by:
K arg max - ell DRegre
L (T;
(8)
E arg max ET,
E
[U(T; π (0);
(9)
0
(0) arg max
E [UTTT==;(]]}
(10)
x Em 0
The final line of which follows from the fact that æ-; is best-response for each 0. More concretely, this can be seen in Equation by noting that and _., conditioned on a specific can be independently optimised and holding 0 fixed.
Using this theorem, we can also prove natural and intuitive corollary for the case where the environment fully observable:
Corollary D In fullo--bbeervable two-player zero-sum settings, the MAESTRO student at equilibrium implements Nash equilibrium in each environment in the support of the environment distribution.
Proof. From Theorem 1
we have:
Ty arg max W.EII, Reegrtt
IUK (N (T;T5(;;11)
However, since the world is fully observable, the policy R can be made independent the additional observation 0 in the -i-knowing game since that can be inferred from the information already in the agent's observations. As such, R can be interpreted as a policy the original game, giving:
my arg max E EI ReeDRegres
Moreover, since the enviromment is fully observable, म; can condition on so for to be optimal for the distribution, it must be optimal for each level in the support of the distribution. Giving, for each be in the support of gM: W arg ( m.lll,
showing that æ is a best-response to xx((0) on 0. The same arguments can be followed to show that TxK(() (0) is a best response to on 0. Since each policy is a best response to the other, they are in Nash equilibrium as desired.
Thus, MAESTRO reaches an equilibrium in fully observable two-player zero-sum setting, it be- haves expected by achieving Nash equilibrium in every environment in support of the curriculum distribution MM
B ENVIRONMENT DETAILS
This section describes the environment-spee speecfff details used in our experiments. For both LaserTag and MultiCarRacing, we outline the process of environment generation, present held-out evaluation environments, well other relevant information.
15

---

Published as a conference paper at ICLR 2023
+
(a) Cross
(b) FourRooms
(c) SoxmeenRooms
(d) Ruins
(e) Ruins2
5
(I) Star
(g) LargeCorridor
(h) Mazel
ii) Maze2
Arenal
(k) Arena2
(I) Corridorl
(m) Corridor2
Figure 8: Evaluation environments for LaserTTag.
B.1 LASERTAG
LaserTag is a two-player zero-sum grid-based game, where two agents aim to tag each other with a light beam under partial observability. is inspired by prior singleton variation used in (Lanctot et al.
2017 Leibo et al. 2017) and developed using the Griddly sandbox framework (Bamford et al. 20200 2022). LaserTag challenges the agent to master various sophisticated behaviour, such as chasing opponents, hiding behind walls, keeping clear of long corridors, maze solving, etc. Each agent can only observe 5 x 5 area of the grid in front of it. The action space includes the following 5 actions: turn right, turn left, move forward, shoot, and no-op. Upon tagging an opponent, an agent receives a reward of 1, while the opponent receives 1 penalty, after which the episode is restarted. If the episode terminates while the two agents are alive, neither of the agents receives any reward.
All environment variations (or levels) that are used train agents are procedurally generated by an environment generator. Firstly, the generator samples the size of the square grid (from 5 x 5 to 15 15) and the percentage of the walls in it (from 0% 50%) uniformly at random. Then the generator samples random locations for the walls, followed by the locations and directions of the two agents. Figure Dillustrates some levels sampled from the level generator. Note that the generator can generate levels where agents are unreachable.
Upon training the agents on randomly generated levels, we assess their robustness on previously unseen human-designed levels shown in Figure 8 against previously unseen agents.
B.2 MULTICARRACING
MultiCarRacing is continuous control problem with dense rewards and pixel-based observations
(Schwarting et al. 2021). Each track consists of n tiles, with cars receiving a reward of 1000/ or 500/n, depending on if they reach the tile first or second respectively. An additional penalty of -0.1 is applied at every timestep. Episodes finish when all tiles have been driven over by at least one car. If a car drives out of bounds of the map (rectangle area encompassing the track), the car "dies" and the episode is terminated. Each agent receives a 96 x 96 x 3 image as observation at each timestep. The action space consists of simultaneous moves that change the gas, brakes, and steering direction
16

---

Published as a conference paper at ICLR 2023
(a) F1-Australia
(b) Fl-Austria
(c) F1-Bahrain
(d) F1-Belgium
(c) F1-Brazil
C
(f) FI-China
(g) FI-France
(h) FI-Germany
(i) FI-Hungary
(i) F1-Iallyy
(k) Fl-LagunaSeca
(I) FI-Malaysia
(m) F1-Mexico
(n) FI-Monaco
(0) FI-Netherlands
(p) F1-Portugal
(q) FI-Russia
(r) Fi--Sngapore
F1-Spain
(1) FI-UK
(u) FI-USA
Figure 9: Evaluation Formula tracks for MultiCarRacing originally from Jiang et al, 2021a)).
of the car. For this environment, we recognise the agent with higher episodic return as the winner of that episode.
All tracks used to train student agents are procedurally generated by an environment generator, which was built top of the original MultiCarRacing environment (Schwarting al. 202T. Each track consists of closed loop around which the agents must drive full lap. In order to increase the expressiveness of the original MultiCarRacing, we reparameterized the tracks using Bézier curves. In our experiments, each track consists of Bézier curve based on 12 randomly sampled control points within a fixed radius of B/2 of the centre O of the playfield with B size.
For training, additional reward shaping was introduced similar to (Ma) 2019): an additional reward penalty -0.1 for driving on the grass, a penalty of -0.5 for driving backwards, as well as an early termination if cars spent too much time on grass. These are all used to help terminate less informative episodes. We utilise a memory-lest agent with a frame stacking = and with sticky actions 8. After training the agents randomly generated tracks, assess their robustness previously unseen 20 real-world Formula (F1) tracks designed to challenge professional racecar drivers proposed by (Jiang al. 2021a) and shown in Figure 9
17

---

Published as a conference paper at ICLR 2023
C IMPLEMENTATION DETAILS
In this section, we detail the agent architectures, hyperparameter choices, and evaluation procedures used in our experiments discussed in Section We use PPO to train the student agent in all experiments. Table summarises our final hyperparameter choices for all methods.
All experiments are performed on an internal cluster. Each job (representing a seed) is performed with a single Tesla V100 GPU and 10 CPUs. For each method, we train 10 LaserTag agents for approximately 7 days and 5 MultiCarRacing agents for approximately 15 days.
C.1 LASERTAG
Agent Architecture:
The student policy architecture is adapted from (Dennis et al.) 2020 Jiang
e 202Ta). Our model encodes the partial grid observation using a convolution layer (3 x kernel. stride length 1, 16 filters) followed by a ReLU activation layer over the flattened convolution outputs. This is then passed through an LSTM with hidden dimension 256, followed by two cunle-connected layers, each with hidden dimension of size 32 with ReLU activations, produce the action logits over the possible actions. The model does not receive the agent's s direction as input.
Evaluation Procedure: For each pair of baselines, we evaluate cross-play performance between all pairs of random seeds (10 x 10 combinations) over 5 episodes on 13 human-designed I LaserTag levels, resulting in total of 6500 evaluation episodes for given checkpoint.
Choice of Hy Hyperparameters: Many of our hyperparameters are inherited from previous works such as (Dennis al. 2020 Jiang al. 202 bla a PaarerrHolldrr et al.] (022) with some small changes. We selected the best performing settings based on the average return on the unseen validation levels against previously unseen opponents on least 5 seeds.
We conducted a coarse grid search over student learning rate in (5 * 10-1 10-1 5 10-5,10-9) }. number of minibatches per epoch in {1, 2, 4). entropy coefficients in {0, 10-3, 15=10-3, and number of epochs in {2. 5, 10]. For agent storage, we tested adding a copy of the student agent in the storage after every {2000, 4000, 6000, 8000) student update. For PFSP, we compute the win rate between agents in the last 128 episodes. We further conducted grid search over the entropy parameter of Shord in [1.5, 2,3) 3 and a smoothing constant which adds a small value to each probability in PFSP with {0.1, 0.2) values so that all previous checkpointed agents have a nonzero probability to be replayed again 5) For the parameters of PLR, we conducted grid search over level replay rate p in {0.5, 0.9), buffer size in {4000, 8000, 12000}. staleness coefficient p {0.3, 0.7), as well as the level replay score functions in [MaMMC, PVL) (see Appendix C.3 for information on score functions in PLR). For MAESTRO, evaluated the co-player exploration coefficients in {0.05, 0.1}, and per-agent environment buffer sizes in (500, 750, 1000, 1200).
C.2 MULTICARRACING
The student policy architecture is based on the PPO implementation in (Mal 2019). The model utilises an image embedding module consisting of a stack of 2D convolutions with square kernels of sizes 2, 2, 2, 2, 3, 3, channel outputs of 8, 16, 32, 64, 128, 256, and stride lengths of 2, 2, 2, 2, 1 respectively, resulting in an embedding of size 256. This is then passed through fully-connected layer with a hidden size of 100, followed by ReL.U nonlinearity. Then, the output fed through two separate fully-connected layers, each with a hidden size of 100 and an output dimension equal to the action dimension, followed by softplus activations. We then add 1 to each component of these two output vectors, which serve as the a and parameters respectively for the Beta distributions used to sample each action dimension. We normalize rewards by dividing rewards by the running standard deviation of returns so far encountered during the training.
Agent Architecture:
Evaluation Procedure: For each pair of baselines, evaluate cross-play performance between all pairs of random seeds (5 x 5 combinations) over 5 episodes on 21 OOD Formula tracks Diang et al. (2021a), resulting in a total of 2625 evaluation episodes for a given checkpoint.
Otherwise, if the student agent wins all the episodes in their first encounter against opponent B, B will have 0 prohability of being selected again.
18

---

Published as a conference paper at ICLR 2023
Table 2: Hyperparameters used for training each method in the LaserTag and MultiCarRacing environments.
Parameter
LaserTag MultiCarRacing
PPO
0.995
0.99
ACAE
0.95
0.9
PPO rollout length
256
125
PPO epochs
5
8
PPO butches per epoch
4
4
PPO clip range
0.2
0.2
PPO number of workers
32
32
Adam learning
lc-4
lc-4
Adam
le-5
le-5
PPO max gradient norm
0.5
0.5
PPO value clipping
yes
no
Return normalization
no
yes
Value loss coefficient
0.5
0.5
Student entropy coefficient
0.0
0.0
PLR
Replay rate, Buffer size, K Scoring function Prioritization
0.5
0.5
4000
8000
MaxMC
PVL
rank
rank
Temperature, 3
0.3
1.0
Staleness coefficient, p
0.3
0.7
FSP
Agent checkpoint interval
8000
400
PFSP
fhard entropy coef
2
2
Win rate episodic memory
128
128
MAESTRO
À coef
0.1
0.1
Buffer size for 8 members
1000
1000
Choice of Hyperparameters: Many of our hyperparameters are inherited from (Jingg et al.) 2021a) with some small changes. We conducted a limited grid search over student learning rate in {10 3, 3 10-4), number of actors in {16, 32), PPO rollout length {125, 256}. For agent storage, we tested adding a copy of the student agent in the storage after every {200, 400} student update. For PFSP, we compute the win rate between agents in the last 128 episodes, while recognising the agent with a higher episodic return as the winner. For the parameters of PLR, conducted grid search over level buffer size in (4000, 6000, 8000}. staleness coefficient in {0.3, 0.7), as well as the level replay prioritisation in (rank, proportional) (Jiang et al. 2021a). For MAESTRO, evaluated the co-player exploration coefficients in {0.05, 0.1). and per-agent environment buffer sizes in (500, 1000].
Given the poor performance of random co-player the MultiCarRacing domain, agents are added to co-player populations in MAESTRO as well as FSP- and PFSP-based baselines only after 400 PPO updates. All baselines are trained using SP until that point.
C.3 REGRET APPROXIMATIONS
Jiang et (2021a) proposes the following two score functions to approximate regret in PLR.
Maximum Monte Carlo (MaxMC) mitigates some of the bias of the PVL by replacing the value target with the highest empirical return observed on the given environment variation throughout training. MaxMC ensures that the regret estimate does not depend on the agent's 's current policy. It takes the form of (1/T) En Rmax V(s)).
19

---

Published as a conference paper at ICLR 2023
LaserTag-Eval
LaserTag-Eval Tasks]
0.7
0.2
Cress-Play Return
0.1
0.0
0.0
-0.1
-0.2
-0.2
Updates
Updates
MAESTRO MAESTRO-R MAESTRO-P
Figure 10: Ablation Study Results. Comparing MAESTRO against two variants: MAESTRO-R and MAESTRO-P. Plots show the mean and standard error across 10 training seeds.
Positive Value Loss (PVL) estimates the regret by computing the difference between the maximum achieved return and predicted return episodic basis. When GAE (Schulman et al. 2016) is used to estimate bootstrapped value targets, this loss takes the form of T Ei= max - og, 0)
where and are the GAE and MDP discount factors respectively, and 6, the TD-error at timestep t.
In this work, we MaxMC regret approximation in the LaserTag domain and PVL in MultiCarRac- ing.
D ABLATION STUDY
We perform an ablation study to evaluate the effectiveness of co-player selection MAESTRO from population based their per-environment regret scores, described in Equation ①.. We consider different methods for selecting a co-player in MAESTRO (line 6 in Algorithm [ MAESTRO-R samples the co-player uniformly random, whilst MAESTRO-P uses PFSP's win rate heuristic for opponent prioritisation. Figure illltustrt that MAESTRO outperforms both variants in terms of sample-efficiency and robustness.
E
FULL RESULTS
Agents trained for 40000 PPO updates on LaserTag and 4500 PPO updates MCR.
E.1 MAESTRO VERSUS SPECIALISTS
Figures II and 12
show the cross-play performances between MAESTRO and specialist agents trained directly on the target environments for LaserTag and MultiCarRacing, respectively.
E.2 CROSS-PLE PLASY RESULTS
E.2.1
LASERTAG CROSS-PLAY
14 illustrate the round-robins returns with and without normalization between MAESTRO and other baselines throughout training on each held-out evaluation environment in LaserTag. Figure 15 shows the round-robin returns between MAESTRO and other baselines after the training.
Figures 13
E.2.2 MULTICARRACING CROSS-PLAY
Figure illlstste the round-robin returns between MAESTRO and other baselines each track of the Formula benchmark (Jiang et al., (2021a). Figures 17 18 and Figure 19 show the win rates, returns, and average time on grass during cross-play between MAESTRO and each baseline on Formula benchmark.
20

---

Published as a conference paper at ICLR 2023
LaserTag Tasks]
Ruins
Lasertag
Loce rag Co mondddr Easy N2-v0
059
025
-032
Studerk Updeter
Upcein
dadat Lawet Empty-hi-st
2uder: Updktas
Lasert agg.vellllll (4 Tasbs]
hoa.ttp--eutttom-hh... N2.v0
1a Corritee Eacr- N2-4D
Onw Oww--tr tar
Cre paaam
330
48c
MAESTRO
SP Specialit
PSP Specialit
Figure 11: Cross-play between MAESTRO and specialist agents trained directly on the target environ- ment in LaserTag.
Tasks]
F1-UK-v0
F1-Belgium-vV
F1-Spain-vO
500
Cross-Fay Return
400
Cross-Ray Baturn
800
300
Crozs-Ray
300
200
200
300
100-
Formulag] Tasks]
F1-UK-vO
F1-Belgium-v0
F1-Spain-v0
0.6
PlaysPPayy Winn Rate
0.5
Gross-layy Win Rate
0.6
Cross Play Win Rate
0.7-
0.6-
0.5
0.6-
0.4
0.4
0.5-
0.3
0.3
0.4-
0.3
0.3-
0.
0.1
6.1
0.0
0.0
0.0
0.0
MAESTRO
Specialist
Figure 12: Cross-play between MAESTRO and specialist agents trained directly the target environ- ment in MultCarRacing.
21

---

Published as a conference paper at ICLR 2023
tariin Laseriog Auito
Lasertag Cross
Laneriag Pour Sooms
Lasvetag Cargeaanker
Lasertap Huarod
Lasering Satoenkomms
Laceriig Star
Lasertng Maze?
LoneTagg Maadl
Stader
1CC
MAESTRO
PLR-SP
R+P
PLR+PESP
DR+SP
DR+FSP
DR-PFSP
Figure 13: Normalised round-robin return cross-play between MAESTRO and baselines on all I LaserTag evaluation environments throughout training (combined and individual). Plots show the mean and standard error across 10 training seeds.
Arena
Laserayy Condori
Laseriy Coniter?
Stadeen Updrtie
Stater Upden
Stadine Lit
Stateet Updenes
Shatert
Stbee Updeo
Statee
Shatert Liddee
Loverlag Mandi
6:2
MAESTRO
PLR+SP
PLR+
PIR+PESP
DR+SP
DR+FSP
DR-PESP
Figure 14: Round-robin return in cross- cross-play between MAESTRO and 6 baselines on all LaserTag evaluation environments throughout training (combined and individual). Plots show the mean and standard error across 10 training seeds.
22

---

Published as a conference paper at ICLR 2023
LacerTag Rus (L3 TAKE
Lacetig Carvidrr
Lawercag
Lavercag LargaCor 1927
Leuetiag 14tr2
Loantap Sedeartoors
Loserog
Laseraag Mauci
Loorlay Maxdi
MAESTRO
PLR-SP
PLR+FSP
PLR+PESP
DR+SP
DR+FSP
DR-PFSP
Figure 15: Returns round-robin tournament between MAESTRO and baselines on all LaserTag evaluation environments (combined and individual). Plots show the mean and standard error across 10 training seeds.
Fermul
TLAuabia
1al8 um
71-Srual--2
P2-Gomary--0
P2:Mungayys0
300
Juc
Fl-Auecavu0
F1-Sppliv2
340-
200
MAESTRO
PLR+FSP
PLR+PFSP
DRYSP
DR+FSP
DR+PFSP
Figure 16: Round-robin returns between MAESTRO and 6 baselines on all Formula tracks (combined and individual). Plots show the mean and standard error across 5 training seeds.
23

---

Published as a conference paper at ICLR 2023
Porma LIZL Tasa)
TLAMA JI2V
*Ladgkumm
F5-Crim-00
PL-fracevv
12.Grmanyyo
f2-1hunpary-o0
Fl-tortoon w0
FL V2
P3-UDA-VD
MAESTRO
PLR+SP
PLR+FSP
PLR+PFSP
DR+SP
DR+FSP
DR+PFSP
Figure 17: Win rates in cross-play between MAESTRO vs each of the baselines all Formula tracks (combined and individual). Plots show the mean and standard eтror across 5 training seeds.
24

---

Published as a conference paper at ICLR 2023
22-Gemmaryyv
100
R2Rttherarde--0
P.Prtugsiiv
FL. T2-Aassarv0
F1 T1-Spalvv
Aue
180
MAESTRO
PLR+SP
PLR
PLRIPFSP
DR.SP
DR+FSP
DR+PFSP
Figure 18: Returns in cross-play between MAESTRO vs each of the 6 baselines on all Formula tracks (combined and individual). Plots show the mean and standard error across 5 training seeds.
25

---

Published as a conference paper at ICLR 2023
Australe
um-s0
100
200
TL Tranno-v
Flitarguyys
Tlitabyv0
Medioosn
PC T--onacovvo vO
3100
Pottupsive
Xiee:
sap
F3.05A
MAESTRO
PLR+SP
PLR+FSP
PLRIPFSP
DRiSP
DR+FSP
DR+PFSP
Figure 19: Time on grass during cross-play between MAESTRO vs each of the 6 baselines on all Formula tracks (combined and individual). Plots show the mean and standard error across 5 training seeds.
26


Reviews:
[{"review_id": "yUHUB-odM2", "reviewer": "Reviewer_wyTE", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper proposes Maestro, an open-ended multi-agent learning method that extends UED to the multi-agent setting, combining the benefits of both environment and co-player autocurricula approaches. The work claims to be the first to adequately address the dependency between co-players and environment design when shaping the autocurricula. The theoretical results presented show that Maestro both produces a regret maximizing distribution over environments and co-players and attains Nash Equilibrium in each supported environment. The authors pit Maestro against a cross-product of relevant environment/co-player autocurricula works in the literature, and demonstrate in two diverse environments (grid-world w/ sparse rewards and continuous control w/ dense rewards) that Maestro performs the best in cross-play. Additional supporting results are presented, including analysis of the regret landscapes (highlighting the importance of a curricula over the joint space), evaluation versus specialist agents (demonstrating Maestro’s robustness), and analysis of the emergent curriculum (highlighting interesting qualitative differences between Maestro’s curricula versus the baselines’).  ", "summary_of_the_review": "I vote for this paper’s acceptance. The method is well-motivated, the writing is clear, the results are interesting and compelling, and the findings and resources will likely be of use to the field. ", "strength_and_weaknesses": "Strengths: \n\n* The paper is exceptionally well-written, well-organized, and clear. Care was clearly taken in the formatting too, and the paper is even aesthetically pleasing.  \n\n* The method is well-motivated, and the discussion surrounding related works is comprehensive.\n\n* The method details are described clearly, and useful reference points are provided (e.g. Maestro being a variant of PFSP in fixed singleton environment setting).\n\n* The theoretical results appear to be useful and correct (though I did not read in detail).\n\n* The “illustrative example” is very useful and clearly expresses the motivation. \n\n* The empirical results are compelling and comprehensive, and all of the appropriate baselines (to the best of my knowledge) are included. The results deliver what the method promises, and they also provide more insight into the nature of the problem (via the analysis of the regret landscape) and the nature of the emergent curriculum. The emergent curriculum analysis is very cool (e.g. the wall percentage increasing and grid size decreasing).\n\nWeaknesses:\n\n* None major. \n\n* Typo in middle of 3.2.1 (random section symbol). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "wC7fc5foKZ", "reviewer": "Reviewer_GPFe", "summary": "", "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": "", "summary_of_the_paper": "The paper extends the framework of unsupervised environment design to multi-agent setting and demonstrate its effectiveness on two 2-player competitive games. ", "summary_of_the_review": "This paper addresses an important problem of open-ended learning in a multi-agent setting. While the proposed algorithm seems like a straight forward extension of existing algorithms (PAIRED, PLR, Robust PLR), the authors showed a convincing performance of the proposed algorithm in comparison to all the relevant work. ", "strength_and_weaknesses": "Strengths:\n- Extending the UED to multi-agent setting is an important problem to tackle; and for the chosen environments, the performance of the proposed algorithm was compared with all the relevant work.\n\nWeaknesses:\n- While the authors claim that the proposed framework is applicable to all multi-agent RL settings, the results were shown only on 2-player competitive games. It would add more value to see at least one cooperative setting and one multi-player (more than 2 players) setting.\n- No analysis was provided on the memory complexity or time complexity of the proposed algorithm. These are important because the algorithm maintains an independent replay buffer for each player and with increasing number of players, it also becomes unclear of how the algorithm can effectively simultaneously choose the best policy for each player and environment parameters. Without this analysis, it is unclear if the proposed framework and the algorithm can extend beyond the 2-player setting.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WJZwvBVPiH", "reviewer": "Reviewer_AFZu", "summary": "", "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": "", "summary_of_the_paper": "This paper investigates learning training agents in games where nature samples the games initial state before play. In such a games certain strategies may be at an advantage when the settings play into their strengths. Present methods consider the performance of each strategy with respect to an approximate expectation of the initial state sampling distribution. This work looks at game solving while taking into account the distribution of game settings. Specifically, they propose a population based-training regime where iteratively a policy is optimized to perform well against each coplayer strategy in the worst-case (where buffers of game configurations are used to approximate the game distribution). They demonstrate their approach on a discrete laster-tag gridworld and a continuous racing game.", "summary_of_the_review": "The paper introduces an intuitively nice idea and offers some reasonable empirical analysis of the method. However, I am not convinced that the theoretical results apply to the method, and am suspicious that about the empirical results and that the algorithm's namesake is only a footnote at the end of the paper. \n\nI think with some minor edits and additional empirical results this paper could be ready for publication. ", "strength_and_weaknesses": "**Strengths**\n - I have never seen an approach that explicitly accounts for regret with respect to nature and I think that the idea is straightforward and nice.\n - The authors include reasonable ablations of the game instance generation methods as evidence supporting that regret-based prioritization is empirically advantageous. \n\n\n**Weaknesses**\n - While the idea has a nice intuitive appeal, it's not clear to me that maintaining buffers for the highest-regret game instances is the most sensible. If these settings rarely if ever occur in practice (or under the evaluation distribution) then your learned strategy may compromise its performance in general for these rare cases. \n - Could the authors explain how the proposed theoretical guarantees of Maestro (convergence to BNE) hold when it relies on an expectation over game instances and in practice a highly bias discrete sample of these instances is accounted for? It seems to me that there is an important gap and that the authors should make this clear within the paper.\n - The authors name their algorithm in the style of Policy-Space Response Oracles (PSRO) a general game solving algorithm. Despite this, only PSRO's predecessors are extended (FP, FSP) to adtop their extension when PSRO can naturally be extended in the same way. This is an odd gap that makes me suspicious as a reader. Did the authors try this and it not work? \n - Minimum expect return is an atypical measure of performance for the game solving methods. Could the authors please comment on the regret and the coplayer return as it relates to the relative performance of each method. It seems this measure may lend advantage to the method introduced as it optimizes for the worst-case game instances.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster