Genetic Algorithm for Curriculum Design in Multi-Agent Reinforcement Learning
Authors: Yeeho Song
Jeff Schneider
Venue: CoRL 2024 (2024)
Keywords: Reinforcement Learning
Multiagent Learning
Curricular Learning

Abstract: As the deployment of autonomous agents in real-world scenarios grows, so does the interest in their application to competitive environments with other robots. Self-play in Reinforcement Learning (RL) enables agents to develop competitive strategies. However, the complexity arising from multi-agent interactions and the tendency for RL agents to disrupt competitors' training introduce instability and a risk of overfitting. While traditional methods depend on costly Nash equilibrium approximations or random exploration for training scenario optimization, this can be inefficient in large search spaces often prevalent in multi-agent problems. However, related works in single-agent setups show that genetic algorithms perform better in large scenario spaces. Therefore, we propose using genetic algorithms to adaptively adjust environment parameters and opponent policies in a multi-agent context to find and synthesize coherent scenarios efficiently. We also introduce GenOpt Agent—a genetically optimized, open-loop agent executing scheduled actions. The open-loop aspect of GenOpt prevents RL agents from winning through adversarial perturbations, thereby fostering generalizable strategies. Also, GenOpt is genetically optimized without expert supervision, negating the need for expensive expert supervision to have meaningful opponents at the start of training. Our empirical studies indicate that this method surpasses several established baselines in two-player competitive settings with continuous action spaces, validating its effectiveness and stability in training.

Genetic Algorithm for Curriculum Design in Multi-Agent Reinforcement Learning
Yeeho Song"
Jeff Schneider School Of Computer Science Carnegie Mellon University United States America jeff 4 andrew. cmu, edu
School of Computer Science
Carnegie Mellon University United States America yeehos @anheww....d......ooo..... cmu. edu
Abstract:
As the deployment of autonomous agents in real-world scenarios grows, does the interest in their application to competitive environments with other robots. Self-play in Reinforcement Learning (RL) enables agents to develop competitive strategies. However, the complexity arising from multi-agent interactions and the tendency for RI. agents to disrupt competitors' training introduce instability and a risk of overfitting. While traditional methods depend on costly Nash equilibrium approximations or random exploration for training scenario optimization, this can be inefficient large search spaces often prevalent in multi-agent problems. However, related works single-agent setups show that genetic algorithms perform better in large scenario spaces. Therefore, propose using genetic algorithms adaptively adjust environment parameters and opponent policies in multi-agent context to find and synthesize coherent scenarios efficiently. We also introduce GenOpt Agent- genetically optimized, open-loop agent executing scheduled actions. The open-loop aspect of GenOpt prevents RI. agents from winning through adversarial perturbations, thereby fostering generalizable strategies. Also, GenOpt is genetically optimized without expert supervision, negating the need for expensive expert supervision to have meaningful opponents at the start of training. Our empirical studies indicate that this method surpasses several established baselines in two-player competitive settings with continuous action spaces, validating its effectiveness and stability in training.
Keywords: Reinforcement Learning, Multiagent Learning, Curricular Learning
Introduction
Competitive multi-agent reinforcement learning (RL) has gained interest for its potential in various fields, such as gaming, robotics, finance, and cybersecurity, where agents need to outperform others. To discover new competitive strategies, self-play is often used to explore the environment with RL agents. Most self-play algorithms train ego agents against population of opponent policies to avoid overfitting to specific opponent. [1, 2, 3].
When training against a population policies, selecting the policies most useful for training chal- lenging. Some works use game-theoretic methods select opponents [4. 5]. but finding approximate Nash Equilibria in setups with large search spaces is costly. Others curriculum learning to select opponent policies [6], but relying random sampling find candidates is not scalable with large search spaces. Therefore, we propose using genetic algorithms, which have proven efficient for searching and generating scenarios with large scenario spaces in single-agent domains [7].
Another issue with ell-play training instability due the adversarial vulnerability RL policies [8, 9, 10). RL agents often overfit to specific opponent's weakness, resulting in non-generalizable
"eehos @ andrew.cmu.edu, Robotics Institute
8th Conference Robot Learning (CoRL. 2024), Munich, Germany.

---

behaviors, For example, when training against mujoco-any ant agent trained to play sumo [11], agents would learn to win by waving their legs to confuse the opponent, instead of the non-trivial solution of pushing the opponent. Exploitation destabilizes self-play, especially during the initial phases when the opponent's policy is underdeveloped. Initiating opponents with expert demonstrations [3] to avoid this issue can be costly. We, therefore, introduce GenOpt Agents, which are environment-agnosee open-loop agents optimized by genetic algorithms to match the performance of the ego agent.
To summarize, our approach utilizes genetic algorithms to efficiently search and generate an optimal training curriculum in expansive search spaces, while GenOpt Agents improve training stability. An ablation study provides insights into our methodology 's effectiveness and design choices. Figure summarizes our approach. Supplementary information and codes can be found in https:/ g thub. com wwweeeeeee//eeeeeeeeeeeee Becchhos//Eneeee /eeeeGEnntttteeeeeeeeeeeeeeeeeee C- agent Se fp av. qit
Generatee a poputation high regret scenarios
Scenario
Curriculum Generator
Ego Student Agent
X
Reports losal and regnet
Choice of Opponent
Gen Agent Script
Trains Scanario
Environment Description
Periodically copies checkpoints to opponant population
opponent
Co-Player
Population
Overview of our proposed approach: During training, the ego student agent is trained against scenario describing the choice of opponent, action script for the GenOpt Agent, and the choice of environment parameters. Our curriculum records regret and win/lose/tie outcomes for each scenario. Based the performance of the scenarios in the previous population, our curriculum generator uses genetic algorithm to generate new population of scenarios to be used to train the agent for an epoch each fixed interval of steps.
Figure 1:
Related Works
Game Theoretic Approach to Self-Play
Training an RL agent competitive multi-agent environments requires an opponent. Unlike rule- based opponents [12] expert demonstrations [13], self-play [14, 15] agents autonomously explore and discover competitive behaviors. However, training against only one RL opponent can suffer from the instability of opponent behavior changing over time and ego agent overfitting to specific policy [16]. Therefore, Fictitious Self-Play (FSP) [17, 18, I] proposes to train against population of opponents. In deep RL, this opponent library is often compiled by saving checkpoints of the ego policy during training [3, 19].
Expanding these findings, game theoretic approaches like Policy Space Response Oracle (PSRO) [4, 3, 19] utilize Nash equilibrium [5], stable point in multi-agent game where no player can unilaterally change their strategy to improve their payoff. PSRO calculates an approximate Nash strategy to determine the mixture of checkpoints to load as opponents. However, computing an approximate Nash strategy can be computationally intensive the policy space is large. Moreover, effectively learning policies complex, non-stationary, and partially observable multi-agent environ- ments remains significant challenge. While some approaches use ensemble learning split the learning task [20] [21], they limited simpler, discrete action setups. This paper approaches this issue with a curricular viewpoint.
Curricular Reinforcement Learning
When it comes to learning policy for difficult problem, Curricular RL suggests that agents can learn faster by first being exposed to simple tasks and scenarios and gradually progressing similar but slightly more difficult tasks. [22, 23, 24, 25, 26, 27, 28, 29, 30, 31].

---

