Automatic Curriculum Generation for Reinforcement Learning in Zero-Sum Games
Authors: Jiayu Chen
Yunfei Li
Zelai Xu
Huazhong Yang
Jiaming Song
Yu Wang
Yi Wu
Venue: Submitted to ICLR 2023 (2023)
Keywords: multi-agent reinforcement learning
curriculum learning
zero-sum games

Abstract: Curriculum learning (CL), whose core idea is to train from easy to hard, is a popular technique to accelerate reinforcement learning (RL) training. It has also been a trend to automate the curriculum generation process. Automatic CL works primarily focus on goal-conditioned RL problems, where an explicit indicator of training progress, e.g., reward or success rate, can be used to prioritize the training tasks. However, such a requirement is no longer valid in zero-sum games: there are no goals for the agents, and the accumulative reward of the learning policy can constantly fluctuate throughout training. In this work, we present the first theoretical framework of automatic curriculum learning in the setting of zero-sum games and derive a surprisingly simple indicator of training progress, i.e., the Q-value variance, which can be directly approximated by computing the variance of value network ensembles. With such a progression metric, we further adopt a particle-based task sampler to generate initial environment configurations for training, which is particularly lightweight, computation-efficient, and naturally multi-modal. Combining these techniques with multi-agent PPO training, we obtain our final algorithm, Zero-sum Automatic Curriculum Learning (ZACL). We first evaluate ZACL in a 2D particle-world environment, where ZACL produces much stronger policies than popular RL methods for zero-sum games using the same amount of samples. Then we show in the challenging hide-and-seek environment that ZACL can lead to all four emergent phases using a single desktop computer, which is reported for the first time in the literature. The project website is at https://sites.google.com/view/zacl.

Under review as a conference paper at ICLR 2023
AUTOMATIC CURRICULUM GENERATION FOR REIN- FORCEMENT LEARNING IN ZERO-SUM GAMES
Anonymous authors
Paper under double-blind review
ABSTRACT
Curriculum learning (CL), whose core idea is to train from easy to hard, is a popular technique accelerate reinforeement learning (RL) training. has also been trend to automate the curriculum generation process. Automatic CL works primarily focus on goal-conditioned RI. problems, where an explicit indicator of training progress, c.g., reward success rate, can be used to prioritize the training tasks. However, such a requirement is no longer valid in zero-sum games: there goals for the agents, and the accumulative reward of the learning policy can constantly fluctuate throughout training. In this work, we present the first the- oretical framework of automatic curriculum learning in the setting of zero-sum games and derive a surprisingly simple indicator of training progress, i.e., the Q- value variance, which can be directly approximated by computing the variance of value network ensembles. With such progression metric, we further adopt a particle-based task sampler to generate initial environment configurations for training, which is particularly lightweight, multi-modal. Combining these techniques with multi agent PPO training, we ob- tain our final algorithm, Zero-sum Automatic Curriculum Learning (ZACL). We first evaluate ZACL in a 2D particle-world environment, where ZACL produces much stronger policies than popular RL methods for zero-sum games using the same amount of samples. Then we show in the challenging hide-and-seek envi- romment that ZACL can lead to all four emergent phases using single desktop computer, which is reported for the first time in the literature. The project website is at https: htt///steeee googl com/v vii ew zacl.
and naturally
INTRODUCTION
Curriculum learning (CL) (Bengio et al., 2009), whose core idea is to generate training samples from easy to hard, is a popular paradigm to accelerate the training of reinforcement learning (RL) agents (Lazaric et al., 2008; Taylor al., 2008; Narvekar et al., 2020). Starting from simple tasks, RL agent can progressively adapt to tasks with increasing difficulty according to a properly designed curriculum, and finally solve hard tasks with fewer samples than naive RL training from scratch with uniformly sampled training tasks.
Automating the design of curriculum for RL training has attracted much research interest. An or- dinary formulation is the teacher-student framework (Matiisen et al., 2019; Portelas et al., 2020), where a "teacher" proposes task configurations that are neither too easy nor too hard for the "stu- dent" RL agent to solve. A key ingredient in order to generate suitable task configurations is to measure the progress of the learning student. In goal-oriented RL problems or cooperative multi- agent games, the training progress is straightforward to measure since the success rate for reaching a goal the accumulated reward can explicitly reflect the current performance of the student on specific task (Wang al., 2019; Florensa al., 2018; Chen et al., 2021).
However, an explicit progression metric does not exist in the setting zero-sum games, where the ultimate goal of the RL agent is no longer reaching any goal or getting high rewards. Instead, the convergence criterion to find a Nash equilibrium (NE) efficiently. The accumulated reward of policy for player would oscillate when it is exploiting or being exploited by its opponent throughout RL training. Therefore, it becomes non non-trivial to measure how "close" the current policy NE is. Existing curricula in zero-sum sum games typically based heuristics, i.e., training on

---

