Genetic Algorithm for Curriculum Design in Multi-Agent Reinforcement Learning

Authors: yeeho  song
jeff  schneider
Venue: robot-learning_org_CoRL_2024_Conference
Published: 2024-06-07 09:34:15

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.

Main paper: 
 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 a population of opponent policies to avoid overfitting to a specific opponent. [1, 2, 3] .When training against a population of policies, selecting the policies most useful for training is challenging. Some works use game-theoretic methods to select opponents [4, 5] , but finding approximate Nash Equilibria in setups with large search spaces is costly. Others use curriculum learning to select opponent policies [6] , but relying on random sampling to 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 self-play is training instability due to the adversarial vulnerability of RL policies [8, 9, 10] . RL agents often overfit to a specific opponent's weakness, resulting in non-generalizable behaviors. For example, when training against a mujoco-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-agnostic 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 1 summarizes our approach. Supplementary information and codes can be found in https:// github.com/yeehos/GEnetic-Multiagent-Selfplay.git Figure 1 : Overview of our proposed approach: During training, the ego student agent is trained against a 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 on the performance of the scenarios in the previous population, our curriculum generator uses a genetic algorithm to generate a new population of scenarios to be used to train the agent for an epoch at each fixed interval of steps. 
related works: 
 Game Theoretic Approach to Self-Play Training an RL agent in competitive multi-agent environments requires an opponent. Unlike rulebased opponents [12] or expert demonstrations [13] , self-play [14, 15] agents to 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 a specific policy [16] . Therefore, Fictitious Self-Play (FSP) [17, 18, 1] proposes to train against a population of opponents. In deep RL, this opponent library is often compiled by saving checkpoints of the ego policy during training [3, 19] .Expanding on these findings, game theoretic approaches like Policy Space Response Oracle (PSRO) [4, 3, 19] utilize Nash equilibrium [5] , a stable point in a 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 if the policy space is large. Moreover, effectively learning policies in complex, non-stationary, and partially observable multi-agent environments remains a significant challenge. While some approaches use ensemble learning to split the learning task [20] [21] , they are limited to simpler, discrete action setups. This paper approaches this issue with a curricular viewpoint.When it comes to learning a policy for a difficult problem, Curricular RL suggests that agents can learn faster by first being exposed to simple tasks and scenarios and gradually progressing to 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 Optimization [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 a 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 a population, helping the transfer of skills within the curriculum by enhancing similarity among the scenarios. While successful in generating an effective curriculum in a large scenario space, GC requires costly evaluation steps to validate scenarios. Additionally, GC cannot regulate scenario difficulty.One way to regulate difficulty is to use regret, which quantifies the gap between the current obtained return with the maximum possible return on the scenario. Showing success in various singleagent 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 guarantee robustness, it is limited by relying on domain randomization to uncover new scenarios. Studies in GC [7] suggest this can lead to suboptimal performance. Unlike those generated by population-wide 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-agent curriculum generation. 
preliminaries: 
 An RL problem setup is typically represented as a tuple in a Markov decision process: [S, A, P, r, γ], where S is the state space of a problem, A is the action space, P is the transition dynamics, r is the return of a state-action pair, and γ ∈ [0, 1) is the temporal discount factor. The agent's policy, π(a | s), maps states s ∈ S to actions a ∈ A. The utility of a policy π is the expected return is denoted as J(π) = E tγ t r(s t , π(s t )). During training, an RL algorithm optimizes the policy with respect to the data it has collected.In our multi-agent setup, we consider that the utility of a policy is dependent on both the opponent's policy π opp and the environment ψ, denoted as J(π ego , π opp , ψ). At each epoch consisting of a fixed number of time steps, we save the current version of our ego agent and add it to the library of possible opponents to choose from Π opp . We describe the environment with parameters, ψ. We define a scenario ξ as an opponent policy -environment pair: ξ = {π opp , ψ}. The goal of our curriculum generator at a given timestep is to generate a population of scenarios, Ξ train = {ξ 0 , ξ 1 , ..., ξ n }, where optimizing the ego policy π ego with respect to the curriculum Ξ train will result in a policy with the behaviors we desire.π * = max π J(π ego , Ξ train )For the multi-agent setup, we want our algorithm to continuously explore the game by visiting scenarios that it does not do well to learn new competitive behaviors. We design our curriculum generator around this idea by first formulating multi-agent learning as a zero-sum game G(π ego , ξ) between the π ego and the curriculum generator. G(π ego , ξ) = 1 if π ego wins the scenario ξ, G(π ego , ξ) = 0 if it was a tie, and G(π ego , ξ) = -1 if loses. The opponent π opp and the environment parameters ψ are determined by the curriculum's scenario ξ. The solution for a finite zero-sum two player game is minimax;G * = min Ξ max πego G(π, Ξ)Therefore, our curriculum generator will generate a population Ξ that minimizes G(π ego , Ξ) Mutation changes an encoded segment of a parent with a random sequence.In this section and onward, we explain how our proposed algorithm, GEnetic Multi-agent Self-play (GEMS), as described in Algorithm 1, generates curriculum.To generate a curriculum, GEMS uses a 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 Ξ train . π ego trains on the Ξ train for an epoch consisting of a fixed number of steps. For 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(ξ), defines the probability of a scenario being harvested. Since the GEMS is trying to minimize G(π ego , Ξ) of the generated curriculum, fitness is proportional to (1 -G(π ego , ξ)). At the same time, GEMS needs to generate scenarios with high information potential, measured as regret, δ(ξ). Therefore, fitness is set asp(ξ) ∝ δ(ξ)(1 -G(π ego , ξ)).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 is when the algorithm selects a random segment from a parent scenario encoding and swaps it with a segment from a 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 a 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.Self-play in deep RL often suffers from training instability due to ego agents exploiting the adversarial vulnerability of the opponents. While using open-loop agents can 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 π ∅ , that optimizes open-loop behaviors using genetic algorithms without supervision.π ∅ = {(t 0 , a 0 ), (t 1 , a 1 ), (t 2 , a 2 ).....} encodes the opponent as a list of non-fixed lengths describing which actions to take in an open-loop fashion. For example, at timestep t 1 < t < t 2 , the opponent takes action a 1 . 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-induced confusion, but unlike No-OP, GenOpt is competitively optimized to match the ego agent's performance, enhancing its applicability across diverse environments.Using the features above, GEMS encodes a scenario as ξ = {i π , π ∅ , ψ} i π is an integer representing the i-th checkpoint to load as the opponent π opp . If i π = 0, it indicates that no agent will be loaded, and instead, a GenOpt Agent π ∅ will be used as the opponent. ψ denotes which environment parameters to load. It should be noted that whether it is used or not, the encoding for the GenOpt Agent π ∅ is always present in a scenario ξ. This ensures that the optimization and the memory about a GenOpt Agent π ∅ are not lost during the genetic operations and can always be brought back if needed throughout the training. Pong is a 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 1-D movement and fixed horizontal ball speed focus make dynamics easy to learn and relatively emphasize the game-theoretic aspect of the solution more than other benchmarks.Volley is based on [43] . Each player uses continuous action input to control an avatar, moving left, right, and jumping. The goal is to bounce the ball to land on 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 its 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] , a high-fidelity simulator widely adopted in autonomous aircraft and aircraft controls research due to its accurate aerodynamic 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 to one of the agents.Ant is a simulated Mujoco environment based on OpenAI's Competitive Gym environment. [11] . The game'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 to mix and use them to win a game. To the best of our knowledge, we are the first paper to solve the Ant problem by training from scratch without expert supervision or pretrained weights.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 collaborative-competitive settings with multiple agents. 
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 a gradual, easy-to-learn fashion. Therefore, we utilize PSRO as a characteristic example to highlight the limitation of this assumption. While PSRO necessitates additional steps to 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 a comparison against approaches that use a 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 fairness 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 use an approach more relevant to the multi-agent domain by including MAESTRO [6] . MAESTRO represents a state-of-the-art approach to optimizing environment-opponent 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-based multi-agent RL. FSP loads environmental parameters by domain randomization.For all algorithms, we use a publicly available implementation of Soft Actor Critic (SAC) [52, 53] and Proximal Policy Optimization (PPO) [54, 55] as the base strategy explorers.We conduct experiments to evaluate each method's effectiveness using ten random seeds for Pong, Volley, and 5 for the more complex ACM and Ant benchmarks. The training duration varied from 5 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 our GEMS across 200 games with randomized environment parameters, utilizing Round Robin format for both interim (every 2.5e5 timesteps for SimpleAdversary, 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 on 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. 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 in other benchmarks. GC [7] suggested that relying on random exploration instead of curriculum generation can be limiting. We will confirm that this limitation extends to the multi-agent setup in our ablation study.While PSRO performs well in Pong, where dynamics are simple and approaching game-theoretical solutions is relatively more important, PSRO'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 a broad spectrum of opponents. Also, while PSRO's game theoretic approach allows it to outperform most of the baselines in an asymmetrical setup such as SimpleAdvesary, as shown in Table 4 , our GEMS outmatches PSRO via flexible architecture applicable to such setups as well.Despite both being curricular methods, GC+FSP and SPDL+FSP exhibit different performances. SPDL+FSP can regularize scenario difficulty and outperforms GC+FSP in more complex environments such as Volley, ACM, and Ant compared to PONG. GC+FSP, on the other hand, has a robustness guarantee unlike SPDL+FSP, and outperforms SPDL+FSP in simple benchmarks such as Pong, where difficulty regularization is not important. However, both suffer from ACM benchmark as neither are designed for multi-agent setups.MAESTRO'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. 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 to 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 a 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. We conduct an ablation study on our GEMS to demonstrate the empirical effects of our design choices. NoRegret experiment excludes the regret term (δ) when calculating 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] One key aspect of GEMS is the use of genetic operations. GC [7] showed that genetic algorithms outperform random exploration in single-agent settings by efficiently identifying challenging scenarios similar to each other, facilitating effective task generation. The ablation study shows that this advantage also applies to the multi-agent domain, where even solely relying on mutation (NoCrossover) is more effective than random exploration (NoGenetic). 
ablation study: 
 However, beyond difficulty regularization by regret, GEMS has several useful features for multi-agent training. One such is 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, NoVic exhibits inferior performance, illustrating that while regret contributes to curriculum generation, G(π ego , ψ) is pivotal for ensuring training stability and effective curriculum optimization. 