Various papers explore curriculum optimization in the single-agent domain, such as Bayesian Opti- mization [32], teacher agents [33], and genetic algorithms [34, 35, 36). Genetic operations make scenarios similar to each other, thus achieving curriculum learning by facilitating the transfer of skills. Many genetic approaches rely on mutations, which make small alterations to the encoding of a scenario, in order to populate curriculum with similar scenarios.
On the contrary, the Genetic Curriculum (GC) [7] uses population wide genetic operations, such as crossover, for curricular RL. Crossover involves merging sequences encoding across population, helping the transfer of skills within the curriculum by enhancing similarity among the scenarios. While successful in generating an effective curriculum a large scenario space, GC requires costly evaluation steps to validate scenarios. Additionally, GC cannot regulate scenario difficulty.
One way to regulate difficulty is regret, which quantifies the gap between the current obtained return with the maximum possible return on the scenario. Showing success in various single- agent domains [37, 38), regret has been applied to curriculum learning in a multi-agent setup by Multi-Agent Environment Design Strategist for Open-Ended Learning (MAESTRO) [6]. While MAESTRO introduced optimization of both environmental parameters and opponent selection to limited by relying on domain randomization to uncover new scenarios. Studies in GC [7] suggest this can lead suboptimal performance. Unlike those generated by population wiide genetic operations, scenarios generated by domain randomization may not be similar to each other, making transfer of skills difficult and learning slow. We, therefore, combine both population-wide genetic operations with regret regulation for multi- curriculum generation.
guarantee robustness,
Open-Loop Opponents for Multi-Agent Self-Play
Self-play can be unstable, especially at the beginning of training when the opponent is not well-trained to make effective moves in the game. While some approaches involve hand-crafted opponents [3) or agents trained via imitation learning from expert data [39], such supervision can be costly.
No-OP (No Operation) agents [40], which do not take any actions, can reduce the need for expert supervision. However, their simple and limited behavior limits the approach certain types of environments. For instance, walking robot will fall if there is no torque in the joints, while a plane with no control input will eventually crash by losing speed and altitude due to drag. Our GenOpt addresses such issues by introducing agents that take optimized actions.
Approach
3.1 Preliminaries
An RL problem setup is typically represented as a tuple in Markov decision process: [S, A, P, r; 7]. where the state space of a problem, A is the action space, P is the transition dynamics, is the return state-action pair, and y E [0, 1) is the temporal discount factor. The agent's policy, to actions denoted J(x) E. Σ f ((s)). During training, an RI. algorithm optimizes the policy with respect to the data has collected.
Taa s), maps states
A. The utility of a policy is the expected return
In our multi-agent setup, we consider that the utility of a policy is dependent on both the opponent's policy Topp and the environment b denoted as JTTego Topp: v). At each epoch consisting of fixed number of time steps, we save the current version of our ego agent and add it to the library of possible opponents choose from Hopp- We describe the environment with parameters, vi. We define scenario & as an opponent policy environment pair: & {Tppp J. The goal of our curriculum generator at given timestep is to generate population of scenarios, Etrain = {Eo, & } where optimizing the ego policy Tego with respect to the curriculum Etrain will result in policy with the behaviors we desire.
n
max J( Strain)
n
3.2 Problem Formulation
For the multi-agent setup, we want our algorithm to continuously explore the game by visiting scenar- ios that it does not do well to leam new competitive behaviors. We design curriculum generator around this idea by first formulating multi-agent learning zero-sum game G(Tego: 3 between
3

---

the Tego and the curriculum generator. Ge {) if Tego wins the scenario &, G {) = 0 if was tie, and Gego { = -1 if loses. The opponent Tppp and the environment parameters 3 are determined by the curriculum's 's scenario Ç. The solution for a finite zero-sum two player game is minimax;
G
min max G((T Peyo
Therefore, our curriculum generator will generate a population E that minimizes (T E)
Crossover
3.3 Genetic Algorithm for Curriculum Generation
Parent Scanario Encoding
Child Scenario Encodings
In this section and onward, we explain how our proposed algorithm, GEnetic Multi-agent Self-play (GEMS), as de- scribed in Algorithm 1, generates curriculum.
Mutation
To generate curriculum, GEMS uses genetic algorithm due to its proven efficiency in large scenario spaces and its flexibility in scenario encoding. At the beginning of the training, as in Line 5 of Algorithm 1, GEMS randomly initializes curriculum Etrain- Tego trains on the Etrain for an epoch consisting of a fixed number of steps. For
Figure Visualization of crossover and mutation. Crossover replaces encoded segments between two parent scenarios. Mutation changes an encoded segment of parent with a random sequence.
each scenario, our algorithm records whether the agent has won, lost, or tied, along with the regret estimated by positive value loss [37, 41].
At the end of each epoch, GEMS harvests scenarios from the current curriculum to generate the next curriculum as in line 14 of Algorithm 1. The fitness function, p(E), defines the probability of a scenario being harvested. Since the GEMS is trying to minimize G(Tego; E) of the generated curriculum, fitness proportional to (1 G <)). At the same time, GEMS needs to generate scenarios with high information potential, measured as regret, 8(E). Therefore, fitness is set as p(g) (1 (Teeoo {)).
From these harvested scenarios, GEMS uses crossover and mutation (see Figure 2) to create an offspring population consisting of sequences of similar to the ones harvested. Crossover occurs when the algorithm takes a random segment from one parent scenario encoding and swaps it with a random segment from another parent scenario encoding. The mutation when the algorithm selects a random segment from a parent scenario encoding and swaps it with a segment from randomly generated scenario encoding. Scenarios Çs generated by the genetic algorithm will inherently be similar, aiding in the transfer of skills and, consequently, a faster rate of convergence when used as curriculum. Detailed operations for crossover and mutation are shown in Appendix E.
Unlike GC, which has separate evaluation steps, GEMS calculates fitness from the performance measured during training, reducing the computational cost. In addition, GEMS regularizes difficulty.
3.4 GenOpt Agent and Scenario Space
Self-play in deep RL often suffers from training instability due ego agents exploiting the adversarial vuinerability of the opponents. While using open-loop agents mitigate this issue, previous approaches used expert supervision to design open-loop behaviors, which can be costly [40]. To allow an open-loop agent that continuously evolves to match the ego agent's performance during training without expert supervision, we introduce GenOpt Agent, denoted as Te, that optimizes open-loop behaviors using genetic algorithms without supervision.
To {(o,, au), (t1,a1), (f2, o2)..... encodes the opponent a list of non-fixed lengths describing which actions to take in an open-loop fashion. For example, at timestep 4 < t < l2, the opponent takes action 01. As genetic algorithms can be agnostic to the length of encoding, the encoding length does not need to be pre-specified and is optimized by the curriculum generator without expert supervision. GenOpt's open-loop nature makes it less vulnerable to opponent- opponent-induced induuced confusion, but unlike No-OP, GenOpt competitively optimized to match the ego agent's 's performance, enhancing its applicability across diverse environments.

---

Using the features above, GEMS encodes a scenario as Ç = {iz, TØ. 3 i, is an integer representing the i-th checkpoint to load as the opponent т opp-- If iz- = 0, it indicates that no agent will be loaded, and instead, a GenOpt Agent &e will be used as the opponent. &b denotes which environment parameters to load. It should be noted that whether is used or not, the encoding for the GenOpt Agent Te is always present in a scenario Ç. This ensures that the optimization and the memory about GenOpt Agent z are not lost during the genetic operations and can always be brought back if needed throughout the training.
Experiments
4.1 Benchmarks
Pong
Volley
ACM
Ant
Simple
Adversary
Figure 3: Screenshots of Pong, Volley, ACM (dots marking trajectories), Ant, and SidereAAvvessary
Algorithm GEnetic -ulti- Self-play
We evaluate our algorithm in Pong, Volley,
ACM, Ant, and SivpreAdversay to assess its
Initialize Policy Tego
performance in different levels of complexity.
2: #Select size of curriculum, Merain
3: # #Select mutation rate, Pp
More environment details are in Appendix B.
4: Input Merain, Py
Pong is 2-player, continuous-action space version similar to Atari Pong [42]. Each player controls a paddle to hit a ball back and forth, aiming to score by getting the ball past the opponent. The scenario set the players' sides and the ball's initial velocity. Simple 11:
5: Initialize Curriculum Etrain
6:
while True do outcome regrets =
7:
# Train т with Etrain by exploring scenario E for & in Strain do
8:
9:
G(m, , d Train(Tegos E) seecome.append(((G) regrets.append(6)
10:
{))
1-D movement and fixed horizontal ball speed
12:
end for
13:
Harvest Examples
focus make dynamics easy to learn and rela-
14:
Exred, utility haaresefEmmmaas.uuucnnnnerrrrr
tively emphasize the game-theoretic aspect of the solution more than other benchmarks.
15:
#Generute New Curriculam
16:
Etrain = Eeess
17:
Strai = mutation (ariiionnEtranna
Etresn Pμ)
Volley is based on [43]. Each player uses 18:
save(Tegg.) # #Regllarly save checkpoint
continuous action input to control an avatar, 19:
end while
moving left, right, and jumping. The goal is to bounce the ball to land the other side of the map across the net. The scenario specifies the players' sides and the initial ball velocity. Volley incorporates gravity, elastic collisions, and a net, increasing complexity and skill requirements.
ACM is a simulated dogfighting environment. Each player flies an airplane in 3D space, aiming to position nose toward the opponent without crashing to the ground. The scenario describes the spawning airplanes' positions, postures, and velocities. With physics simulated by JSBSim [44], high-fidelity simulator widely adopted in autonomous aircraft and aireraft controls research due to its accurate acrodynamic modeling [45], and direct control over the aircraft operating in 3D space with no stability assist, ACM is a complex environment that needs well-trained skills to master the game with non-linear dynamics. Additionally, since the game's objective is to maneuver and position the ego plane in relation to the opponent, the scenario, encoding spawn locations and orientations of the planes, significantly influences the game's outcome. ACM tests whether algorithms are robust when environmental factors outside their control give an unfair advantage one of the agents.
Ant is a simulated Mujoco environment based on OpenAl's Competitive Gym environment. [11]. The game's 's goal is to flip the opponent or push the opponent out of the ring. Ant challenges the agent to learn multiple different skills to master the game. For example, while ramming is often the only way to win an opponent that stands still, those who ram are vulnerable to those who flip the opponent. However, flipping is not helpful against opponents that stand still, as an opponent keeping all its legs on the ground leaves no room for flipping. The agents must learn various skills and know how mix and use them to win game. To the best of our knowledge, we are the first paper to solve the Ant problem by training from scratch without expert supervision pretrained weights.
5

---

SimpleAdversary is a Multi Particle Environment from [46]. As in the Figure 2, the environment features one adversary (red), two good agents (blue), and two landmarks (green and black). Agents are rewarded based on their proximity to the target landmark, with opposing goals for good agents and the adversary. Only good agents know the target's location. SimpleAdversary tests offers asymmetrical environment with goals, action and observation space being different per role, along with added challenge of collaboratiee-compttite settings with multiple agents.
4.2 Baseline Algorithms
We use PSRO as one of the baselines for comparison. While many algorithms have emerged from PSRO, such as Rectified PSRO [47], Pipeline PSRO [48], or Anytime PSRO [49], these are fundamentally based on PSRO's framework. They share the underlying structure of generating Nash strategy opponents without considering the ego agent's performance to present the tasks in gradual, easy-to-learn fashion. Therefore, utilize PSRO as characteristic example highlight the limitation of this assumption. While PSRO necessitates additional steps evaluate each policy to run the meta-solver during training, we report performance without considering the extra evaluation steps that PSRO requires. We believe that presenting PSRO's performance without factoring in these additional steps provides a comprehensive comparison, not only against PSRO itself but also against newer subsequent algorithms such as XDO [50] and NAC [51], which aim to reduce the computational cost associated with policy evaluation.
We include GC [7] as comparison against approaches that use genetic algorithm to generate a curriculum. We include SPDL [26] to compare our approach against algorithms controlling environment parameters and actively regulating difficulty levels during curriculum generation. For faimess in the multi-agent domain, GC and SPDL. are running with Fictitious Self-Play (FSP) [1], labeled GC+FSP and SPDL+FSP, where the curriculum generator can choose opponents from saved checkpoints. While other single-agent curricula RL regulate difficulty levels, such as using regret, we decide to MAESTRO represents state-of taae-of-theeart approach to optimizing euvironment-opponcee choices in the multi-agent domain using regret to regulate the difficulty level of the scenarios. Finally, we include FSP as a baseline comparison for simple population basod multi-agent RL. FSP loads environmental parameters by domain randomization.
approach more relevant to the multi-agent domain by including MAESTRO [6].
For all algorithms, we use publicly available implementation of Soft Actor Critic (SAC) [52, 53] and Proximal Policy Optimization (PPO) [54, 55) the base strategy explorers.
4.3 Evaluation and Hyperparameters
We conduct experiments to evaluate each method's effectiveness using ten random seeds for Pong, Volley, and for the more complex ACM and Ant benchmarks. The training duration varied from to 15 days, with computationally intensive algorithms like ACM requiring the most time. Given the impracticality of exploitability analysis in complex environments, performance was assessed through competitions against five baselines and GEMS across 200 games with randomized environment parameters, utilizing Round Robin format for both interim (every 2.5e5 timesteps for SimpleAdversarry every 5e5 timesteps for the rest) and final evaluations. Ablation studies were performed with five seeds to validate our design decisions further, comparing ablated models against fully trained baselines.
While PSRO, GC, and SPDL involve additional simulation steps for curriculum generation, we report results based the exploration steps taken by each agent for easier comparison. We train each algorithm for 7e6 steps in each benchmark, and 3.5e6 steps for the SimpleAdversary. See Appendix B for implementation details and hyperparameter tuning results.
5 Results
5.1 Round Robin Results
As summarized by the round robin results in Table 1, Our approach outperforms all baselines in the win and lose rates across benchmarks. See Appendix A for comprehensive results.

---

Pong
Volley
ACM
Ant
SimpleAAversary
FSP
59: 1: 39
10:5:55 55
37: : 14
38
28
34
50:0:50 50
PSRO
56: 4:
40:5:55
35:51:
37: 42
53: 0:
GC+FSP
58:1:42 46:7:47
23:34:43
36:24:30
49:0:51
SPDL+FSP
31:0:69
:7: 28
28:
37:21:
46:
MAESTRO
21:0:79
42:6:52 52
10:23:67
34:
22:22::
49:0:51
GEMS
32:3:25
48
24: 28
:2:8
44
36:
21
53: 0::47
Table 1: Mean Win:Tie:Lose Ratio (%) of algorithms against baseline algorithms and ours (GEMS). In bold are the statistically significant highest win rates and lowest lose rates.
While MAESTRO performs comparable to FSP in Volley, it does not perform well other bench- marks. GC [7] suggested that relying on random exploration instead of curriculum generation can be limiting. We will confirm that this limitation extends the multi-agent setup our ablation study.
While PSRO performs well in Pong, where dynamics are simple and approaching theoretcaee so- lutions is relatively more important, PSRO's s effectiveness diminishes in more complex environments like Volley, ACM, and Ant. This highlights the significance of a curriculum that aids in learning new skills against broad spectrum of opponents. Also, while PSRO's game theoretic approach allows outperform most of the baselines an asymmetrical setup such as SimpleAdvesary, shown in Table 4, our GEMS outmatches PSRO via flexible architecture applicable to such setups well.
Despite both being curricular methods, GC+FSP and SPDL+FSP exhibit different performances. SPDL+FSP can regularize scenario difficulty and outperforms GC+FSP more complex envi- ronments such as Volley, ACM, and Ant compared to PONG. GC+FSP, on the other hand, has robustness guarantee unlike SPDL+FSP, and outperforms SPDL+FSP simple benchmarks such as Pong, where difficulty regularization is not important. However, both suffer from ACM benehmark neither designed for multi-agent setups.
MAESTRO's s performance is comparable to FSP in Volley but is less effective in other benchmarks, especially in ACM and Ant. This highlights the limitations of relying on random exploration in expansive scenario spaces. Our ablation study further supports this finding in the multi-agent context.
5.2 Evolution of Generated Curriculum
Start Training
Middle Training
Training
1907
Figure 4: Evolution of scenarios generated by our GEMS. Each dot marks the position of red and blue aircraft at I-second intervals. The color of the markers starts from black to blue for student aircraft and black to red for the opponent aircraft.
To demonstrate the curriculum evolution, Figure 4 shows characteristic scenarios generated at 1e6, 3e6, and 7e6 steps with the ACM benchmark. Initially, to accommodate the untrained ego agent, our algorithm generates GenOpt that spawns close and circles around the ego agents, offering non-trivial and easy opponents for the ego agent practice basic tracking. As the training progresses, our GEMS starts to generate scenarios with interesting learning examples, such as the opponent chasing the ego agent for head-on pass. This gradual complexity increase enables the agent to tackle complex situations by training's end, such as a much longer chase shown in the figure. For extensive visualizations and comparisons, see Figure 7 in the appendix.
5.3 Ablation Study
7

---

Ablation Results for ACM
We conduct an ablation study on our GEMS to demon- strate the empirical effects of our design choices. NoRe- gret experiment excludes the regret term (6) when calcu- lating the fitness function to observe how effectively regret regulates the difficulty level of scenarios during training. NoGenetic experiment employs the approach of MAE- STRO [6] instead of using genetic algorithm to generate scenario population. Scenarios are individually selected from a replay buffer, and new scenarios are added through a random search, deviating from the batch generation a genetic algorithm. NoCrossover experiment disables the crossover function of the genetic algorithm, relying solely on mutation for scenario search. NoGenOpt experiment disables the option to use a GenOpt Agent during training. NoVic experiment disables the fitness function from utilizing (Tego +)), focusing solely on maximizing regret. Lastly, No-OP replaces GenOpt Agents with No-OP agents, which takes no actions.
Mean Cumulative Reward
GEMB
Mettogret
NoGentOpt
-200
NcCroesover
exploration steps
Figure 5: Ablation study training curve
While NoRegret initially mirrors GEMS in training performance, plateaus earlier. This marks that while regret becomes crucial for adjusting curriculum difficulty towards equilibrium, its impact on training efficacy is less significant compared to GEMS's other design features.
One key aspect of GEMS is the use of genetic operations.
MAESTRO
226.845+22.3333 139.080=32.768
GC [7] showed that genetic algorithms outperform random exploration in single-agent settings by efficiently identifying challenging scenarios similar to each other, facilitating ef- fective task generation. The ablation study shows that this advantage also applies to the multi-agent domain, where solely relying mutation (NoCrossover) is more effective than random exploration (NoGenetic).
GEMS
NoRegret NoGenetic
128.416+114.724
2.44.64--9.595
NoCrossover
75.808
No
16.62267=16.605
NoGenOpt
-213.551
No-OP
-243. 173.172218.521
Table 2: Mean return of the ablation study ACM benchmark.
However, beyond difficulty regularization by regret, GEMS
has several useful features for multi- agent training. One such the GenOpt Agent, which provides non-trivial open-loop agents without expert supervision. Compared to the No-OP approach, which involves agents taking no actions, the ablation study shows that training with GenOpt is better. In the ACM environment, for instance, an uncontrolled aircraft's inevitable energy loss leads to a crash. The GenOpt Agent, on the other hand, addresses this issue by providing a sophisticated sequence of actions optimized by the curriculum generator, thereby ensuring sustained engagement and challenge.
Finally, NoVic underscores the critical role of Nash equilibrium in our zero-sum game formulation between the curriculum generator and the ego agent. Unlike NoRegret, No Vic exhibits inferior performance, illustrating that while regret contributes to curriculum generation, G'(Tegor vb) is pivotal for ensuring training stability and effective curriculum optimization.
6 Conclusion
This paper proposes using genetic algorithm to improve and stabilize learning in multi-agent environments. Using the strength of genetic algorithms to generate curriculum in a large scenario space, enable RL agent to reach better solution faster. We also introduce GenOpt Agent, an open-loop agent optimized by the curriculum generator without expert supervision. This enhances training stability, which is especially valuable early on when the self-play opponent lacks sufficient competence. Empirical results across multiple benchmarks show our method outperforming various basclines, and an ablation study further confirms the significance of our design decisions.
7 Limitations and Future Works
Similar to MAESTRO [6]. our method currently lacks provable guarantee for convergence to the Nash equilibrium in games. This presents an opportunity to identify conditions under which guaranteed convergence can be achieved.
8

---

Acknowledgments
This work was partly funded by The Boeing Company.
References
[1] Heinrich, M. Lanctot, and D. Silver. Fictitious self-play in extensive-form games. In International conference on machine learning, pages 805-813. PMLR, 2015.
[2] J. Heinrich and D. Silver. Deep reinforcement learning from self-play in imperfect-innformation games. 2016.
[3] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, Ewalds, Georgiev, et al. Grandmaster level starcraft using multi-agent reinforcement learning. Nature, 575(7782):350-354 2019.
[4] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and T. Graepel. A unified game-theoretic approach to multiagent reinforcement learning, Advances in neural information processing systems, 30, 2017.
[5] Nash Equilibrium points in n- n-person games. Proceedings of the national academy of sciences, 36(1):48-444 1950.
[6] M. Samvelyan, A. Khan, M. D. Dennis, M. Jiang, J. Pooder- J. N. Foerster, R. Raileanu, and T. Rocktäschel. Maestro: Open-ended environment design for multi-agent reinforcement learning. In The Eleventh International Conference on Learning Representations.
[7] Y. Song and J. Schneider. Robust reinforcement learning via genetic curriculum. In 2022 International Conference Robotics and Automation (ICRA). IEEE, 2022.
[8] C. Yu, B. Han, L. Shen, J. Yu, C. Gong, M. Gong, and Liu. Understanding robust overfitting of adversarial training and beyond. International Conference on Machine Learning, pages 25595-2566 22610. PMLR, 2022.
[9] Y. Liang, Y. Sun, R. Zheng, and F. Huang. Efficient adversarial training without attacking: Worst-case-aware robust reinforcement learning. Advances in Neural Information Processing Systems, 35:22547-22561, 2022.
[10] L. Rice. E. Wong, and Z. Kolter. Overfitting in adversarially robust deep learning. In Interna- tional Conference Machine Learning, pages 8093-8104. PMLR, 2020.
[11] T. Bansal, J. Pachocki, S. Sidor, I. Sutskever, and I. Mordatch. Emergent complexity via multi-agent competition. In International Conference on Learning Representations, 2018.
[12] G. H. Burgin and L. Sidor. Rule-based air combat simulation. Technical report, 1988.
[13] D. Chen, V. Koltun, and P. Krähenbühl. Learning to drive from world on rails. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15590-15599, 2021.
[14] G. Tesauro al. Temporal difference learning and td- id-gammon. Communications of the ACM, 38(3):58-68, 1995.
[15] D. Silver, T. Hubert, J. Schritwieser,, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L.. Sifre, D. Kumaran, T. Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 14001144, 2018.
[16] M. Garnelo, W. M. Czarnecki, S. Liu, D. Tirumala, Oh, G. Gidel, H. van Hasselt, and D. Balduzzi. Pick your battles: Interaction graphs population-level objectives for strategic diversity. arXiv preprint 210.042110.04441, 2021.

---

[17] G. W. Brown. Iterative solution of games by fictitious play, Act. Anal. Prod Allocation, 13(1):
374, 1951.
[18] D. S. Leslie and E. J. Collins. Generalised weakened fictitious play. Games and Economic Behavior, 56(2):285-298, 2006.
[19] C. Berner, G. Brockman, B. Chan, V. Cheung, P. Dębiak, C. Dennison, D. Farhi, Q. Fischer, S. Hashme, C. Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06666 2019.
[20] M. O. Smith, T. Anthony, and M. P. Wellman. Iterative empirical game solving via single policy best response. arXiv preprint arXiv:2106.0199) 2021.
[21] M. O. Smith, T. Anthony, Y. Wang. and M. P. Wellman. Learning to play against any mixture of opponents. arXiv preprint arXiv:2009. 14/80, 2020.
[22] C. Florensa, D. Held, X. Geng, and P. Abbeel. Automatic goal generation for reinforcement learning agents. In International conference machine learning, pages 1515-1528. PMLR, 2018.
[23] C. Florensa, D. Held, M. Wulfmeier, M. Zhang, and P. Abbeel. Reverse curriculum generation for reinforcement learning. In Conference on robot learning, pages 482-495. PMLR, 2017.
[24] S. Narvekar and P. Stone. Learning curriculum policies for reinforcement learning. In Pro- ceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, pages 25-33. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
[25] B. Ivanovic, J. Harrison, A. Sharma, M. Chen, and M. Pavone. Barc: Backward reachability curriculum for robotic reinforcement learning. In 2019 International Conference Robotics and Automation (ICRA), pages 15-21. IEEE, 2019.
[26] P. Klink, C. D' D'Eramo, J. Peters, and J. Pajarinen. Self-paced deep reinforcement learning. In NeurlPS, 2020.
[27] R. Portelas, C. Colas, K. Hofmann, and P.-Y. Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments. In Conference Robot Learning, pages 835-853, PMLR, 2020.
[28] M. Dennis, N. Jaques, E. Vinitsky, A. Bayen, S. Russell, A. Critch, and S. Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Advances in neural information processing systems, 33: 13049-13611,, 2020.
[29] Q. Long, Z. Zhou, A. Gupta, F. Fang. Y. Wu, and X. Wang. Evolutionary population curriculum for scaling multi-agent reinforcement learning. arXiv preprint wwXh::2003./0423 2020.
[30] F. L. Da Silva and A. H. R. Costa. A survey transfer learning for multiagent reinforcement learning systems. Journal of Artificial Intelligence Research, 64:645-7003 7035,00,325 2019.
[31] S. V. Albrecht and P. Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258:66-95, 2018.
[32] S. Paul, M. A. Osborne, and S. Whiteson. Fingerprint policy optimisation for robust reinforce- ment learning. In International Conference Machine Learning, pages 5082-5091. PMLR, 2019.
[33] Y. Du, P. Abbeel, and A. Grover. It takes four to tango: Multiagent selfplay for automatic curriculum generation. arXiv preprint 1rX1v:2202.10608 2022.
[34] R. Wang, Lehman, J. Clune, and K. O. Stanley. Poet: open-ended coevolution of environments and their optimized solutions. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 142-151, 2019.
10

---

[35] R. Wang. J. Lehman, A. Rawal, J. Zhi, Y. J., Clune, and K. Stanley, Enhanced poet: Open- ended reinforcement learning through unbounded invention of learning challenges and their solutions. In International Conference on Machine Learning, pages 9940-9951. PMLR, 2020.
[36] D. Howard, H. Munn, Dolcetti, J. Kannemeyer, and N. Robinson. Assessing evolutionary terrain generation methods for curriculum reinforcement learning. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 377-384, 2022.
[37] M. Jiang, M. Dennis, J. Parker-Holder, J. Foerster, E. Grefenstette, and T. Rocktäschel. Replay- guided adversarial environment design. Advances in Neural Information Processing Systems, 34:1884-188 1897, 2021.
[38] Parker-Holder, M. Jiang, M. Dennis, M. Samvelyan, J. Foerster, E. Grefenstette, and T. Rock- täschel. Evolving curricula with regret-based environment design. In International Conference on Machine Learning, pages 17473 17498. PMLR, 2022.
[39] J. Won, D. Gopinath, and J. Hodgins. Control strategies for physically simulated characters performing two-player competitive sports. ACM Transactions on Graphics (TOG), 40(4):1-11, 2021.
[40] A. A. Team, Bauer, Baumli, S. Baveja, F. Behbahani, Bhoopchand, N. Bradley-Schmieg. M. Chang, N. Clay, A. Collister, et al. Human-timescale adaptation in open-ended task space. arXiv preprint arXiv:2301.0700 2023.
[41] M. Jiang, E. Grefenstette, and T. Rocktäschel. Prioritized level replay. In International Conference on Machine Learning, pages 4940-4950. PMLR, 2021.
[42] G. Brockman, V. Cheung, L. Pettersson,, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. arXiv preprint arXiv: 2016.
[43] Hardmaru. Slimevolleygym. http:p/pwg..ttpeee///////.o/o/aa http::///ttto.oooommmaa//a////a/ 2020.
[44] J. Berndt. Jsbsim: An open source flight dynamics model in c++ In AIAA Modeling and Simulation Technologies Conference and Exhibit, page 4923, 2004.
[45] A. P. Pope, J. S. Ide, D. Mićović, H. Diaz, D. Rosenbluth, L. Ritholtz, C. Twedt, T. T. Walker, K. Alcedo, and D. Javorsek. Hierarchical reinforcement learning for air-to-air combat. In 2021 international conference on unmanned aireraft systems (ICUAS), pages 275-284. IEEE, 2021.
[46] J. Terry, B. Black, N. Grammel, M. Jayakumar, A. Hari, R. Sullivan, L. S. Santos, C. Dieffendahl, C. Horsch, R. Vicente, et al. Pettingzoo: Gym for multi-agent reinforcement learning. Advances in Neural Information Processing Systems,
2021.
[47] D. Balduzzi, M. Garnelo, Y. Bachrach, W. Czamecki. J. Perolat, M. Jaderberg, and T. Graepel. Open-ended learning symmetric zero-sum games. International Conference on Machine Learning, pages 434-443, PMLR, 2019.
[48] S. McAleer, J. B. Lanier, R. Fox, and P. Baldi. Pipeline psro: A scalable approach for finding approximate nash equilibria in large games. Advances in neural information processing systems, 33:20238-2038 2020.
[49] S. McAleer, K. Wang, J. B. Lanier, M. Lanctot, P. Baldi, T. Sandholm, and R. Fox. Anytime psro for two-player zero-sum games. 2022.
[50] S. McAleer, J. B. Lanier, K. A. Wang, P. Baldi, and Fox. Xdo: A double oracle algorithm for extensive-form games. Advances in Neural Information Processing Systems, 34:23128-22 23199, 2021.

---

Pong
Volley
ACM
FSP
0.197 = 0.158
-0.143 + 0.061
94.498 + 39.686
PSRO
0.141 0.154
-0.145 0.058
83.274 + 51,499
GC+FSP
0.159 0.179
1.00440..0
-124.304 44.356
SPDL+ESP
-0.386 = 0.144
0.192 0.058
-97.987 = 51.969
MAESTRO
-0.578 0.142
-0.094 + 0.053
-226.845 + 25.332
GEMS
0.466 + 0.121
0.194 + 0.058
139.080 + 32.768
Table 3: Mean return of algorithms against baseline algorithms and ours for Pong, Volley, and ACM. The highest mean return bold.
[51] X. Feng, Slumbers, Wan, B. Liu, McAleer, Wen, Wang, and Y. Yang. Neural auto-curricula in two-player zero-sum games. Advances in Neural Information Processing Systems, 34:3504- 3517, 2021.
[52] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, et al. Soft actor-critic algorithms and applications. 2018.
[53] createmind. Deep reinforcement learning. hertinggtttttpp//gggtto.ooo////e wttp://cccccceeeaaaaeaeee 2019.
nd IdDDRI/
t http:///www...saoooo/////////aaa
[54] Schulman, Moritz, Levine, M. Jordan, and Abbeel. High-dimensionall continuous
control using generalized advantage estimation. arXiv preprint arXiv:1100.00248,, 2015.
[55] N. Barhate. Minimal pytorch implementation of proximal policy optimization. https:
/ //githbb.
2021.
[56] N. Minorsky. Directional stability of automatically steered bodies. Journal of the American Society for Naval Engineers, 34(2):280-309, 1922.
A Full Performance Results of the Trained Algorithms
In this section, we include the full results of our experiments. Table 3 and Table 4 shows the mean return of each algorithm against each other, while Table 5 and Table 6 includes the detailed results of each pair. Figure 6 shows the training curve, evaluated round robin fashion.
Pan CUPPERANTT Srmee
oxpleciue Mays
FSP
PSRO
GC-FSP
SPDL-FSP
MAESTRO
GEMS
Figure 6: Training curve with round robin results.
B Environment Details
This section will discuss the details of the benchmark environments used in this paper.
B.1 Pong
Environment Overview
12

---

Ant
SimpleAdversary
FSP
25.788
4.228
-10,545 + 0.166
PSRO
23,061 + 4.066
-5.535 + 0.308
GC+FSP
23,544 3.735
-10.125 + 0.158
SPDL+FSP
22.312 4.275
-15.47 = 0.338
MAESTRO
-9.358 + 0.169 19.748 + 3.706
GEMS
34.714 + 4.549
-5.010 + 0.333
Table 4: Mcan return of algorithms against baseline algorithms and ours for Ant and SimpleAdversaryy. The highest mean return in bold.
Pong is game similar to the one described in [42]. In this game, there are two paddles, each located at the left and right edges of the map. Each agent controls a paddle capable of ID movement, At the start of the game, a ball spawns at the center of the map with a certain velocity. The ball will bounce it comes in contact with the top edge, the bottom edge, or paddles. An agent wins the game if the ball passes through the opposite edge of the map.
To play the game, each agent observes the position and velocity of the ball and the location of each paddle. The action space is I-D. If the value is positive, the agent's paddle will move up at constant speed, and vice versa negative. An agent receives a reward of +1 if they win and -1 if they lose. neither player manages to win the game after 300 steps, it considered a tie with a reward of
Environment Encoding
The original enviromment calls the random number generator four times to reset game. Subsequently, we encode the environment with four values. One value determines whether the ego agent plays the left or right paddle. The other three control the initial velocity of the ball. One value determines whether the ball will be moving up or down, another controls the magnitude of the ball's velocity vector in the up-down axis, and the last one determines whether the ball will be traveling left or right. The magnitude of the ball's velocity in the left-right axis remains constant throughout the game.
B.2 Volley
Environment Overview
Volley is an environment based the concept presented in [43], where agents engage in 2D volleyball game. This presents more intricate update than Pong, as both players can move in 2D space instead of the ID movement of paddles. Additionally, the ball's horizontal speed can vary along with its vertical speed. At the start of the game, the ball spawns at the center of the map above the net, which divides the map into two halves. The ball will bounce upon contact with any players or edges except for the bottom. Each agent can redirect the ball by hitting it with the avatar they control. The ball follows simple physics model, subject to gravity and simple elastic collision mechanics. An agent wins the game by successfully landing the ball on the other side of the map.
To play the game, each agent observes the position and velocity of the ball, the ego agent, and the other agent. Each agent has a 2-D continuous action space, dictating the desired vertical and horizontal velocity of the avatar in the game. While the avatar can move at the desired velocity in the horizontal axis, can only launched upward with a desired velocity if on the ground. Otherwise, it will move along the surface or be in free fall due gravity, An agent receives a reward of +1 if they win and -1 if they lose. If neither player manages to win the game after 300 steps, is considered a tie, and both players receive a reward of O.
Environment Encoding
The Volley environment expressed in three values. The first two values are continuous (-1,1) and define the ball's initial velocity. The third value is discrete 0, 1 and defines whether the ego agent controls the avatar the left or the right.
13

---

Table 5: Detailed Win:Tee:Lose Ratio(%) of Each Algorithm Against Others.
GEMS (Ours)
GEMS (Ours)
GEMS (Ours)
GEMS (Ours)
MAESTRO
SPDL PPD
MAESTRO
SPDI SPDL+FSP +FSP
MAESTRO
SPDI SPDL+FSP +FSP
MAESTRO
SPDL +FSP
GC+FSP
GC+FSP
PSRO GC+FSP
GC+FSP
PSRO
PSRO
PSRO
Agent
FSP
FSP
FSP
FSP
36:1 06:1:442+1
30:0:25++
:2:0:22:1:::
32:::22: :2:00 :45+0
31:1 :2:+1 :42+1
3440 :3:40 :4:+0
36-0 06:0:2740
32:0 :5610 :14+0
1+0 1+0:39+0 :39+0 :60+0
2+0 :400:4400000 :00+
3:0 :48 :4
2010 :54+0 :660
25 :4 :25=
6110:1 61:0:13415 :1:10 :26:10
5140 :0=0 :4
59-0:11 :1::0 :25=0
58+0 000 :42#0
50.0 :0:0 50+0
5040 00 :50
6611 :410 :3010
9+: :0=0 :11=0
22+ :0: :78=0
48+1 :1 :111
42 :1:0 :5#+1
4941 :2=0 :49+1
:270 37:0
FSP
:22+1
:45+0
51=11 :30+1 :1911
:8:00:1-00
17:10
48 48:10
40:11
43-10
:050
35:0 :55 00:10-100
1+0 :390
210 :911 :9:1
320 :50=0 :47+1
22-0 :55-0
:7:10:1::000 :25-10
58:10:11
52+:
39:0:11-:0
59 :00 :41=0
5010 010 :50000 :50-0
63:1
13+1
22+1
50+1 :00 :49+1
4941 :310 049-0
VS PSRO
:20+:: :40+1
:00 :48+0
:410 :33-1
:0: :7011
:1:0 :78=1
:44+00
:1140
42-+0
:12-0
:00+0
:22+0
:26+0
Ant
ACM
Volley
Pong
47+1 47+1:311
16:1:23311
36:1112
38:11
42:11 :20 :381
50-10 :40-0:
10+11 ::34+1
:3:2:23:1
38:2:234
52:10 02:10:1::00 :1:10 00::002:1111
46:00
51+0 :1:10
49 :240 :4940
73:11 :2:10 :25
8=0 :0 92=0
1940 :00 80++
50+11 :0 :501
11:1::0100
VS GC+SSP
31111 :2+11
:23+1 1+:1:411
20 01:0:42:1
:2:0
11:00:20 :9::0
:41+1
:42:1
:2:0
:7++1
:5+11
:3822
:29110
:5440
30:0
31 31:0 0110:371000 :3:0
4941
0040:18:4
3940
4340:16:1
48.10: :5000:0000::::
2+0 :40:540 :540 (9:0:9344
8 $10:8410
0010:1540
29
3040
89:10: :140 :11::111: :100
40+0 :0 600=
50+0 :0 :50=0
VS SPDL+FSS
1111:11 3141
:4:440
:840
:1::::::0:00
0
03710:36
1::1:004
08:0:000
0::0::14
10:00:114
0 1-003044
2011
00:4:444
:10
31:00
30+0
5140
42#1 1:1::1844
0210: 0210:3710:
62.1662110000 :6-
17:1:661
47 17:1:66
47
- 541:
00:0:0::0
0 94:10 :0:0 :::00::::0
50+0
vS MAESTRO
04003300 :30+1
:840
:2010
:0=0
:0= :50=0
0::0:50:0
1::1::188:
:7:4+11
:::00:2:::
2 :141
41:
:2710
:6::0
26=11
18-1
31:0
GEMS (Ours)
1 1 10-11:220
:64
:7:10
1
17+1
:18-0
:31:00
.7:11
14

---

Table 6: Detailed Win: Win:Tie:Loss Loe: Ratio(%) of Each Algorithm Against Others. (SimpleAdversarry)
GEMS (Ours)
MAESTRO TRO
SPDL4 +SP
GC+ESP
PSRO
Agent
ESP
5440 :0: :46.10
49.10
46 0=0 :54+0
50+0 0== :50+0
53 0=0 :47+-
50 00= :50+
:0 :1:0:1100
FSP
:51110
50410
47.10
43:0
46:0
50+0
:0:0 10:000000
:0.0 00100:511
:00 :57+
:00 :5440
:50+0 50=0
PSRO
:3110
5500
SimpleAdversary
5440
49.0
47+0
50+0 :0:00 :50=
vs GC+FSP
:011 :46110
:0110 :51:00
:00 :53-10
1 57-10 :0+0
52.10:0 :010
50+0 :0+ :50=0
VS SPDL4FSP
:010
4810
5010 00.00:011 :0.10 0010:50110
MAESTRO
00:0 10:0::55
GEMS (Ours)
15

---

B.3 ACM
Environment Overview
ACM a simulated dogfight environment. This more complex than the previous two benchmarks, as ACM agents will move in 3D space with realistic physies simulation. At the start of the game, two aireraft spawn in the air a certain orientation and velocity vector with respect to the nose heading. The agent wins the game by pointing its nose at the opponent while avoiding getting pointed by the opponent's s nose. There is also a penalty involved with crashing to the ground.
To play the game, each agent observes the position, orientation, and velocity the ego and the opponent agents. Each agent has 4-D continuous action space with direct control over the aircraft's elevator, aileron, rudder, and throttle. The physies is simulated by JSBSim [44], high-fidelity simulator often used in autonomous aireraft research. The aerodynamics model for ACM is based on Boeing F-15D, capable of flying two times faster than the speed of sound.
To win the game, the agent should have its nose pointed less than 5 degrees off the opponent aircraft while flying less than 2,000 feet away from the opponent. The agent can also win the game the opponent aircraft flies below the hard deck of 500 ft. The agent wins the game if either of these conditions are met and loses if the opponent achieves either of the conditions. It is tie if both aireraft achieve either of these conditions simultaneously. If either of the agents meets none of the conditions for 300 seconds, it is considered tie. Agent receives a penalty of -300 for crashing into the ground, 150 for pointing the nose toward the target, and 100 if the opponent crashes to the ground. To help with training, there is a small, dense reward for getting closer to pointing the nose toward the opponent.
Environment Encoding
The ACM environment is expressed in 14 continuous values. They define the initial conditions of the game, which are each aircraft's position, orientation, and airspeed.
B.4 Ant
Environment Overview
Ant is simulated Mujoco environment where two ant agents try to flip or push the other agent out of the arena. With each agent having 8 degrees of freedom in a contact-rich setup, the environment offers a variety of behaviors to learn. For example, while ramming is often the only way to win against a stationary target, ramming is vulnerable to flipping attacks. However, flipping attacks are useless against stationary opponents as agents need more torque to lift and flip an opponent with all its legs firmly contacting the ground.
To play the game, each agent observes the position, orientation, velocity, and posture of the ego and the opponent agents. Each agent has 8-D continuous action space with direct control over the torques applied to each joint. The agents get a reward of 100 the opponent is flipped or pushed out of the arena. There a penalty -20 if the agent is flipped or exits the arena. To make the training faster, there is sparse reward for approaching the opponent or moving towards the center the arena. neither player manages win the game after 300 steps, it is considered tie, and both players receive reward of 0. While the environment is based OpenAl's implementation of Sumo-Ant [11], the arena is smaller to allow agents to interact more and learn faster.
Environment Encoding
The Ant environment expressed in discrete value assigning who will be controlling the red agent and who will be controlling the blue agent in the game. The red and blue agents have the same winning and losing conditions and have fixed spawn points in the arena.
16

---

B.5 Simple.Avvessary
SivpleAdversary is Multi Particle Environment from [46]. SimpleAdversary provides an interesting opportunity to validate our GEMS on environments that are asymmetrical and have both competitive and collaborative features to a game. ?? shows a screenshot of the environment.
In this environment, there is one adversary agent (red), two good agents (blue), and two landmarks (green and black). One of the landmarks is target landmark where the good agents get reward for the good agents getting close to the agent and a negative reward for the adversary agent getting close to the target landmark. The vice versa applies to the reward for the adversary agent. While all agents can see the location of each other and landmarks, only good agents have additional information on where the goal is. The good agents observe the environment with 10-D space including the goal information while the adversary agent observes the environment with 8-D space missing this environment. The action space is continuous, with the agents being allowed to move up, down, left, and right.
This environment covers challenges that are not covered well in the original manuscript. First, it is an asymmetrical environment where the goal and the optimal policies differ by role. Also, there are two good agents in the game which has to learn to collaborate with each other. Finally, there are three agents this game, giving a limited yet first glimpse into scalability regarding the number of agents.
B.6 Environment Encoding
SimpleAdversary has total of 5 objects in the game consisting of two landmarks, two good agents, and one adversary agent. The first 10 variables in the environment encoding cover the X and Y coordinates of the objects in the game. The last I Ith variable in the environment encodes whether the ego agent playing as the good agent or the adversary agent in the game.
As observation space is different whether playing zero padding to equalize the dimensions. In addition, we also add variable to the observation space denoting whether the agent is playing as an adversary agent or good agent. This allows the policy network to run as conditional network able to support both roles in the game.
adversary agent or good agent, we added
C Implementation Details
This section covers the details of implementing the training procedures for each baseline for repro- ducibility purposes.
C.1 Training Hardware
We used an 88-core Intel Xeon Gold 6238 CPU at 2.10 GHz to train the models. Training models took from 5 ~ 15 days. Lighter benchmarks, like Pong, took 5 days, while heavier benchmarks, such as ACM, took 15 days. This is due to the computation load of the JSBsim, which provides high-fidelity aerodynamics simulation.
C.2 Tuning RL Algorithm
Tuning Procedures
To ensure that hyperparameters do not favor one baseline over another, they were tuned for the RL policy explorer in a single-agent setup against hand-coded opponents. For Pong and Volley, the opponents were PID controllers chasing the estimated impact point of the ball [56]. In the case of ACM, a simple PID autopilot was employed to control the opponent aircraft's 's speed, heading, and altitude. Ant was tuned with a stationary agent that does not move. The combination of network structure and hyperparameters that performed the best in these single-agent setups was selected for baseline experiments. Note that these hand-coded agents were only used to tune the RL
17

---

Benchmark
Parameter Name
Range
Pong
Magnitude of the Ball's Vertical Speed Left-Right Initial Velocity Direction of the Ball
[0.1]
{0,1)
Up-Down Initial Velocity Direction the Ball
{0.1)
Left / Right Paddle Controlled by the Ego Agent
{0.1)
Volley
Initial Horizontal Velocity of the Ball Initial Vertical Velocity of the Ball Left / Right Paddle Controlled by the Ego Agent
[0.1]
[0,1]
(0.1)
ACM
Ego Agent Initial X Coordinates
Ego Agent Initial Y Coordinates
Ego Agent Initial Z Coordinates
Ego Agent Initial Heading
Ego Agent Initial Pitch Angle
Ego Agent Initial Role Angle
Ego Agent Initial Airspeed
Opponent Agent Initial X Coordinates Opponent Agent Initial Coordinates
Opponent Agent Initial Z Coordinates Opponent Agent Initial Heading Opponent Agent Initial Pitch Angle Opponent Agent Initial Role Angle Opponent Agent Initial Airspeed
[1,1]
Ant
Ego and Opponent Agent Spawnpoint Configurations
(0.1)
SinpleAdversary
Good Agent 0 Location, X
Good Agent 0 Location, Y Good Agent 1 Location, X Good Agent 1 Location, Y
Adversary Agent Location, X
Adversary Agent Location, Y
Goal Location, X
Goal Location, Y
Obstacle Location, X
Obstacle Location, Y
[1,1]
Ego Agent Playing As
(0.1)
Table 7: Summary of environmental parameters.
hyperparameters. The hand-coded agents were not used when training the baselines and our approach, GEMS.
Network Structure
To train our RI algorithm, we experimented with various network structures, varying the depth of the hidden layers from I to layers and the width from 64 to 512. Our findings revealed that the optimal architecture for Pong, Volley, and ACM consists of hidden layers composed of two fully connected layers, each with size of 256. We utilized ReL.U activation between the hidden layers and concluded that the last layer had output dimension equivalent the action dimension, followed by Tanh activation. Conversely, Ant uses 2-layer policy networks with Tanh activation and width of 128.
C.3 RL Hyperparameters
We conducted limited grid search to hyperparameters for our RL algorithm. For learning rate, tried (3e-5, le-4, 3e-4, 1e-3). For discount ratio 7, we tried (0.95, 0.98, 0.999).
18

---

Pong
Volley
ACM
Ant
SimpleAdversary
Start Steps
10000
10000
10000
N/A
10000
Learning Rate
3e-4
3e-4
3e-4
3e-4
3e-4
0.98
0.98
0.98
0.98
0.98
auto
auto
auto
N/A
auto
Batch Size
256
256
512
36864
256
Replay Size
le6
le6
le6
N/A
le6
Update Every
1
36864
Backpropagation per Update
N/A
N/A
N/A
20
N/A
Table 8: Selected hyperparameters for RL algorithms.
Regarding the algorithms that use SAC, we tried 0, 1000, 10000 for the initial exploration steps. For batch size, we tried {64, 256, 512]. For update every, we tried {1, 32, 100). We tried {1e6, 3e6} for Replay size. We each setting 3 seeds balance performance and computational cost.
Regarding algorithms that use PPO, we tried policy update frequency of the number of times the gradient was calculated and backpropagated per update frequency, we tried 10,20,30. We ran each setting on 3 seeds to balance performance and computational cost.
For
Table 8 shows the selected hyperparameters used for the main experiments.
D Baseline Hyperparameter Tuning
To tune the hyperparameters for the baselines, we trained the models using the following settings. Since is challenging to tume the hyperparameters by conducting round-robin across all hyperpa- rameter settings used for different baselines, each setting was evaluated against the same hand-crafted opponents used for tuming the RL hyperparameters. Striking balance between performance and com- putational cost, we ran each configuration with 3 seeds. Table 9 presents the selected hyperparameters used for the main experiments.
We tested the following hyperparameter values limited grid search. For adding checkpoints, we tried saving copy of the agents' policies at every {10000, 30000, 50000} exploration step. We used the same interval of steps the interval in which curriculum is generated for the algorithms random that generate at every epoch. For measuring performance between each checkpoint environment parameters to approximate the Nash equilibrium in PSRO, we tried { (10,30) evaluations per pair. As for the hyperparameters of the GC, we tried {200,300} for the size of the population of scenarios evaluated for whether being solved or not solved. We also tried sizes of (200,300) for the sizes of the generated curriculum and mutation rates of (,.1,1} }. For SPDL, we tried values of {0.10,20) for offset and (0.1,0.3.1) for penalty proportion. For MAESTRO, we tried co-player exploration coefficients of (0.05.0.1) and curriculum buffer sizes of (500,1000) For GEMS, copied the hyperparameters from the GC in terms of the size of the curriculum and mutation rate. This was done to make comparisons between different algorithms easier by removing the effect of different hyperparameters during genetic operations.
E
Crossover and Mutation
This section covers how GEMS perform crossover and mutation. Please note that these steps simply conduct generic genetic operations and are not hand-tuned nor hardcoded to specifically solve the benchmark tasks in this paper.
For sampled parent scenarios m, n, the corresponding encoding would look like;
(in, To, 2) {mo, mi} {mo,,, mo, 1...1... 11,00 11, 11.1........
19

---

Pong
Volley
ACM
Ant
PSF
Checkpoint Interval
10000
10000
10000
50000
PSRO
Match Times
30
30
10
10
GC
Evaluation Set Size
200
200
300
300
Curriculum Size
200
200
300
300
SPDL
Penalty Proportion
0.1
0.1
Offset
20
20
20
20
MAESTRO
Co-Player Exploration Coefficient
0.1
0.1
0.1
0.1
Curriculum Buffer Size
1000
1000
1000
1000
Table 9: Selected hyperparameters for baselines.
n1 = {io: To: )/ (no: n2 = {n Ro. 10,00 11.1
m. encodes the choice of opponent to load in and the environment parameters v while m. represents the encoding the GenOpt Agent To .In this section, x corresponds to the length of environment encoding for m. y and 2 in this section corresponds to the length of GenOpt Agent Te encoding for m and n. If using the same environment, x will not be different between the scenarios, whereas y and will vary depending the encoded environment.
GEMS performs crossover by swamping section from one parent with a section from another parent. This would be done by randomly selecting three split points in the encoding. Using uniform distribution, GEMS sample three integer values yo E (0, 1,2,,,22..) m E {0, -,,..).. 722 E
(0, 2,2,
From this, GEMS generates two child scenarios p, q follows;
(mo.o.. 7 Ro. 11.00..M1,,,0, e1..
q (no.o...Ro.m Mu Mu. 711,0...71,etaa Mt,eta +1 +1....1..
For the special cases such as n7 x 71 0, or 1/2 0, GEMS inherits the segment without dividing it. For example, if no 0, then Po no, qo mo and on.
To perform a mutation on a sampled scenario, GEMS first performs crossover between the scenario and a randomly generated scenario and returns one of the child scenarios as the mutated scenario. The mutation rate controls the probability of each scenario undergoing mutation.
Sampling Parents
In this paper, we have defined the probability of GEMS sampling scenarios as parents as the following:
p(E) x 8(E) - G(Tegoo E))
In practice, GEMS uses the normalized form as follows;
p(E)) 8(5,)( G G(Tego Ei)
Σ5(E) G(Tegos E))
20

---

If (() = 0, GEMS use regret-only version as follows;
(1 G (Tegas Ex)
p())
Σ( G ())
G Evolution of Curriculum
Figure 7 includes characteristic examples of the scenarios generated and used as curriculum for each algorithm in the ACM benchmark.
21

---

Start Training
Middle Training
End of Training
FSP
PSRO
GC+FSP
SSPL
-18
MAESTRO
GEMS (Ours)
Figure 7: Each dot marks the position of the red and blue aircraft at 1-second intervals. The color of the markers transitions from black to blue for the student aircraft and from black red for opponent aircraft. It is important to note that at the start of the training, only our approach, GEMS, can present scenarios and opponents that provide interesting data points instead of simply crashing to the ground. While SPDL+FSP somewhat succeeds in finding scenarios that do not end in crash, it optimizes scenarios without considering opponent policy. simply finds trivial cases where agents flying in circles.
22


Reviews:
[{"review_id": "eLJyMor5VL", "reviewer": "Reviewer_1f7s", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 2, "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": "This paper presents a genetic algorithm based method for curriculum lear.ning in multi-agent RL setting. It also introduces a genetically optimized agent, GenOpt Agent, which executes a scheduled action. This agent is optimized without an expert supervision . The result shows the proposed method outperform the previous work in two-player competitive setting.", "summary_of_recommendation": "The reviewer suggests major modification to add more clarity in methodology. The reviewer's concern is  the result being statistically significance compared to the previous work.", "technical_quality": 3, "clarity_of_presentation": 3, "potential_impact": 2, "robotics_focus": 2, "quality_of_limitations": 2, "questions_for_rebuttal": "1- The related work only provides previous work and their limitation. It is not clear how the proposed method fills their gap and limitation, which needs to be provided in related section\n2- Figure 1: it is not clear if Ego student is GenOpt agent. Also, why having GenOpt similar to ego agent is beneficial?\n3- line 120: 2 player-> 2-player or two player\n4- Algorithm 1, line 14: reward -> regret?\n5- It would be helpful if the author/s provide a pseudo code or algorithm for GenOpt Agent, or they improve the explanation.\n6- Line 103: it seems it provides a formulation for  RL with deterministic assumption as there is not transition function in  this formulation\n7- Table 1: it would be helpful if the author/s provide statistical result to show whether their method is statistically significant\n8- To add more clarity, the reviewer suggests the word' (ours)' infront of the proposed method\n9- It is not clear why those games are selected and how this environments are challenging, in other words, why the proposed method would achieve better result.\n10- Figure 5: it seems GEMS and MEASTRO would perform similarly when they converge, the reviewer suggest  running more episode to see their trend when they converge.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F7m2iwDZl9", "reviewer": "Reviewer_7Pcd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "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": "This paper introduces GEnetic Multi-agent Self-play (GEMS), a genetic curriculum to select environment variables and opponents, and GenOpt agent, an open-loop opponent that is optimised by the curriculum generator. GEMS outperforms several baselines on multi-agent reinforcement learning tasks (Pong, Volley, ACM, Ant).", "summary_of_recommendation": "I think there is some interesting work here, though I'm not convinced the contribution is sufficient. -> Increased score after rebuttal.", "technical_quality": 3, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 2, "quality_of_limitations": 2, "questions_for_rebuttal": "See above", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kYiz1nVWlJ", "reviewer": "Reviewer_FqYm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "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": "This paper introduces a curriculum generation scheme for multiagent scenarios using genetic algorithms. The authors show positive results through extensive experiments.", "summary_of_recommendation": "Although showing extensive and positive experimental results, I recommend a weak rejection due to concerns on limited novelty in the proposed methodology, no theoretical analysis on convergence and sample complexity, and limited generalization to asymmetrical problems. After rebuttal, the authors sufficiently addressed the biggest concern I had during review, hence I've updated my recommendation to weak accept.", "technical_quality": 4, "clarity_of_presentation": 3, "potential_impact": 3, "robotics_focus": 2, "quality_of_limitations": 3, "questions_for_rebuttal": "1. I would love to hear some rebuttal to points 1 and 2 that I’ve written down in the weakness section.\n2. How are the GenOpt agents parameterized? Does GEMS directly search over the actions at each timestep range? Are the timestep range knotpoints (t1, t2, etc.) chosen beforehand and fixed? Since the parameterization of the GenOpt agent is always present as part of the genome, wouldn’t the outcome obtained when NOT using the GenOpt agent introduce potentially wrong direction for optimization in GEMS?", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AWhDUNEv0v", "reviewer": "Reviewer_jtXR", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "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": "The paper introduces a genetic algorithm approach to optimize the curriculum of learning agents in simulated environments with multiple agents using self-play with checkpoints. Their approach utilizes a scenario generator which is able to perform traditional genetic algorithm operations given some scenario and the regret of the policy in past scenarios. The authors formulate the learning policy and this generator as adversaries in a zero sum game. Basically, the generator tries to find the scenarios and modifies them through mutation, in which the current policy performs bad and the current policy tries to maximize its return on the current set of given scenarios. Opposing players in each scenario are sampled by the generator from past checkpoints of the policy. This approach is tessted in four environments and evaluated against the PSRO baseline. The new approach GEMS performs best in all environments and shows robustness in evaluation against 5 baseline agents and the GEMS agent. They also provide an ablation study showing that the regret component of their algorithm is not important for early training but maximizing out an agents final performance.", "summary_of_recommendation": "The paper is an enjoyable read and presents clearly a new idea, that is a combination of previously known concepts applied in an interesting manner. The approach outperforms existing methods and therefor is of interest to the scientific community. While there are minor improvements that can be made to the paper i recommend accepting.", "technical_quality": 4, "clarity_of_presentation": 5, "potential_impact": 2, "robotics_focus": 1, "quality_of_limitations": 2, "questions_for_rebuttal": "Question 1:\nIn the evaluation section you write that you evaluate in a round robin format of the agents. However as GEMS still loses to others it does provable never learn an optimal strategy to cover all opponent strategies. What are the reasons for the exploitable weaknesses that remain in the learning process?\n\nQuestion 2:\nIf I understood correctly, the regret component of GEMS chooses environments, which have the regret of -1 with a higher probability to reuse (given modifications). How is it ensured that environments of appropriate difficulty are selected? Could not the hardest difficulties, which yield a high regret but also are too hard for learning currently and up being selected making learning very expensive? What if the space of learnable scenarios is small in comparison to those which are too hard to learn?", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers all saw some strengths with the paper, however the authors must address multiple comments and perform numerous revisions to improve chances of acceptance.  

The work is interesting, generally clear, and (to some extent) novel.  Compared to the presented baselines, and with the constraint of only being suitable for symmetric scenarios, the algorithm presents some promising results.

However, it is rather incremental and - in addition to the comments on novelty highlighted by the reviewers, I can point the authors to https://dl.acm.org/doi/abs/10.1145/3512290.3528870 for a related approach.  The constraint of limiting to only symmetric scenarios is significant and only represents a small minority of the types of scenarios we'd like an curriculum design algorihtm like this to work on.

Due to the incremental nature of the work, there are questions around the level of contribution provided by the paper.

The paper also lacks a proper discussion of limitations, and is only done on simulation experiments with no real-world testing.



Update:

The authors have done a good job in responding to reviewer comments, and have effectively answered the main issues with the original paper.  The paper is significantly improved.
Decision: Accept