Under review as a conference paper at ICLR 2023
an increasing number of agents (Long al., 2020; Wang et al., 2020b) adapting other environment parameters according to domain knowledge (Berner et al., 2019; Tang et al., 2021). It remains unclear how to automate the generation process of these task parameters.
In this work, we propose a novel automatic CL framework for multi-agent RL training in zero- sum games. We theoretically derive surprisingly simple progress metric, i.e., Q-value variance, as an implicit signal of the learning progress towards an NE. By prioritizing learning on game configurations with high Q-value variance, we are implicitly tightening lower bound of the true distance between the learning policy and a desired NE. This simple metric is also straightforward to incorporate into a configuration sampler to automatically generate the training curriculum for the RL agents to accelerate convergence towards NE.
We approximate the Q-value variance by value variance and implement as the empirical uncer- tainty over an ensemble of independently learned value networks. We then develop curriculum generator that samples game configurations according to an empirical probability distribution with density defined by the value uncertainty. In order to keep track of the constantly evolving and multi-modal density landscape induced by value uncertainty throughout RL training, we adopt a non-parametric sampler that directly samples configurations from a diversified data buffer. Combin- ing the progression metric and non- con-amametrrcc curriculum generator with a multi-agent RL back- bone MAPPO (Yu et al., 2022), derive our overall automatic curriculum learning algorithm for zero-sum games, Zero-sum Automatic Curriculum Learning (ZACCL). We first evaluate ZACL in a 2D particle-worf world benchmark, where ZACL learns stronger policies with lower exploitability than existing multi-agent RL algorithms for zero-sum games given the same amount of environment in- teractions. We then stress-test the efficiency of ZACL in the challenging hide-and-seek environment. ZACL produces the emergence of all four phases of strategies only using a single desktop machine, which is reported for the first time. Moreover, ZACL also consumes substantially fewer environment samples than large-scale distributed PPO training.
2 RELATED WORK
Curriculum learning has a long history of accelerating RL training (Asada et al., 1996; Soni & Singh, 2006; Lazaric al., 2008; Taylor al., 2008; Narvekar et al., 2020). In the recent literature, automatic curriculum learning (ACL) is often applied to the goal-oriented RL setting where the RL agent needs to reach a specific goal in each episode. ACL methods design or learn a smart sampler to generate proper task configurations or goals that are most suitable for training advances w.r.t. some progression metric (Florensa et al., 2017: 2018; Racaniere et al., 2019; Matiisnn et al., 2019; Portelas et al., 2020; Dendorfer et al., 2020; Chen et al., 2021). Such a metric typically relies on an explicit signal, such as the goal-reaching reward or reward changes (Wang et al., 2019; Florensa et al., 2018; Portelas et al., 2020; Matüsen et al., 2019), success rates (Chen et al., 2021), and the expected value on the testing tasks. However, in the setting of zero-sum games, these explicit progression metrics become no longer valid since the reward associated with Nash equilibrium can be arbitrary.
There are also ACL works utilizing ewaard-agosste metrics. One representative category of meth- ods is asymmetric self-play (Sukhbaatar et al., 2018; Liu et al., 2019; OpenAl al., 2021). where two separate RL agents are trained via self-play with one agent setting up goals to exploit the other. Such self-play training framework implicitly constructs a competitive game leading to an emergent curriculum for the training agents. Some recent works have also shown that this training process can be provably related regret minimization with proper changes (Dennis et al., 2020; Gur et al., 2021). However, these methods still assume a goal-oriented problem and it remains non-trivial to adapt them zero-sum games. (Zhang et al., 2020) adopts a similar value disagreement ACL metric to tackle a collection of single-agent goal-reaching tasks, which is perhaps the most technically sim- ilar work to our method. In addition to different problem domains of interest, we remark that (Zhang et al., 2020) develops the method in purely empirical fashion while we follow complete theo- retical derivation. It is a beautiful coincidence that empirical observations and theoretical analysis converge to the same implementation even with parallel motivations.
Applying RL to solve zero-sum games can be traced back to the TD-Gammon project (Tesauro et al., 1995) and has led to great achievements in defeating professional humans in complex compet- itive games (Jaderberg et al., 2018; Berner et al., 2019; Vinyals et al., 2019). Most RL methods for zero-sum games can be proved to converge (approximate) Nash equilibrium (NE) correlated
2

---