conclusion: 
 This paper proposes using a genetic algorithm to improve and stabilize learning in multi-agent environments. Using the strength of genetic algorithms to generate a curriculum in a large scenario space, we enable an RL agent to reach a 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 baselines, and an ablation study further confirms the significance of our design decisions. 
limitations and future works: 
 Similar to MAESTRO [6] , our method currently lacks a provable guarantee for convergence to the Nash equilibrium in games. This presents an opportunity to identify conditions under which guaranteed convergence can be achieved. Pong is a 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 1D movement. At the start of the game, a ball spawns at the center of the map with a certain velocity. The ball will bounce if 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. 
 
 Appendix: To play the game, each agent observes the position and velocity of the ball and the location of each paddle. The action space is 1-D. If the value is positive, the agent's paddle will move up at a constant speed, and vice versa if negative. 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, it is considered a tie with a reward of 0.The original environment calls the random number generator four times to reset a 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.Volley is an environment based on the concept presented in [43] , where two agents engage in a 2D volleyball game. This presents a more intricate update than Pong, as both players can move in a 2D space instead of the 1D 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 a 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, it can only be launched upward with a desired velocity if it is on the ground. Otherwise, it will move along the surface or be in free fall due to 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, it is considered a tie, and both players receive a reward of 0.The Volley environment is 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 on the left or the right. ACM is a simulated dogfight environment. This is more complex than the previous two benchmarks, as ACM agents will move in 3D space with realistic physics simulation. At the start of the game, two aircraft spawn in the air at a certain orientation and a 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 nose. There is also a penalty involved with crashing to the ground.To play the game, each agent observes the position, orientation, and velocity of the ego and the opponent agents. Each agent has a 4-D continuous action space with direct control over the aircraft's elevator, aileron, rudder, and throttle. The physics is simulated by JSBSim [44] , a high-fidelity simulator often used in autonomous aircraft research. The aerodynamics model for ACM is based on a 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 if 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 a tie if both aircraft achieve either of these conditions simultaneously. If either of the agents meets none of the conditions for 300 seconds, it is considered a 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.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.Ant is a 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 if the opponent is flipped or pushed out of the arena. There is a penalty of -20 if the agent is flipped or exits the arena. To make the training faster, there is a sparse reward for approaching the opponent or moving towards the center of the arena. If neither player manages to win the game after 300 steps, it is considered a tie, and both players receive a reward of 0. While the environment is based on OpenAI's implementation of Sumo-Ant [11] , the arena is smaller to allow agents to interact more and learn faster.The Ant environment is expressed in 1 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.SimpleAdversary is a 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 a target landmark where the good agents get a 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 in this game, giving a limited yet first glimpse into scalability regarding the number of agents.SimpleAdversary has a 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 11th variable in the environment encodes whether the ego agent is playing as the good agent or the adversary agent in the game.As observation space is different whether playing as an adversary agent or a good agent, we added a zero padding to equalize the dimensions. In addition, we also add a variable to the observation space denoting whether the agent is playing as an adversary agent or a good agent. This allows the policy network to run as a conditional network able to support both roles in the game.This section covers the details of implementing the training procedures for each baseline for reproducibility purposes.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.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 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 our baseline experiments. Note that these hand-coded agents were only used to tune the RL 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 {1e6, 3e6} for Replay size. We ran each setting on 3 seeds to balance performance and computational cost.Regarding algorithms that use PPO, we tried policy update frequency of 9216,18432,36864. For 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.Table 8 shows the selected hyperparameters we used for the main experiments.To tune the hyperparameters for the baselines, we trained the models using the following settings. Since it is challenging to tune the hyperparameters by conducting a round-robin across all hyperparameter settings used for different baselines, each setting was evaluated against the same hand-crafted opponents used for tuning the RL hyperparameters. Striking a balance between performance and computational 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 in a limited grid search. For adding checkpoints, we tried saving a copy of the agents' policies at every {10000, 30000, 50000} exploration step. We used the same interval of steps as the interval in which curriculum is generated for the algorithms that generate one at every epoch. For measuring performance between each checkpoint on random 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 {0.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, we 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.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 a sampled parent scenarios m, n, the corresponding encoding would look like; m = {i π , π ∅ , ψ} = {m 0 , m 1 } = {m 0,0 , m 0,1 ...m 0,x , m 1,0 , m 1,1 ...m 1,y }  


Decision: 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.

Reviews: review: title: title: The paper is well written and easy to follow. However, it is not clear if the result is statistically significant.
paper_summary: paper_summary: 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.
main_review: main_review: Strength:
- The paper is well written and easy to follow.
- The paper provided an extensive experiments and comparison with the previous work.
- The paper considers Genetic Algorithm for curriculum learning, which is different from most of RL methods and  outperforms previous work in different competitive benchmarks.
Weakness:
- The results shows the proposed method (GEMS) outperforms all the baselines. However, it is not clear if the result are statistically significant.
- It is not clear if the proposed method can be considered for robotics application. All of the experiments are in simulation and it is more in the domain of game environment. They do not include any physical or dynamic features and constraints which limits this work.
- It is not clear how GenOpt can be more robust to adversarial opponents
- More ablation study and experiment for GenOpt is required
- There are some typos and punctuations that needs to be addressed during the rebuttal (please the reviewer's comment in rebuttal)
- It is mentioned the difference between the GC baseline and the proposed method is that GC baseline has a separate evaluation step, while GEMS evaluation is during training., which would reduce the complexity.  However, there is no evidence/result show that how this difference makes GEMS more desirable
questions: questions: 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
2- Figure 1: it is not clear if Ego student is GenOpt agent. Also, why having GenOpt similar to ego agent is beneficial?
3- line 120: 2 player-> 2-player or two player
4- Algorithm 1, line 14: reward -> regret?
5- It would be helpful if the author/s provide a pseudo code or algorithm for GenOpt Agent, or they improve the explanation.
6- Line 103: it seems it provides a formulation for  RL with deterministic assumption as there is not transition function in  this formulation
7- Table 1: it would be helpful if the author/s provide statistical result to show whether their method is statistically significant
8- To add more clarity, the reviewer suggests the word' (ours)' infront of the proposed method
9- 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.
10- 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.
limitations: limitations: 2
review_summary: review_summary: 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.
title: title: Review
paper_summary: paper_summary: 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).
main_review: main_review: The method as described seems relatively simple, and the results show an improvement over the baselines. I particularly like the justification of experiment and baseline selection, and attempts at fairness in the results. 

I found this paper was well written, though there were critical details of the method that weren’t clear to me (questions below). Overall I’m not convinced  of the novelty of the contribution, though this might be because I haven’t understood some of the key elements. There doesn’t appear to be a limitations section, I’m not sure if that is still a requirement for this conference. It’s also not a requirement to have real robot experiments though sim only experiments are harder to show novelty.

The method states the GenOpt agent is an optimised open-loop trajectory using genetic algorithms without supervision, but I couldn’t see any more details (even in the appendix) about the training of these. What are the specifics for each environment, what is the GenOpt Agent script (Fig1)? Similarly, what are some of the environment attributes that are mutated for each experiment? My apologies if I overlooked these.

What could be the cause of the larger number of ties compared to wins/losses? MAESTRO has significantly fewer ties for all tasks than GEMS. Perhaps GEMS formulates safer behaviours that prevent losing but are not as diverse as those generated through random exploration? 

Fictitious Self Play seems to be a strong baseline on all tasks. On what tasks does self-play induce instability? 

Formatting of equation at line 103 defining the expected return objective should include subscripts for action sampling.

“We train each algorithm for 7e6 steps in each benchmark for each benchmark” -> Double up

“regret term (σ)” (line 281) -> regret term was a delta (δ)? 

Update reference list with peer reviewed sources where possible, e.g:

T. Bansal, J. Pachocki, S. Sidor, I. Sutskever, and I. Mordatch. Emergent complexity via multi-agent competition. arXiv preprint arXiv:1710.03748, 2017. -> from ICLR 2018

M. Samvelyan, A. Khan, M. Dennis, M. Jiang, J. Parker-Holder, J. Foerster, R. Raileanu, and T. Rocktäschel. Maestro: Open-ended environment design for multi-agent reinforcement learning. arXiv preprint arXiv:2303.03376, 2023. -> ICLR 2023
questions: questions: See above
limitations: limitations: 2
review_summary: review_summary: I think there is some interesting work here, though I'm not convinced the contribution is sufficient. -> Increased score after rebuttal.
title: title: Review of Submission 545
paper_summary: paper_summary: This paper introduces a curriculum generation scheme for multiagent scenarios using genetic algorithms. The authors show positive results through extensive experiments.
main_review: main_review: ## Strength:
1. The paper is well-written and introduces most of the key concepts in the proposed methodology clearly.
2. The experiments are extensive and show positive empirical results of the proposed approach.

## Weakness:
1. A big limiting factor of the proposed approach is it’s only designed for symmetric agents in symmetric environments, namely the ego and opponent agents have the same observation and action space. The baselines being compared are more general in this aspect.
2. The problem that the paper is trying to solve is somewhat nebulous, the proposed approach, and the problem formulation itself is aimed towards curriculum learning where environment the agent is in is part of the curricular, while the baseline being compared (PSRO) is aimed towards finding approximated Nash strategy profiles for both the ego and the opponent, while less focused on the environment.
3. The proposed methodology has limited novelty since crossover/mutation is well studied in prior genetic algorithm research, and the estimated regret was introduced by prior work. Moreover, the study is mainly empirical, while a big part of the problem the paper is trying to tackle is computational efficiency when compared to other baselines, and convergence/sample complexity analysis is important to support the claims.

## Additional Comments:
1. Since the regret is estimated, and highly biased towards the current ego policy, and from the ablation results, the argument for the necessity is weak. The plateauing in Figure 5 doesn’t seem to be that important for the overall performance. It might be helpful to show the regret curve as well.
2. While I understand the need for the GenOpt agent, the implementation is not clearly described. See Question 2 for more details.

## Minor Comments:
1. In Appendix E, the GenOpt agent is referred to as the Blind Agent.
2. When introducing the estimated regret, it’ll be better to add an intuitive description of what it’s measuring (gap from the current obtained return to the maximal possible return of the level).
questions: questions: 1. I would love to hear some rebuttal to points 1 and 2 that I’ve written down in the weakness section.
2. 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?
limitations: limitations: 3
review_summary: review_summary: 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.
title: title: Review of Genetic Algorithm for Curriculum Design in Multi-Agent Reinforcement Learning
paper_summary: paper_summary: 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.
main_review: main_review: **Quality and Clarity**

The quality of the writing is high and the paper was for the most parts easy to read. The presentation is clear and concise with well done figures to help explain the underlying concepts. There are some questions remaining regarding the approach and the evaluation.

** Originality ** 

The paper introduces a new framework using genetic algorithms for curriculum generation. While the concept of curriculum generation is known, the combination of genetic modification and regulation of difficulty of scenarios is novel making this work an incremental improvement over existing work.

** Significance **

The significance of this paper is limited. This is because no theoretical guarantees are made and the range of scenarios this approach was shown on is limited to competitive multi-agent environments. Nevertheless, this work sets a new baseline in this niche.

** Strenghts **

- Clarity of idea
- Empirical Validation
- Extensive ablation studies

** Weaknesses **

- Limited scenario range (only competitive)
- Unclear Evaluation regarding negative aspects of the approach
questions: questions: Question 1:
In 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?

Question 2:
If 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?
limitations: limitations: 2
review_summary: review_summary: 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.