Under review as a conference paper at ICLR 2023
equilibrium. A large body of works is based on regret minimization (Brown et al., 2019; Stein- berger et al., 2020; Gruslys et al., 2020), which assumes game rules are known. Another notable line of works adopts model-free RL algorithms with self-play training, such fictitious self-play (FSP) (Heinrich et al., 2015; Heinrich & Silver, 2016) and its variants (Jin et al., 2021; Bai et al., 2020; Perolat et al., 2022), which derives a single NE policy. It is often empirically observed that the RL agent will obtain increasingly more complex skills during the self-play training, which is often called the emergent auto-curricula (Bansal et al., 2018; Baker et al., 2020). Our work fo- cuses on how to accelerate self training to reach an NE faster rather than analyzing emergent behaviors. The self-play framework can be further extended to population- maintaining policy pool and repeatedly adding best-response policies to it, which is called the dou- ble oracle method (McMahan et al., 2003) or policy space response oracles (PSRO) (Lanctot et al., 2017). There are also PSRO-specific ACI methods for faster best-response training by construct- ing a smart mixing strategy over the policy pool according to the policy landscape (Balduzzi et al., 2019; Perez-Nieves et al., 2021; Liu et al., 2021). By contrast, our method focuses curriculum generation over low-level states or task configurations and is complementary to these meta-level CL methods. Besides, some CL methods for zero-sum games adopt domain heuristics over the number of agents (Long et al., 2020; Wang et al., 2020b) or environment specifications (Berner et al., 2019; 19; Tang et al., 2021) while our method only assumes a minimal requirement of generic state sampler.
training (PBT) by
Our work adopts a non non-parametric state sampler which is fast to learn and naturally multi-modal, instead of training an expensive deep generative model like GAN (Florensa et al., 2018). Such an idea has been recently popularized in ACL literature. Representative samplers include Gaussian mixture model (Warde-Farley et al., 2019), stein variational inference (Chen et al., 2021), Gaussian process (Mehta et al., 2020), or simply evolutionary computation (Wang et al., 2019; 2020a). Tech- nically, our method is also related to prioritized experience replay (Schaul et al., 2015; Florensa et al., 2017; Li et al., 2022) with the difference that we maintain diversified buffer (Warde-Farley et al., 2019) to approximate the uniform distribution over the state space.
3 CURRICULUM LEARNING FOR ZERO-SUM GAMES
We consider decentralized Markov decision process (Dec-MDP) denoted as S,, Po, 7). where N is the number of agents, S and A are state and action space shared across all the agents, RA, i E [I are reward functions for different agents, P denotes the transition probability, Po is the distribution of initial states, and y the discount factor. Each agent optimizes its policy n; with multi-agent reinforcement learning. We focus on mixed- coopeertteeeeeiveeee competitive zero-sum games in particular, where n out of the total N agents share the same reward function R. and the remaining N -n agents are with the reward function - R. For simplicity, we denote the joint policy distribution for the team of agents with reward R as n and the joint policy for other agents as w_ In this way, the problem setting becomes standard two-player zero-sum game. The joint policy over the two teams of agents is denoted as π, and the policy of either of the two teams is denoted as π
Curriculum learning assumes a task space T the agent is allowed to be trained over, which can be collections of initial states, environment parameters, or goals. In automatic curriculum learning, a task generator typically draws samples from T for the RL agent to train according the current performance of the policy. Without loss of generality, we assume the state contains all necessary information to construct task configuration. Therefore, a good curriculum is equivalent to smart state sampler proposing appropriate states to initialize each episode. So, in the following content, we use the terminology of state to denote the concept of task configurations in curriculum learning.
3.1 MUL.TI-AGENT RL. AS DISTRIBUTION MATCHING
In non-cooperative Markov games, it is difficult to directly evaluate the learning progress with re- spect to the reward function obtained by each individual agent. In principle, though, the learning progress could be modeled via some statistical distance between the trajectory distribution of the current agents, and that of the agents under some optimality notion, similar to a multi-agent imita- tion learning setting (Song et al., 2018; Yu et al., 2019). However, even this is hard to characterize, as we do not have access to the trajectories of the optimal agents. Ideally, we should devise our currieulum from the policies and/or value functions alone.
3

---

Under review as a conference paper at ICLR 2023
Our first step is to connect this statistical distance with value functions. Under reasonable assump- tions such as bounded rationality (McKelvey & Palfrey, 1995; 1998), it possible to characterize the joint distribution of trajectories generated by agents some equilibrium, given the Q-functions. For example, we can consider the Logistic Stochastic Best Response Equilibrium (LSBRE) introduced in Yu et al. (2019).
Definition 1 (LSBRE). The logistic stochastic best response equilibrium (LSBRE) for Markov game with horizon T a sequence of stochastic policies defined recursively via a Markov chain. The state of the Markov chain at step k for each agent at time t is (z4.(k) :S + Aijiz with each random variable 24 1,(k) (s) taking values in A.. The transition from step l to (k + 1) defined as:
(.(h)ss)
exp (AQT (s',a), 1.(k) (5*)
2.(1ht) Patla' (5), 2,
Eno exp (AQT 11: (st, z 2.(1k)
(st) (st)
recursively from = T to t = O. and E R+ controls the level of rationality of the agents. Each joint policy π at time is given by T (a1, "anl.""""llls')) = (niltz (,))))))))))))) - where the probubility is taken with respect to the unique stationary distribution of the t-th Markov chain.
Informally, the LSBRE the stationary distribution of Markov chain over the joint policy æ, whose transition kernel at step (k + 1) given all agent policies at step is defined for every agent T, as the optimal maximum entropy RL policy if all other agents are acting according to their policies at step k. This equilibrium notion naturally specifies how agents would act under cer- tain reward function (with maximum entropy regularization controlled by X). which also induces a joint distribution over the trajectory of all agents. In principle, we can then measure the learning progress in non-cooperate Markov games via some statistical distance between our current joint dis- tribution versus the joint distribution induced by LSBRE. A common choice is the KI. divergence: min, (p(s a))ls(s, a)), where p(s, a) = π (als) E Pr(s, s/π) is the occupancy mea- sure induced by our parametrized policies and p(s, a) the one induced by the LSBRE-optimal policies. Naturally, our policies reach the LSBRE when this objective is zero
However, for computational efficiency, we often would like to take pseudolikelihood approach (Be- sag, 1975), where we approximate the joint likelihood π Taass) ()) with a product of the conditionals, i.e., πt. a- s) (a_ s). Intuitively, replace the KL divergence of the joint policy with KL divergences of individual policies, and thus we replace the optimization over the joint policy with the optimization over the individual policies, where each agent updates its own policy accord- ing to the current fixed policy of other agents (as opposed to optimizing jointly). According to the LSBRE setup, each team operates under a maximum entropy (MaxEnt) RL-like setup (Haarnoja et al., 2017) conditioned on the behavior of other agents, and thus we can treat them as part of the environment, such that:
exp eXQ (s)
# (a1ls))
(2)
Eng exp (AQi (s,a²))²
where Q1 is the soft Q-function for either team. which aims to maximize the expected cumulative discounted reward along with the entropy in each state. Thus, we may represent a policy with a corresponding energy-based formulation Q+, i.e., (u+ = exp (Q= a4)), such that т is the optimal entropy-regularize or the value function are tied in MaxEnt RL, means that we may represent the learning progress with either one of the quantities.
policy under the normalized value function Q+. As the the policy
3.2 CURRICULUM FROM Q- VALUE VARIANCE
In curriculum learning, we wish to select experiences (state-action pairs) that would maximize the learning progress of the agents. Although can theoretically measure the learning progress with KL divergence to LSRBE-optimal policy, we have no access to that optimal policy in practice, so we have to rely on alternative metrics to decide the curriculum learning strategy.
For each agent, let us consider the case of learning m value functions (denoted as (f) Q!)) "......,................. ...., ((m)) in parallel; each of which induces policy " (als) = exp(Q2 (s,aa)))s)a))))))))) (s,a)) (for
4

---

Under review as a conference paper at ICLR 2023
self-play
self-play
agent
environment
agent
environment
update
reset
update
reset
oydusp
edtues
value uncertainty
value uncertainty
low
high
initial
low
high
Initial
running and chasing
fort-building
ramp-use
ramp-defense
automatic curriculum
Figure 1: Illustration of ZACL in the hide-and-seck environment. In Fort-Building stage, the states with hiders near the box are of high uncertainty (red) and the agent can easily learn to build a fort by practising these states, while the states with randomly spawned hiders are of low uncertainty (green) and contribute less to learning. By sampling the environment initial state from the density defined by the value uncertainty, the agent can proceed new stages efficiently.
j E [1, ml), and with infinite training capacity, they should all converge the optimal policy (KL divergence becomes zero). Effectively, each agent is maximizing the following':
Ex [Q1 (s, a=) log (a
(3)
where Q* the soft Q=-function that induces the optimal policy (Ziebart al., 2008) for either team of agents. In curriculum learning, we need to prioritize over more useful state-action pairs to achieve the fastest learning progress. However, as we do know the optimal policy distribution, we use surrogate to decide where we could achieve better gains, and thus use it to decide our curriculum learning strategy. Intuitively, our strategy three fold. First, we use multiple indepen- dent policies, from which we can obtain an average policy; we will prove that the average policy should perform better than individual policies acting independently. Second, for each state-action pair we characterize this performance gap, which we will tic with the disagreement of the individual policies/values. Third, if the disagreement large, then the gap between the individual policies and the average policy is also large, and the gap with the (unknown) optimal policy should also be large. Therefore, we can use the disagreement of the individual policy values to devise a curriculum.
Define ([a|s) = 1
n Σx T(5 (a(s) as the average policy produced by the m individual ones, then for any state-action pair (s, ) we have the following:
Proposition all policies T- and Q!2 such that +L = exp(Q
m
1 m
(azls)(Q1 log ()) = (s ( m
Σ (s.az)) m
We list the proof in Appendix A.2, which uses two Jensen's 's inequalitics. The differences between the ends of the Jensen inequality is known Jensen gap:
exp(Qf (s) (s, 1 m 1=1
1 Σ (s,
exp(Q (s. a1)) m 1=1
(4)
m
1=1
which is essentially the covariance between exp(Q!)) (s, a=)) and Q= (under the empirical distribu- 2 The Jensen gap becomes zero if all the Q-values equal, and maybe larger if the Q-values are more difffrrntt If we initialize the different functions randomly, then it is unlikely that they will become identical without having reached the optimal one.
For conciseness, we use = 1, which corresponds to certain degree of entropy regularization, but argument is still valid for other X > 0. As covariance is non-negative, this provides another proof angle for the proposition.

---

Under review as a conference paper at ICLR 2023
Our curriculum strategy is to choose state-action pairs that maximize the Jensen gap (which indi- rectly maximizes the gap between the individual policies and the optimal one), so intuitively we should select cases where the value functions have high disagreement with each other. To further simplify the computation, we can use Taylor approximation to connect the Jensen gap to the variance of _ (see Appendix A.1 for details).
METHOD
In this section, we describe the algorithmic components of ZACL. We first introduce value variance as progress measurement in Sec. 4.1. Then we propose non-parametric task sampler that samples the most feasible tasks according to the training progress Sec. 4.2. In Sec. 4.3, we summarize the framework and the implementation details. An overview of ZACL is illustrated in Fig.
4.1 VARIANCE ESTIMATION
Following the theoretical analysis, the uncertainty of value functions can be approximate metric of learning progress. We train an ensemble of value functions V = (Ve, ) and take the statistical variance of their predictions each state the uncertainty measurement, w(s) (s)(. The value networks in the ensemble are initialized with different random parameters. In RL training, they are trained over mini-batches using different random splits from the same environment samples.
A naive way to compute the mean policy is to train separate policies for each value function over disjoint data batches that used train the value ensemble. However, maintaining m policies is computationally expensive. Considering that we only care about learning one good policy instead of ensemble, we instead train single policy network with respect to the mean value function in practice. Taking the average of the value ensemble leads to more accurate value estimation than each individual value function and therefore can accelerate policy learning.
4.2 STATE GENERATION FROM A DIVERSIFIED BUFFER
With value uncertainty as an approximate progression metric hand, we can then treat it as the density distribution from which to sample promising states for the RL agent to train Training a neural generative model fe from which to sample states for automatic curriculum learning is a typical solution (Dendorfer et al., 2020; Fang et al., 2021), but it requires large number of samples to accurately, therefore cannot adapt instantly to the ever-changing density (value uncertainty) in our Moreover, the value uncertainty distribution is highly multi-modaa which is hard to capture for many neural generative models.
We instead adopt particle-based approach efficiently sample from the value uncertainty distri- bution. We maintain a large diversified state buffer Q using all the visited states throughout RL. training approximate the state space, then draw samples from with probability proportional to the value uncertainty associated with each state. Since the number of states we can store is limited while the state configuration space is exponentially large, it important to only keep representative states so as to ensure good coverage of the state space with limited samples. When inserting new visited states into the buffer, we only keep those states sufficiently far from existing states.
4.3 ZERO-SUM AUTOMATIC CURRICULUM LEARNING
Combining the uncertainty-bast based curriculum progression metric and the efficient state generator with an RI. backbone, we get our final algorithm ZACL for accelerating RI training in zero-sum games. When each episode resets, we use the state generator to sample good initial game config- urations. After collecting bunch of environment samples, perform policy and value training and update the density estimation for all the existing samples the state buffer with new value uncertainty. The novel states from rollout then stored into the diversified state buffer.
Implementations: We adopt a sfate-of-ther the-art multi-agent RL algorithm MAPPO (Yu et al., 2022) as the backbone. Although theoretical analysis follows the max-entropy RL framework, ZACL can empirically work with standard multi-agent RL algorithms. To avoid lack of exploration, we allow each episode start from random states with 30% probability and generated states from the

---

Under review as a conference paper at ICLR 2023
Algorithm 1:
The ZACL Algorithm
Algorithm 2: State buffer update rule
Input:
Empty state buffers and M. probability to reset from state buffer Pezp.
Input: State archive Q of capacity K; new state buffer M.
policy иe, value ensemble (V,, J= repeat
// Update old density
Output: final policy TTa
for (s, () E Q do
Recompute w using the latest value ensemble w f- Var({V (s)
So Q if rand() Pezp else 8D pos
Rollout NT:
for (s, w) E M do
Train ne, JE via MARL;
if min d(s;,s) > 8 then
// Compute uncertainty
(s1:)62
wi +- Var((Ve (s))( (s)))=)),
O....,T
Q+ (0)((s))))) w))):
Store all visited states and uncertainty
if 0 K then
M (s; we =
j k arg min; wa (5;, w;) Q:
Q - Update(Q,, Q M); 11 Alg. 2
Q t @ QM(s3 wy}:
until Ty converges;
Algo.
Best response
ZACL
96.1
Prey
R-NaD
109.0 (2.6
FSP
114.9 (7.)
Predator
PFSP
109.2 (10.1)
Obstacle
PSRO
306.4 (8.)
PSRO (3x)
176.6 (9.)
Predator-Prey
Table Exploitability of policies learned by different methods. We report the best response to the fixed poli- cies of the prey trained with different algorithms the same environment steps. Lower number is better.
Figure 2: Illustration of the Predator- Prey environment in MPE.
state generator otherwise. To ensure the state buffer has good coverage of the whole state space, only insert the new visited states that are at least distance apart from every existing state in the buffer. When the number of states grows larger than the buffer's capacity, we simply delete some states with the lowest value uncertainty. The overall algorithm is summarized in Alg. 1.
EXPERIMENT
We consider two environments, the multi-agent particle-worke environment (MPE) (Lowe et al., 2017) and the hide-and-seek environment (HnS) (Baker al., 2020). Every experiment repeated over 3 seeds. More environment and training details can be found in Appendix B.
5.1 THE MULTI-AGENT PARTICLE- WORLD ENVIRONMENT
We first test the performance of ZACL in the Predator-Pres environment of MPE. As illustrated in Fig. 2, there are three cooperative predators chasing one prey in a 2D environment with several obsta- cles blocking the way. The game configurations are the positions of all the agents and the obstacles. We choose the following basclines for solving zero-sum games: three popular self-play methods fic- titious self-play (FSP) (Heinrich al., 2015), prioritized fictitious self self-play (PFSP) (Vinyals al., 2019) and R-NaD (Perolat et al., 2022), and population-bast based training method policy-space re- sponse oracles (PSRO) (Lanctot et al., 2017) with population size of 3. We fix the policies of the prey trained at 15M environment samples for all the methods, then train the best response policy of the predators to measure the exploitability. We additionally try allowing 45M (3 times) samples for PSRO since PBT typically requires more samples. The average episodic reward of the preda- tors evaluated at convergence and the standard deviation over 3 seeds are shown in Table The exploitability of our agent is the lowest, indicating the most competitive performance of our policy.

---

Under review as a conference paper at ICLR 2023
Hiders
Door
Ramp
<-Wall Box
Seeker
A
(a) Marginal density different ini- (b) Marginal density of different ini- tial hider positions in Fort- BuiidBu.. tial ramp positions in Ramp-Use Use.
Illustration of a quadrant scenario in hide- and-seek environment.
Figure 3:
Figure 4: Density map from which to sample initial game configu- rations in different training stages. Darker means higher density.
value uncertainty
episode reward
GAE
episode reward
0.00
GAN
GMM
Uniform
-0.02
-0.02
-0.04
1.5
samples
1e8
samples
1e8
Figure 6:
Ablation on the progression met- ric. Our value uncertainty metric clearly outper- forms absolute TD error and GAE error metrics.
Figure 7: Ablation on different state samplers. Our non-parametric state generator outperforms parametric and uniform baselines.
5.2 THE HIDE-AND-SEIE ENVIRONMENT
We consider the fully-observable quadrant scenario in the hide-and-seek environment (HnS) as shown in Fig. 3. The scenario consists of a room in the lower right corner which is connected by one door the remainder of the environment. Two hiders are spawned uniformly in the environment, but one seeker is only spawned outside the quadrant room. One box is spawned inside the room and one ramp spawned outside the room. Both the box and the ramp can be locked place. We need to train policy for hiders to avoid lines of sight from the seekers and for the seeker to keep vision of the hiders. The initial states contain the positions of the agents, the box, the ramp, and the door.
As there are a total of 4 rounds of emergent strategies HoS (Baker et al., 2020), i.e., Running and Chasing, Fort-Building, Ramp-Use, and Ramp-Defense we evalu- ate the training efficiency different methods by com- paring the number of environment interactions required to master the final round of strategy in Fig. 5. We com- pare ZACL using different batch sizes on a distributed system. Note that the distributed system
7.8B
Samples (x109
5.4B
2.0B
single desktop machine with MAPPO
ZACL
Sys.(64k) (12.()
massive parallel of 9600 environment workers, and divides the collected data into batches of size 64k 128k for RL optimizing, while ZACL desktop training only uses 256 parallel workers to collect samples until the GPU memory is full in each eration, then runs RI. over all these data single batch. ZACL consumes 2.0 billion samples, ~xX more efficient than MAPPO without curriculum. We visualize the value uncertainty of different states in two training stages in Fig. 4 to see how our curriculum samples initial configurations. Fig. 3a depicts the stage when the hiders about to learn build fort. The most uncertain states are where the hider is initialized inside the fort. When the seekers are learning use the ramp (Fig. 3b), the most uncertain states the ramp initialized close the walls.
Figure 5: Number of samples required to converge to the strategy of the final stage in HnS. ZACL trained on a single desktop machine is significantly more sample efficient than MAPPO on a dis- tributed system with large batch.
8

---

Under review as a conference paper at ICLR 2023
latest
0.02
running avg
episode reward
0.00
0.6
episode
0.4
-0.02
0.2
ZACL
0.04
0.0
0.0
0.5
1.0
1.5
2.0
samples
167
samples
1e8
Figure 9: Seeker's s average episode rewards in a goal-reaching Ramp-Use Use task. Z.ACL performs comparable to a strong CL baseline VACL, which is specialized for goal-oriented problems.
Figure Comparison between assigning the latest, running average of historical or old value variance to the density in Q.
5.3 ABLATION STUDIES
The experiments in this part are conducted in the HnS environment. All the methods start training from the same checkpoint right after the Fort- Bort-Buldinn stage. In each plot, report the seeker's average episode reward w.r.t. the number environment samples.
Comparison with other progression metrics: Our value uncertainty progression metric is compared against two other reward-agnostic metrics: absolute temporal difference (TD) error |&d1 [R(s, S1+1) +V(())))) (s and absolute GAE (Schulman et al., 2015) value loss (6x and they are implemented with single value function. The results in Fig. show that the agents with value uncertainty metric learn more efficiently than the baselines.
Comparison with different state generators: We substitute our particle-based state sampler with other generators including neural generator GoalGAN (Dendorfer al., 2020), parametric Gaus- sian mixture model (Portelas et al., 2020) and a naive uniform state sampler. As shown Fig. 7, non- non-parametric method,
parametric generators (GAN and GMM) do not learn efficiently since they require a large number of samples to get accurate estimation. The uniform state sampler serves baseline show the effectiveness of any curriculum.
Ablations on the state buffer Q: To validate the necessity of updating the density in Q with the latest value variance, try two variants shown in Fig. 8: updating with the average of stored and new variance (blue), i.e. wo + (w + Var( (a((V))))) and keeping the old density (purple). Using running average performs on par to using the latest density, while using staled density significantly hurts the performance. The requirement on keeping track of the latest value uncertainty can also explain the necessity to adopt a fast non-parametric task generator.
5.4 DEPLOYMENT IN COOPERATIVE SCENARIOS
Although ZACL is motivated from zero-sum games, it is generally applicable to cooperative tasks. We consider a Ramp-Use task proposed in VACL (Chen et al., 2021), where the seeker aims to get into the lower-right quadrant (with no door opening) but is only possible using ramp. We adopt the same prior knowledge of "easy tasks" used in VACL to initialize Q and achieve comparable sample efficiency with VACL (see Fig. 9), one of the strongest CL algorithms for cooperative games.
CONCLUSION
We present ZACL, theoretically grounded automatic curriculum learning framework for acceler- ating multi-agent RL training in zero-sum games. We propose use value uncertainty as a reward- agnostic metric to prioritize sampling different game configurations. With this initial state sam- pler, the RL agent can practise more in the most uncertain tasks with respect to the learning policy throughout training, thus boosting training efficiency. We report appealing experiment results that ZACL efficiently discovers all emergent strategies using single desktop machine in the challenging hide-and-sedl environment that were originally produced with large-scall distributed training. We hope ZACL can be helpful to speeding up prototype developing in multi agltit RL, and help make RI. training complex problems more affordable the community.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Minoru Asada, Shoichi Noda, Sukoya Tawaratsumida, and Koh Hosoda. Purposive behavior acqui- sition for a real robot by vision-based reinforcement learning. Machine learning. 23(2):279-303, 1996.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference Learning Representations, 2020.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojeiech Czarnecki, Julien Perolat, Max Jader- berg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning, pp. 434-443 PMLR, 2019.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition. In International Conference Learning Representations, 2018.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th anmual international conference on machine learning. pp- 41-48, 2009,
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 1912. 2019.
Julian Besag. Statistical analysis of non-lattice data. The statistician, pp. 179-195, 1975.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International conference muchine learning, pp. 793-802 PMLR, 2019.
Jiayu Chen, Yuanxin Zhang, Yuanfan Xu, Huimin Ma, Huazhong Yang. Jiaming Song, Wang, and Yi Wu. Variational automatic curriculum learning for sparse-reward cooperative multi-agent problems. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 9681-9693, Cur- ran Associates, Inc., 2021. URL http:::ttt///tttt.tttt/ http:///occceddeeoo
heurips. cc/ paper/221// pdf.
Patrick Dendorfer, Aljosa Osep, and Laura Leal-Taixé. Goal-gan: Multimodal trajectory prediction based on goal position estimation. In Proceedings of the Asian Conference on Computer Vision, 2020.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. Advances neural information processing systems, 13:13049-33061, 2020.
Kuan Fang, Yuke Zhu, Silvio Savarese, and Fei-Fei Li. Adaptive procedural task generation for hard-exploration problems. In International Conference on Learning Representations, 2021.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse cur- riculum generation for reinforcement learning. In Conference on robot learning, pp. 482-495. PMLR, 2017.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International conference machine learning, pp. 1515-1528. PMLR. 2018.
Audrunas Gruslys, Marc Lanctot, Rémi Munos, Finbarr Timbers, Martin Schmid, Julien Perolat, Dustin Morrill, Vinicius Zambaldi, Jean Baptiste Lespiau, John Schultz, et al. The advantage regret-matching actor-critic. arXiv preprint arXiv:2008. 12234, 2020.
10

---

Under review as a conference paper at ICLR 2023
Izzeddin Gur, Natasha Jaques, Yingjie Miao, Jongwook Choi, Manoj Tiwari, Honglak Lee, and Aleksandra Faust. Environment generation for zero-shot compositional reinforcement learning. Advances in Neural Information Processing Systems, 34:4157-4169, 2021.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with
deep energy-based policies. arXiv preprini arXiv: 170.00/00... 2017.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint arXiv:1603.01121, 2016.
Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International conference machine learning, pp. 805-813. PMLR, 2015.
Max Jaderberg, Wojeiech M Czarnekki, lain Dunning. Luke Marris, Guy Lever, Antonio Garcia Cas- taneda, Charles Beatrie, Neil C Rabinowitz, Ari Morcos, Avraham Ruderman, Nicolas Sonnerat, Tim Green, Louise Deason, Joel Z. Leibo, David Silver, Demis Hassabis, Koray Kavukcuoglu, and Thore Graepel. Human-level performance in first-person multiplayer games with population- based deep reinforcement learning. arXiv preprint arXiv:1807.01281, July 2018.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning a simple, efficient, decentral- ized algorithm for multiagent rl. arXiv preprint arXiv:2 10. /4555, 2021.
Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent rein- forcement learning. Advances in neural information processing systems, 30, 2017.
Alessandro Lazaric, Marcello Restelli, and Andrea Bonarini. Transfer of samples in batch rein- forcement learning. In Proceedings of the 25th international conference on Machine learning, pp. 544-551, 2008.
Yunfei Li, Tao Kong, Lei Li, and Yi Wu. Learning design and construction with varying-sized mate- rials via prioritized memory resets. In 2022 International Conference on Robotics and Automation (ICRA), pp. 7469-7476, 2022. doi: 10. 10.1109/CRA4466399... 2022.9812221 1624..
Hao Liu, Alexander Trott, Richard Socher, and Caiming Xiong. Competitive experience replay. In International Conference Learning Representations, 2019.
Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjie Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. Advances in Neural Information Processing Systems, 34:941-952 2021.
Qian Long, Zihan Zhou, Abhinav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. Evolutionary popu- lation curriculum for scaling multi-agent reinforcement learning. In International Conference on Learning Representations, 2020.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-competiivve environments. In Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
Tambet Matisen, Avital Oliver, Taco Cohen, and John Schulman. Seacher-student curriculum learn- ing. IEEE transactions neural networks and learning systems, 2019.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for extensive form games. Experimental economics, 1(1):9-41, 1998.
Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by adversary. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pp. 536-543, 2003.
Bhairav Mehta, Manfred Diaz, Florian Golemo, Christopher J Pal, and Liam Paull. Active domain randomization. In Conference Robot Learning, pp. 1162-1176. PMLR, 2020.

---

Under review as a conference paper at ICLR 2023
Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey, Journal of Machine Learning Research, 21((81):1-50, 2020.
OpenAl OpenAI, Matthias Plappert, Raul Sampedro, Tao Xu, Ilge Akkaya, Vineet Kosaraju, Peter Welinder, Ruben D' DaSa, Arthur Petron, Henrique Ponde de Oliveira Pinto, Alex Paino, Hyeonwoo Noh, Lilian Weng, Qiming Yuan, Casey Chu, and Wojeiech Zaremba. Asymmetric self-play for automatic goal discovery in robotic manipulation, 2021.
Nicolas Perez-Nieves, Yaodong Yang. Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang- Modelling behavioural diversity for learning in open-ended games. In International Conference on Machine Learning, pp. 8514-8524. PMLR, 2021.
Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. arXiv preprint arXiv:2206, 15378, 2022.
Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre-Yves Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments. In Leslie Pack Kael- bling, Danica Kragic, and Komei Sugiura (eds.), Proceedings of the Conference on Robot Learn- ing. volume 100 of Proceedings of Machine Learning Research, pp. 835-853. PMLR, 30 Oct-Ol html.
Nov 2020. URL https: http///oooceddeeeeee/e ngs. mml.ppress vv 00/ htt.0/ootelaa2200
Sebastien Racaniere, Andrew K Lampinen, Adam Santoro, David P Reichert, Vlad Firoiu, and Timothy P Lillicrap. Automated curricula through setter-solver interactions. arXiv preprint arXiv: 1909. /2892, 2019.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv: .59..,955222.2 2015.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-
Dimensional continuous control using generalized advantage estimation. arXiv preprint 0rXiv:1506.02438 June 2015.
Jiaming Song, Hongyu Ren, Dorsa Sadigh, and Stefano Ermon. Multi-agent generative adversarial imitation learning. 2018.
Vishal Soni and Satinder Singh. Using homomorphisms to transfer options across continuous rein- forcement learning domains. In AAAI, volume 6, pp. 494 499, 2006.
Eric Steinberger, Adam Lerer, and Noam Brown. Dream: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006. 10410, 2020.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fer- gus. Intrinsic motivation and automatic curricula via asymmetric self-play. In International Conference Learning Representations, 2018.
Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang. Simon Shaolei Du, Yu Wang, and Yi Wu. Discovering diverse multi-agent strategic behavior via reward ran- domization. In International Conference on Learning Representations, 2021. URL https: // //openreview. tttp://wwww...eeoooooeeeooaaaaaa dew.rummmdd-VATTSSEE..
Matthew E Taylor, Gregory Kuhlmann, and Peter Stone. Autonomous transfer for reinforcement learning. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 1, pp. 283-290, 2008
Gerald Tesauro al. Temporal difference learning and td- gammon. Communications of the ACM, 38(3):58-68, 1995.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czamecki, Michaël Mathieu, Andrew Dudzik, Juny- oung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)3300-3555 2019.
12

---

Under review as a conference paper at ICLR 2023
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. Poet: open-ended coevolution of environments and their optimized solutions. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 142-151, 2019.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeffrey Clune, and Kenneth Stanley. Enhanced poet: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In International Conference on Machine Learning, pp. 9940- 9951. PMLR, 2020a.
Weixun Wang, Tianpei Yang, Yong Liu, Jianye Hao, Xiaotian Hao, Yujing Hu, Yingfeng Chen, Changjie Fan, and Yang Gao. From few to more: Large-scale dynamic multiagent curriculum learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7293- 7300, 2020b.
David Warde-Farley, Tom Van de Wiele, Tejas Kulkarni, Catalin Ionescu, Steven Hansen, and Volodymyr Mnih. Unsupervised control through non-parametric discriminative rewards. In In- ternational Conference on Learning Representations, 2019.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang. Alexandre Bayen, and Yi Wu. The surprising effectiveness of PPO cooperative multi-agent games. Thirty-sixth Conference on Neural Information Processing Systems Dutasets and Benchmarks Truck, 2022. URL https:
fontt//foruee / wttprr/wwwiieeeeettooooteeeeeeee 112F.
Lantao Yu, Jiaming Song, and Stefano Ermon. Multi-agent adversarial inverse reinforcement learn- ing. In International Conference on Machine Learning, pp. 7194-7201. PMLR, 2019.
Yunzhi Zhang, Picter Abbeel, and Lerrel Pinto. Automatic curriculum learning through value dis- agreement. Advances in Neural Information Processing Systems, 33:7648-76635 2020.
Brian D Ziebart, Andrew L. Maas, Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In AAAI, volume 8, pp. 1433-1438, 2008
13

---

Under review as a conference paper at ICLR 2023
A METHOD DETAILS
A.1 FIRST ORDER APPROXIMATION OF COVARIANCE
Denote M E[Q+] the empirical mean. We can perform second-order Taylor expansion as for the covariance of two random variables X and Y as follows:
1 (D)) ((()
Covlf)(X) ((((())
(5)
Applying X = = = Q. fi exp and fz as identity function, we have that
Cov(exp(Q),, Q] ~ exp (M) Cov(Q, Q] exp (M) Var Q]
(6)
which relates the covariance between exp(Q) and Q to the variance of Q.
A.2 PROOFS
Proposition For all policies Lh and Q such that T6)) = cxx(((lT)
1
m
70 (atss) (s, log x (a+ls) (s=
1 _ Σ (s.
m
m
m
Proof. First, from the convexity of (xx lo we can apply Jensen's inequality to m:
((g=((1)))
(7)
Therefore:
( (alls)(Qissaa)) log (a=ls) S (ss log
(8)
Then, from the concavity of g(x) = log x we can apply Jensen's inequality to Q:
m
log (ag=(a=s)) log
(s 2 m
(s,
m
Thus:
1 (1)))))Q1((aaa - log (5) (a+ls)) <
- log (a==(s)) 1s)]
Σ
Q
U (s.
which completes statement.
B IMPLEMENTATION DETAILS
B. TRAINING DETAILS
Predator-Prey: In this 2D environment, three predators and one prey are randomly generated in a square area with side length of 1.0. There are also two obstacles uniformly initialized in the scene. The environment is fully observable, with states defined as concatenation of the positions, velocities and types of all the agents and obstacles. At each timestep, the agents can choose to move unit from four different directions take idle action. Whenever predator catches the prey, all predators get + 10 reward and the prey gets -10 reward. We adopt a simple MLP architecture for PPO training. All
for training listed in Table 2.
14

---

Under review as a conference paper at ICLR 2023
Quadrant scenario in HnS: The environment is fully observable and the observation is catenation of positions and velocities all the agents, the box, the ramp, and also the indicators representing whether the box and ramp locked. In this environment, when the hider is spotted, the seeker gets a reward of +1. Otherwise, the hider gets +1. We adopt the same network architec- ture (Baker al., 2020), where the states for each entity, i.e., the agent itself, the other agents, the box and the ramp, are first normalized and encoded with fully connected linear layers, then fused with self-attention network. We then average-poot entity embeddings and concatenate this pooled representation to z-elf- Finally the pooled-represence representation is sent into another dense layer and LSTM before outputting actions. All parameers of are listed in Table 3.
Non-compeeitive Ramp-Use scenario in HnS: In this scenario, we use the same network architec- ture and prior knowledge for defining easy tasks as (Chen al., 2021). The initial states in have the ramp right next to the wall, and agents located next to the ramp. All hyper-parameter are listed Table 4.
Table 2: ZACL. hyper-parameters used in the particle-world environment.
Value
Learning rate
5e-4
Discount rate (?)
0.99
GAE parameter (AGAE)
0.95
Gradient clipping
20.0
Adam stepsize
le-5
Value loss coefficient
Entropy coefficient
0.01
Parallel threads
100
PPO clipping
0.2
PPO epochs
4
Horizon
Pexp
0.7
Ensemble size m
3
State distance threshold 5
1.0
Capacity K
2000
Table 3: ZACL hyper-parameters used in the hide-and-seek environment.
Hyper- parameerass
Value
Learning
3e-4
Discount rate (7)
0.998
GAE parameter (AGAE)
0.95
Gradient clipping
5.0
Adam stepsize
le-5
Value loss cocfficient
Entropy cocfficient
0.01
PPO clipping
0.2
Chunk length
10
PPO epochs
4
Horizon
Mini-batch batch size
57600 chunks of timesteps
Size of embedding layer
128
Size of MLP layer
256
Size of I.STM layer
256
Residual attention layer
32
Weight decay coefficient
10
Pesp
0.7
Ensemble m
3
State distance threshold
2.0
Capacity K
10000
15

---

Under review as a conference paper at ICLR 2023
Table ZACL hyper-parameters of goal-reaching scenarios used in the hide-and-seck environment.
Hyper-paramese parameters
Value
Learning rate
5c-4
Discount rate (7)
0.99
GAE parameter (AGAE)
0.95
Gradient clipping
20.0
Adam stepsize
le-5
Value loss coefficient
Entropy coefficient
0.01
PPO clipping
0.2
chunk length
10
PPO epochs
Horizon
60
Parallel threads
300
Peap
0.7
Ensemble m
3
State distance threshold
2.0
Capacity K
2000
Pexp =
-0.02
episode reward
Pexp 0.9
Peup 0.1
-0.03
-0.04
-0.05
0.0
0.2
0.4
0.6
0.8
1.0
samples
1e8
Figure 10: Ablations on the ratio Peup of sampling initial environment states from the diversified buffer. P Peup should be sufficiently large to ensure good performance.
B.2 MORE RESULTS
Exploration exploitation trade-off: The initial states are sampled from mixture uniform dis- tribution and estimated value uncertainty density in the main results of hide-and-seck environment. We compare the performance using different ratios Pezp = 0.1,0.7, 0.9 to reset from the diversified buffer in Fig. 10. When Peup is too small, the training progress slows down since the agent not effectively utilize the curriculum using insufficient high-uncertainty reset states. When Peup is close 1, the performance becomes slightly worse. We set Peup to 0.7 it empirically achieves good balance between exploration and exploitation.
16


Reviews:
[{"review_id": "vvOCl-MYx1B", "reviewer": "Reviewer_EQHM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a theoretical framework for automatic curriculum generation in the setting of zero-sum games using the Q-value variance as an implicit signal of the learning progress toward the convergence criterion (Nash Equilibrium).\nThe theoretical derivation solves a problem of distribution matching for multi-agent RL, optimizing energy-based policies due to a statistical distance to an LSBRE optimal policy. The proposed method ZACL (Zero-sum Automatic Curriculum Learning) optimizes Jensen's gap between the Q-function of the individual policies and the average policy, which is equivalent to the value disagreement proposed for goal-directed problems in [1].\nThe variance of the value is approximated using an ensemble of value functions. Tasks are sampled from the value uncertainty distribution using a non-parametric particle-based sampler. The method uses the MAPPO algorithm to train the agents, with some tricks to improve exploration and control the replay buffer.\nThe experimental section evaluates the method in two environments; MPE and HnS. The results suggest performance gain and verify most of the claims in the paper.\n\n[1] Zhang, Y., Abbeel, P., & Pinto, L. (2020). Automatic curriculum learning through value disagreement. Advances in Neural Information Processing Systems, 33, 7648-7659.", "summary_of_the_review": "Some of the claims of the paper weren’t evaluated, like the ones mentioned in the comments.\nThe technical contributions are marginal and not significant, given the previous work on using the value disagreement [1].\nThe experimental contributions are marginal as well, where the evaluation is similar to the VARL [2] paper.\nGiven that, the paper is marginally below the acceptance threshold. \n\n[1] Zhang, Y., Abbeel, P., & Pinto, L. (2020). Automatic curriculum learning through value disagreement. Advances in Neural Information Processing Systems, 33, 7648-7659.\n\n[2] Chen, J., Zhang, Y., Xu, Y., Ma, H., Yang, H., Song, J., ... & Wu, Y. (2021). Variational Automatic Curriculum Learning for Sparse-Reward Cooperative Multi-Agent Problems. Advances in Neural Information Processing Systems, 34, 9681-9693.\n\nPost-rebuttal feedback\n------------------------------\nI have read the revised version and found few significant improvement. Thus, I'll keep my score.\n", "strength_and_weaknesses": "The authors haven’t mentioned nor compared to Neural Auto-Curricula [1], which is also a method for automatic curriculum generation in zero-sum games. This is essential given the claim in the abstract that ZACL is the first method to tackle the problem.\nIn related work, the paper states that the method is faster than emergent behavior methods, this claim is not supported in the results.\nIn the paragraph after equation 2, the energy-based formulation should be approximate, not exact. Equation 8 the Q function needs +-.\nIn the experimental section, the comparison to baseline methods was only in the easy MPE environment, while we see only comparisons to MAPPO and ablations in HnS.\nIt would be useful to report the time of the training time when assuring using a single desktop machine as a major contribution (given the method needs 2.0 billion samples in figure 5).\n\n[1] Feng, X., Slumbers, O., Wan, Z., Liu, B., McAleer, S., Wen, Y., ... & Yang, Y. (2021). Neural auto-curricula in two-player zero-sum games. Advances in Neural Information Processing Systems, 34, 3504-3517.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "qvgW-yCb2wf", "reviewer": "Reviewer_L9ZZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper ZACL, a curriculum method for self play, where the policy is incentivized by the variance of the Q function", "summary_of_the_review": "Overall, I think the method is not well-motivated, and the experiments do not convince me that it indeed (1) finds a NE, and (2) converges faster than baselines. ", "strength_and_weaknesses": "I liked that this paper was able to replicate and improve on the results from the OpenAI hide and seek paper with much less compute. However, there are a number of issues with this paper. \nFirst, I don’t think the motivation is there. If you are already doing self play, why do you need a curriculum? Usually the idea is that you need to use a curriculum to scale up to hard tasks, but the point of the OpenAI paper was to show that self play is an automatic curriculum. \nSelf play isn’t guaranteed to converge to Nash in two-player zero-sum games, and MAPPO is a cooperative RL algorithm\nI don’t understand why PSRO is exploitable by a best response. By design, upon convergence PSRO is not exploitable by a best response. How many iterations did you train it? Could you show approximate exploitability over time for all algorithms? Also, comparisons to CFR-based methods such as ESCHER would help the evaluation. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Al9PZmG1VZt", "reviewer": "Reviewer_5rst", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a method for choosing an auto curriculum strategy: a big buffer with all visited states is preserved, and the initial state for starting a trajectory is sampled from it proportionally to the variance of a number of value functions trained jointly with the policy.\n\nThe method is motivated by the lack of progression metric in 0-sum games, where the absolute value of the reward doesn't correspond to the progress in training where multiple agents are training in parallel.\n\nAuthors also provide a mathematical motivation of using the Q-value variance, under the assumption of using a MaxEnt policy with a fixed $\\lambda$ parameter.\n\nThe experiments consist of a simple Predator-Prey environment where the proposed method (ZACL) is compared against a number of 0-sum alternatives, and 4 rounds in the hide-and-seek (HnS) environment (where the goal is to converge to a Nash equilibrium as quickly as  possible), where MAPPO is used as a baseline.", "summary_of_the_review": "Overall, the proposed method is reasonable, but with little novelty. I find the authors' claim on \"complete theoretical derivation\" of the work to be an overstatement, given that the empirically evaluated method differs significantly from the one being derived. Similarly, I don't find the 0-sum motivation matching the content of the paper.\n\nI find the proposed evaluation task very interesting, but provided results are not detailed enough to be confident that it provides a useful signal to evaluate CL methods on.\n\nedit: after the usage of HnS task was pointed out by another reviewer, I decided to decrease the score from 5 to 3, given the (unchanged) review above, claiming the task is the novel part of the paper.", "strength_and_weaknesses": "## Strengths\n\nThe results on hide and seek sound impressive, and the ones for Predator-Prey are evaluated against good baselines.\n\nThe proposal of using convergence time on HnS is an interesting idea, and a useful contribution on its own, as it could become a common tool for evaluating curriculum learning methods.\n\n## Weaknesses\n\nI don't find the argumentation behind concentrating on 0-sum (the rewards are not growing) convincing, as there is a lot of work that define progress in 0-sum games this way or another (apart from the cited PSRO-derived ones, eg. [1] claims size of a NE is a useful measure of progress). Furthermore, the mathematical motivation behind the method nor the method itself doesn't use the assumption of the game being 0-sum in any way, which makes the 0-sum part unintuitive.\n\nThe mathematical analysis provides a motivation for a significantly different method:\n\n1. One that uses Q functions, and not value functions. There is no explanation provided on why using V provides an accurate approximation to Q. I don't understand why authors couldn't use Q-function (with actions sampled from the policy) instead, following their motivation.\n2. A Maximum entropy one.\n3. One with a fixed entropy weight, which on its own is a relatively strong assumption in a Curriculum Learning setting, where we may want to decrease entropy penalty over the course of training as the policy gets better and better.\n\nThe comparison with MAPPO on HnS doesn't provide enough detail to be properly judged: it's not clear what machine is used in both cases: the phrasing of the paper makes me assume that for ZACL there is a single GPU, able to process 2B samples in a single batch, but that seems beyond the current hardware possibilities. It's not clear why MAPPO uses 9600 workers while ZACL 256 and why the batch sizes are significantly different between the methods. Finally, it would be useful to test one of the other SOTA methods (eg. from the ones tested on Predator-Prey) on this task for a reliable comparison.\n\nAs authors correctly cite, a very similar method for optimizing the tasks based on maximizing a Q-value variance was proposed in 2020.\n\n## Future work suggestion\n\nOne unaddressed issue of the maximizing-variance method is the variance coming from the environment. If there are tasks which inherently possess such variance (eg. there are two doors chosen randomly and if the agent chooses wrongly, it's not able to get to the goal), they will always be on top of the priority queue, even when with the optimal policy of the agent, wasting environment interaction on tasks where nothing else could be improved.\n\n[1]: Czarnecki et al. [Real World Games Look Like Spinning Tops](https://arxiv.org/abs/2004.09468)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject