Negatively Correlated Ensemble Reinforcement Learning for Online Diverse Game Level Generation
Authors: Ziqi Wang
Chengpeng Hu
Jialin Liu
Xin Yao
Venue: ICLR 2024 poster (2024)
Keywords: Level Generation
Video Games
Deep Reinforcement Learning
Ensemble Learning
Regularisation
Primary area: reinforcement learning
TL;DR: This paper proposes a regularised ensemble reinforcement learning approach with policy regularisation theorems to train generators that generates diverse and promising game levels in real-time.

Abstract: Deep reinforcement learning has recently been successfully applied to online procedural content generation in which a policy determines promising game-level segments.  However, existing methods can hardly discover diverse level patterns, while the lack of diversity makes the gameplay boring. This paper proposes an ensemble reinforcement learning approach that uses multiple negatively correlated sub-policies to generate different alternative level segments, and stochastically selects one of them following a selector model. A novel policy regularisation technique is integrated into the approach to diversify the generated alternatives. In addition, we develop theorems to provide general methodologies for optimising policy regularisation in a Markov decision process. The proposed approach is compared with several state-of-the-art policy ensemble methods and classic methods on a well-known level generation benchmark, with two different reward functions expressing game-design goals from different perspectives. Results show that our approach boosts level diversity notably with competitive performance in terms of the reward.  Furthermore, by varying the regularisation coefficient, the trained generators form a well-spread Pareto front, allowing explicit trade-offs between diversity and rewards of generated levels.

Published as a conference paper at ICLR 2024
NEGATIVELY CORRELATED ENSEMBLE REINFORCE- MENT LEARNING FOR ONLINE DIVERSE GAME LEVEL GENERATION
Ziqi Wang".2, Chengpeng H Jialin Liu Xin Yao
1 Department of Computer Science and Engineering,
Southern University of Science and Technology
2 Research Institute of Trustworthy Autonomous Systems,
Southern University of Science and Technology
3 DDpaarment of Computing and Decision Sciences, Lingnan University (wangzq2021, hucp2021 @maill. sustech. cn, siujl@sustech.oo edu. on, xinyaoθ 1n_ www.uu..euuhhhhemmmmmmmmmm
edu.
ABSTRACT
Deep reinforcement learning has recently been successfully applied to online pro- cedural content generation in which policy determines promising game-level segments. However, existing methods can hardly discover diverse level patterns, while the lack of diversity makes the gameplay boring. This paper proposes an ensemble reinforcement learning approach that uses multiple negatively corre- lated sub-policies to generate different alternative level segments, and stochasti- cally selects one of them following a dynamic selector policy. A novel policy regularisation technique is integrated into approach to diversify the generated alternatives. In addition, we develop theorems to provide general methodologies for optimising policy regularisation in a Markov decision process. The proposed approach is compared with several wate-offtheeart policy ensemble methods and classic methods on a well-known level generation benchmark, with two differ- ent reward functions expressing game-design goals from different perspectives. Results show that our approach boosts level diversity notably with competitive performance terms of the reward. Furthermore, by varying the regularisation coefficient values, the trained generators form a well-spread Pareto front, allowing explicit trade-offs between diversity and rewards of generated levels.
INTRODUCTION
Continuously generating new content in game level in real-time during game-playing, namely online level generation (OLG), is important demand from the game industry (Amato) (017]. Recent works show that reinforcement learning (RL) is capable of training generators that can offline generate levels satisfy customised needs using carefully designed reward functions (Khalifa al., 2020 Huber et al. 2021). Inspired by those works, Shu et al. (202T) propose the experience-driven procedural content generation (PCG) via RI (EDRL) framework, in which an RL policy observes previously generated level segments and determines the following segment in real-time during game- playing. EDRL shown to be efficient and effective in generating promising levels (Shu et al.) 2021 Wang al. 2022). Then, Wang et al. (2023) show that levels generated by EDRL can be quite similar, i.c., lacking diversity. Diversity is one of the essential characteristics for levels since similar levels make players bored soon (Koster) 2013 Gravina al. (019). Research interests in generating diverse levels have a long history of at least two decades (Greuter et al. 2003
Togelius
al. 2011) and has been rapidly growing over the past few years (Gravina al.]
2019 Liu al.;
2021 Guzdial et al.) (022). However, to the best of our knowledge, no work has tackled the issue
of limited diversity of levels online generated by RL policies yet.
"Corresponding author.

---

Published as a conference paper at ICLR 2024
There are mainly two limitations in existing deep RL algorithms for learning to online generate di- verse game levels. Firstl, existing deep RL algorithms typically use a greedy or unimodal stochastic policy. Such policy has limited capability of representing complex and diverse decision distribu- tion (Ren et at.) 2021), thus it is hard to enable diverse level generation. Secondly, the diversity being concerned in this work is about the variations among the generated levels. In the context of OLG via RL, it is induced by the probability distribution of trajectories from the Markov decision process (MDP), A reward function only evaluates single actions, but is not aware of the entire MDP- trajectory distribution. Therefore, one can hardly formulate reward function to express diversity.
To address the two challenges, this paper proposes an en- semble RL approach which performs a stochastic branch- ing generation process, namely negatively correlated en- NCERL semble RI. NCERI, uses multiple individual ac-
Reward (e-g.. is playable" how fun it to play")
tors to generate different alternative level segments. A selector policy is employed to determine the final output
State (Ohservation)
Abrmartis
(Action Spuce)
segment from the alternatives. Figure T shows a diagram
Selestor Instiviitel Actors
of the approach. To diversify the generated alternatives, NCERL incorporates a negative correlation regularisation to increase the distances between the decision distributions determined by each pair of actors. As the regularisation evaluates the decision distributions rather than the action instances, traditional RL methodologies do not directly work for it. To tackle this problem, we derive the reg- ularised versions of the policy iteration (Sutton & Barto 2018) and policy gradient (Sutton et al., 1999) to provide fundamental methodologies for optimising policy regular- isation in an MDP. Those theorems can derive general loss functions to establish regularised off- off-policy and on-policy deep RL algorithms, respectively. Furthermore, the re- ward evaluation in OLG tasks usually relies simulating a game-playing agent on the generated levels, which is time-consuming. Our work also reduces the time cost of training OLG agents by designing asynchronous off-policy training framework.
jing
Decoder
92
J Select
Actor Selection Distribution
Figure 1: Overview of our approach. The decoder g maps a continuous ac- tion
segment. The selector out- puts a probability vector B. One of the individual actors T, will be selected following B to generate a new seg- ment. S the notations.
Main contributions of our work are as follows: (i) we propose an ensemble RL approach with a novel negative correlation regularisation to promote the diversity of levels online generated by RL policies; (ii) regularised versions of policy iteration and policy gradient theorems are derived to illustrate how the policy regularisation can be optimised: (iii) comprehensive experiments show that by using different regularisation coefficient values, our approach produces a wide range of non-dominated policies against state-of-the-art policy ensemble RL methods, in terms of cumulative reward and diversity of generated levels. This makes it possible to make trade-offs based on specific preferences. Code and results are available at pettts://githhnn com/ htt////nuu//N/CCC Diverse- Pereesse-CGGG http::////gg.a.b..oooo//////////
BACKGROUND AND RELATED WORK
Procedural Content Generation via RL PCG has been investigated for decades (Togelius al.
2011 Yannakakis & Togelius| 2018 Risi & Togelius 2020 Liu et al. [202 Guzdial et al. 2022) RL has been applied to a variety of offline PCG tasks, including level generation (Susanto & Tjan-
drasa 2021) and map generation (Khalifa et al. 2020 Earle et al. 2021 Jiang et al. 2022). and shown to be powerful on those tasks. However, those works focus on offline content generation, where the content is determined before same-playing. Besides, RI. has also been applied to mixed- initiative or interactive PCG (Guzdial et al.) 2019), which considers the interactions between human designers and content generators. The focus of this work is generating diverse levels in an online manner. The word "online" not only refers to real-time generation but also implies the considera- tion of player experience while generating new content (Yannakakis & Togelius 201 1). Therefore, our work is more aligned with player-centered approaches, rather than interactive PCG or mixed- initiative systems (Guzdial et al. 2019).
Recently, research interest in online PCG via RL has been raised. Compared to traditional methods for online PCG like rule-based methods (Stammer et al. 2015 Jennings-Teats al. 2010) and
2

---

Published as a conference paper at ICLR 2024
search-based methods (Shaker et al. 2012 de Pontes al. 2022). ,. the RL-based methods rely on little domain knowledge and are scalable. Shu et al. (2021) introduce the EDRL framework to online generate playable, fun and historically deviated levels. Wang et al. (2022) propose model to estimate player experience and use EDRL to train generators that optimise the experience of playing the online generated levels. RL has also been applied specific online PCG scenarios including
dynamic difficulty adjustment (Huber et al., [202)), music-driven level generation (Wang & Liu 2022) and adaptive virtual reality exposure therapy (Mahmoudi-Nejad et al. 2021). In research of OLG via RL, the limited diversity of generated levels has been reported by Wang & Liu (2022) and
[Wang et al. (2023) but not addressed yet. Our work implements EDRL as the online PCG framework and specifically focuses on the RL part of it to improve diversity.
Methods for Diverse Game Content Generation In offline PCG, it is applicable to formulate the contribution of an individual to the diversity and generate set of diverse game content grad- ually given the formulation. A representative method is novelty search (Preuss et al., 2014. Liapis
al. 2013). Beukman al. (2022) integrate neuroevolution and novelty search to evolve multi- plc generators to online generate diverse levels. Another popular method is quality-diversity (QD) search (Gravina et al. 2019 Fontaine al., 2021). which searches for the best quality content under each possible attribute or behaviour combination. QD search has been applied to offiin PCG (Grav- iiaa et al.] 2019 |oontaine al.) 2021, Guzdial al., 2022]. mixed-initiatiie PCG (Alvarez et al., 2019) and has also been integrated with RL to train diverse policies (Tjanaka et al.) (022). However, searching for game content is typically slower than generating content via machine learning mod- els, thus existing novelty search and QD search approaches are not likely efficient enough to realise real-time generation. Moreover, the QD method is powerful for problems with some attribute or behaviour descriptors to express diversity haviour space, while our work does not use such descriptors. Besides, Nam et al. (2021) use RI. to generate role-playing game stages and use diversity-enhancing strategy based on some rules.
the coverage over the corresponding attribute or be-
Population-based RL Population- RI. is used for variety of aspects. /Saphal et al. 22021) select diverse subset from a set of trained policies to make decisions. ACE (Zhang & Yao 2019) combines tree search and policy ensemble for better sample efficiency and value prediction. À number of works consider the population diversity in policy ensemble to encourage the explo- ration. SUNRISE (Lee et al. 2021) integrates several enhancement techniques into ensemble RL. PMOE (Ren et al. 2021) leverages multimodal ensemble policy to improve the exploration ability of RL agents. PPakee-Hollder et al. (2020) define population diversity the determinant of an em- bedding matrix and show that incorporating such a diversity formulation into the training objective generally improves the reward performance of RL algorithms. Yang al. (2022) integrate a regu- larisation loss to enhance the decision diversity of ensemble policy. Diversity of policy population also concerned in multi-agent RL. For example, Cui al.
(2023) propose adversarial diversity
to produce meaningfully diverse policies, Lupu et al. (202 propose trajectory diversity to enable al.
more robust zero-shot coordination, while Charakorn train a population of diverse policies. While diversity in policy populations has been explored in the aforementioned works, our work uniquely extends this consideration to the context of PCG, making diversity primary goal alongside reward. Our ensemble policy uses selector and multiple indi- vidual actors, which is similar to hierarchical RL (Pateria et al.) (02T] and skill discovery (Konidaris & Barto 2009). However, our method features novel diversity regularisation.
(2023) propose compatibility gap to
Regularisation in RL According to (Sheikh et al. 2022). regularisation methods in RL are applied for better exploration (Grau-Moya et al., 2019 Haarnoja et al. (2018a), generalisation (Farebrother et al. 2018) and other aspects that promote overall rewards (Sheikh et al. 2022; Grau-Moya et al.) 2019 Cheng et 2019 Galashov et al.). The works of (Sheikh et al. [022 Yang et al. 2022) study a combination of ensemble and regularisation. Different from our approach, the former regularises network parameters rather than policy behaviour, while the latter focuses on discrete action space rather than the continuous action space addressed in this work. The work by Haarnoja et al. (201 Sa) integrates an entropy regularisation for the decision distribution determined by the policy. Compared with their work, this work extends their theoretical results from entropy regularisation to general regularisation. Moreover, we derive the policy gradient for regularisation, which is a basis of on- policy deep RL algorithms but is not discussed in the work by Haarnoja et al, (2088)).
3

---

Published as a conference paper at ICLR 2024
3 NEGATIVELY CORRELATED ENSEMBLE RL
This section introduces the problem formulation, then describes our proposed ensemble approach, called negatively correlated ensemble RL (NCERL). NCERL features multimodal ensemble policy and a negative correlation regularisation, to address the two aforementioned limitations.
Problem Formulation According to (Sutton & Barto 2018), a general MDP M consists of a state space S, an action space A and its dynamics defined by a probability (density) function a) over x IR S x A, where s E S and s' E are the current and next state, re- spectively, E R C R is reward, and a E A is the action taken at In addition, an initial state distribution is considered, with (s) denoting its probability (density) at 8 for any E S. A pol- icy π is the decision maker which observes state and takes an action stochastically following a probability (density) of (a)ss, s). at each time step. The interaction between и and M induces a trajectory (So: Ag, Ro).... (St, Ar, R2). .... Our work uses decoder trained via generative ad- versarial networks (Goodfellow et al. 2014 Volz et al. latent vector to game level segment. The action is latent vector. The state is represented by fixed number of latent vectors of recently generated segments. These latent vectors are concatenated into a single vector. Conventionally, the initial state is a randomly sampled latent vector. If there are not enough segments generated to construct a complete state, zeros will be padded into the vacant entries. The reward function is defined to evaluate the newly generated segment.
2018) to map low -imeennnni continuous
3.1 MULTIMODAL ENSEMBLE POLICY
Similar to (Ren al. 2021 use multimodal ensemble policy that makes decisions following Gaussian mixture models. The ensemble policy и consists of m sub-policies, namely T Tms and weight function B(-)= S + RT The decision distribution determined by т at state 8, namely (-]s), can be viewed as an m-component Gaussian mixture model. Each component (-Is) is the decision distribution determined by म,
while its mixture weight (s)s is given by the weight function with >x1 (x) = holds. Specifically in this work, the components are i.i.d. spherical Gaussian distributions, and their means and standard deviations
denoted by (s) and (s),,
i.c., Ty (-(s) = N (s) o, (s) The ensemble policy samples sub-policy based on the weight vector (s)) first, and then samples an action with the sub-policy ni i.c., the final output a (-(ss).
We use m + 1 independent muti-layer perceptrons (MLPs) to model the ensemble policy. Each of the m sub-policies is modelled by an individual actor using an MLP, while the weight function is modelled by selector using an additional MLP. We regard the m + 1 MLPs as a union model with multiple output heads, though they do not share any common parameters. The union of their parameters is denoted by 0. The 2h individual actor outputs two vectors 14 (s) and of (s), and the selector outputs an m-dimensional vector 3 (s) that represents the mixture weights.
3.2 NEGATIVE CORRELATION REGULARISATION FOR DIVERSITY
Inspired by (Liu & Yao 1999,, we propose a negative correlation regularisation to diversify the behaviours of sub- nub-policies. The regularisation calculates the 2-Wasserstein distances (Olkin & Pukelsheim 1982 w (s) between each pair of Gaussian decision distributions TT(-ls) and n, (-1)) 2- Wassserstem distance is chosen because it is widely used and differentiable when both distribu- tions are Gaussian. The formula of the distance measure is detailed in Section C.2 Let [-1c denote down-clip function bounding its argument under constant upper bound c, the formulation of the negative correlation regularisation e(-) is
(-T() Σ. Σ, (o),))()))
(1)
where w is clip size parameter. This work arbitrarily sets w 0.6yd where d is the dimensionality
of the action space. We abbreviate (()(--s)) as (s) in the rest this paper. Omitting the clipping function, e (s) is the expected Wasserstein distance of two sub-decision distributions stochastically sampled according to ((s). Two ideas motivate the use of the clipping function: (i) if the distance is
already large, continuously maximising the distance does not benefit a lot for diversity of generated levels but harms the rewards; (ii) few (even two) far- far-away clusters can have large expected distance but such pattern has limited diversity. Taking the down-clip helps with avoiding this case. e" (s) is
4

---

Published as a conference paper at ICLR 2024
maximised only if (s) 2 ت and (((s) By(s) for all pairs of i and j. This regularisation term is integrated into the MDP, thus the objective to be maximised NCERL is defined as
En (r(((,,, A.) + Xe (S.))
J = E,,-
where À is a regularisation coefficient and is the discount rate. The regularisation follows different form compared to the reward r(S,, At), which based on the decision distribution rather than a single action and is independent of the actual action taken by the policy. This raises the question of how to optimise the regularised ohjective ? We adapt the traditional RL theorems, policy iteration (Sutton & Barto 2018) and policy gradiens (Sutton et al. 1999) to answer it.
4 POLICY REGULARISATION THEOREMS
To answer the question above, this section derives regularised policy iteration and policy- regularisation gradient. All lemmas and theorems are proved Appendix A
Value Functions Similar to the standard one (Sutton & Barto
2018),
the state value for policy
regularisation is defined as v (s) = E.y.s [Ei=o T" e* however, is varied from the standard Q-value, defined as
S, a].
The state-action value,
(s, a) = By,. Σ k== e (Se+k) 8, = 8, A:
The counter starts from rather than 0, because e" is independent on the actual action. We further define a regularised state value function (T( = V (s) + (V)(s) and regularised state-action value function 27 (s, (s, a) + XQ a). An optimal policy n² is defined Vss E S, Vi II, e (s) 2 (s), where II is the hypothesis policy space. A IT maximises over II.
4.1 REGULARISED POLICY ITERATION
We now describe the regularised policy iteration for an arbitrary policy regularisation g² Off-policy regularised deep RL algorithms can be established by approximating this theoretical algorithm. Con- sidering an RL algorithm in tabular setting, we define a Bellman operator TØ" of Qe-function for all paired a E S x A to derive the Qp of a policy as
(o, a)
(sa) (vee 1Qo(s'
(4)
Having this definition, it is guaranteed that applying the operators over S x A repeatedly will con- verge the true Qu-function of any policy æ,, as formalised below.
Lemma 1 (Qn-Function Evaluation). By repeatedly applying Q²+ = Te Q² from an arbitrury converges to O as k + oc.
Q functiio Qo the sequence 0% , Q.
The complete regularised policy evaluation applies standard policy evaluation and Qe-function eval- uation either jointly (by summing Q" with AQ directly) or separately.
To derive an improved policy any s, S A, we define a greedy regularised policy improvement operator for all e Sae
Tnew from an arbitrary policy Told assuming QT a) is known for
Nnow (-1s) + arg (s))(()))) [Ae" (s) + (awn(11))) [ (s, [)]]
(5)
We say a policy a' better than another म, denoted as n² n, is E S, (s) 2 VT(s) and 3s E S, ya (s) (s). Then a lemma of regularised policy improvement is formalised as follows. Lemma (Regularised Policy Improvement), For any Told E II and its nnew derived via equation 5
it is guaranteed that nnew > wold if Told is not optimal.
The regularised policy iteration algorithm alters between the regularised policy evaluation and the regularised policy improvement repeatedly.
proved that given finite IT, such an algorithm converges to an optimal policy over IT. This convergence guarantee is formulated into Theorem ! Theorem 1 (Regularised Policy Iteration), Given a finite hypothesis policy space II, regularised policy iteration converges optimal policy over II from any no TT.
5

---

Published as a conference paper at ICLR 2024
4.2 POLICY- REALC--REULLARSATIION GRADIENT
We derive the gradient for policy regularisation, namely the pelicy-regularisation gradient (PRG) to provide a theoretical foundation of regularised RL for on-policy algorithms.
An improper discounted state distribution d' is defined as dd ds) - Ei Is Po())Pll + т] du
like in standard policy gradient, where P(s S s denotes the probability density of transiting to s' after l steps from 8, by applying и. Consider policy represented by a parametric model x where 0 is its parameters. Using e (s) as the abbreviation of e(T" (-1=)), PRG is formalised as follows. (Policy-Regulle Regulaatnn Gradient, PRG). The gradient of a policy regularisation objec- 12-07 2000 (Se) w.r.. 0 follows
Theorem 2
live J = EM
2se 00
(Oe(())
-sx (7(6.a) 0= (als) do de andd
(s) 80
OIn (als))
(e)
+ (e,
(6)
00
00
00
5
IMPLEMENTING NCERL WITH ASYNCHRONOUS EVALUATION
5.1 IMPLEMENTING NCERL AGENT
We implement NCERL agents based on the soft-actor critic (SAC) (Haarnoja et al. 2018b). An NCERL agent carries two critics for soft Q-function, two critics for Q -functio and the ensemble policy. All critics use MLPs. With Qg a; Φ1) and Qe a; Φ22) denoting Qe-value predictions at state-action pair of two -r-riitsss, where Φ1 and Φ2 denote their parameters, each critic j E {1, 2} is trained to minimise the Bellman residual of the negative correlation regularisation
Ls Es,a,''DD (Qo(s,
0;) (V((':
where D is the replay memory. vs(s'; σ) is the prediction of V Va-velue with target parameters ø: Vo(+':)) e (s') Σn, 8 (s) min a':)),
(8)
(E(1.2)
where eº (ss') is the negative correlation regularisation (ef. equation I of the ensemble policy model T² at 8', āe is an action sampled from T.( (-|s".. The target parameters are updated with the same smoothing technique as in SAC. The Q-critics are trained with SAC, but when computing the soft
Q-value target, we take expectation over all individual actors as in equation g
The ensemble policy model is updated by approximating the regularised policy improvement oper- ator defined in equation with crities and gradient ascent. The loss function is
m Le EE.. [xe" (s) E,", (.,
(s.
(9)
where the reparametrisation trick is used with (") E.) = u)()) + (s) Ge where E, ~ NO0, I), and the regularised state-action value is predicted by as) + minke(1.2) Q(s, a; th)) + À minyee(1,2) Qe(ss az (b)) The gradient of -Le is also an approximated estimation of PRG (ef. equation 66] and Appendix [B. The agent learns through performing gradient descent using Adam optimiser (Kingma & Ba 2015) periodically to LG and Le. respectively. For exploration, the agent directly samples an action from the ensemble policy model.
5.2 ASYNCHRONOUS OFF-POLICY TRAINING FRAMEWORK
Reward evaluation in OLG typically requires simulations of gameplay on complete levels test their playability or simulate player behaviours (Wang et al. 2022). Such a simulation is usually realised by running game-playing agent to play the level, which is time-consuming. The paral- lel off- policy training framework devised for OLG in previous work is synchronous (Wang et al.) 2022), which causes unnecessary hang-on of CPU processes and GPU. On the other hand, existing asynchronous RL frameworks focus on on-policy algorithms (Mnih et al.) (016) or distributed learn- ers (Gu et al., 2017), which do not apply to this work. Therefore, we design an asynchronous training framework. It separates model training and reward evaluation into two parallel processes, while the reward evaluation uses an asynchronous process pool to compute rewards of complete levels through mulltippoccessigg. This framework is also potentially beneficial to other tasks such neural com- binatorial optimisation where the reward evaluation operates on complete trajectories (Liu et al. 2023). Appendix C.T provides the pseudo-code.

---

Published as a conference paper at ICLR 2024
6 EXPERIMENTAL STUDIES
NCERL is evaluated on the well-known Mario level generation benchmark (Karakovskiy 'To gelius 2012), with two different tasks. This section introduces the experiment settings and discusses experimental results. Appendix D.2 and E.] provide more details and analysis.
6.1 EXPERIMENT SETTING
NCERL instances with different numbers individual actors and regularisation coefficient values are compared to several state-of-the-art policy ensemble algorithms and classic algorithms.
Algorithm instances are tested on two OLG tasks of a well- known benchmark (Hu al. 2023) from recent literature, namely MarioPuzzle (Shu et al. 2021 and MultiFacet (Wang et al. 2022). They are mainly different in terms of the reward functions. MarioPuzzle defines two reward terms, fun and historical deviation. Fun restricts the divergence between new segments and old ones while historical deviation encourages the RL policy to generate novel segments in relation to previously generated ones. MultiFacet defines two reward terms to guide the RL policy to generate segments that introduce new tile patterns and play traces. Both of them use a playability reward, penalising the RL policy for generating unpassable segments. The full reward function in each task is a weighted sum of these reward terms. The two tasks are selected as they are the statc-of-the-ar for online Mario level generation and their source codes are publicly available online. Formulations and more details of the two tasks are presented in Appendix D.1
Online Level Generation Tasks
Compared Algorithms In total, 30 algorithm instances are used to train 5 independent generators each (thus 150 generators in total), which can be categorised into three groups (i) 24 NCERL in- stances are trained with all the combinations of the ensemble size E {2, 3, 4, 5 and regularisation coefficient À {0.0, 0.1, 0.2, 0.3, 0.4, 0.5). (ii) Three state-of- oofthhe-rr art ensemble RL algorithms pub- lished within the past three years, including PMOE (Ren et al. 2021). DvD (Parker-Holder et al.) 2020 and SUNRISE (Lee al.) (02T) reviewed in Section 2 The algorithm proposed in (Yang al. 2022) is excluded as it is designed for discrete action space. All of them are trained in our pro- posed asynchronous framework, using five individual actors following (Parker-Holder et al., 2020) Lee et al. 2021). During the test, one of the sub-policies is randomly selected to make the decision at each step for better diversity. (iii) Three SACs are trained the standard single-process process setting, in the synchronous multi process framework in (Wang et al. (022), and in our proposed asynchronous framework, referred to as SAC, EGSAC and ASAC, respectively.
All algorithm instances trained for million steps. Common hyperparameters shared by all instances are set to the same values. Hyperparameters uniquely belonging to an algorithm are set as reported in its original paper. Appendix D.2 reports all the hyperparameters and their values.
6.2 RESULTS AND DISCUSSION
Performance Criteria All of the trained generators are tested by generating 500 levels of 25 seg- ments each. Cumulative reward and diversity evaluated on the 500 levels generated by the generators compared. The diversity is measured by the expectation of distance between pairs of generated levels, which is extensively used in PCG (Nam et al. 2021 Earle et al., 202T Beukman et al. 2022). Additionally, geometric mean (G-mean) (Derringer, 1994h and average ranking (Avg- (angrrank (Zhang
ct al. 2022) are used to enable unified comparisons. The average ranking criterion estimates the average of reward rank and diversity rank of algorithm instance out of all compared ones. Both unified criteria are suitable for combining multiple metrics in different scales. Appendix formu- lates the criteria and discusses more details.
Effectiveness of NCERL Table reports the performances of the tested algorithm instances. On both tasks, NCERL achieves the highest diversity. terms of the G-mean criterion which unifies reward and diversity, NCERI almost outperforms all the other algorithms with any À except for PMOE. With = 0.3, 0.4 and 0.5, the G-mean score of NCERL is higher than PMOE on both tasks. The superior G-mean scores indicate that NCERL balances reward and diversity better and
We refer algorithm with specific hyperparameters algorithm instance.

---

Published as a conference paper at ICLR 2024
outperforms other compared algorithms in a unified sense. In terms of the other unified criterion, the average ranking, NCERL surpasses all other algorithms except for SUNRISE on the MarioPuzzle task. Compared to SUNRISE, NCERL allows one make trade-off's between reward and diversity by specifying the regularisation coefficient. With À = 0.5, NCERL achieves the best diversity score on both tasks. PMOE shows competitive performance in terms of diversity, which is only lower than the NCERL instance s of À = 0.2 and À = 0.5 on MarioPuzzle and only lower than the NCERL of À 0.5 on MultiFacet, but the reward gained by PMOE is worse than most NCERL instances. The reward gained by NCERL is not superior among all compared ones, but the enhancement to diversity more significant than the sacrifice of reward, according to the results of the G-mean.
Table 1: Average and standardd deviation of each algorithm's performance over 5 independent trials. All ensemble algorithms reported in this table are trained with individual actors.
Non non-ensemble
Ensemble (m
NCERL (m
Task
Criterion
SAC
EGSAC
ASAC
PMOB
DrD
SUNRISE
A=0,0
A=0.1
2=0.2
3=0.3
A=0.1
A=0.5
56.21
54.86
57.22
46.39
58.78
60.43
55.24
51.42
53.78
53.22
54.59
53.26
Reward
1.896
#,966
=1.00
+/1
#1.41
11.08
+2.20
110.9
#3.72
=7.15
#2.68
#3.23
Divensity
760.8
1714
1342
1570
1698
1967
Mario Puzzle
+173
+77.1
+123
+161
=128
+58.4
+3366
=327
+101
=318
+262
#:78
G-mean
186.1
210.5
207.9
279.4
210.6
243.8
269.7
279.1
322.7
296.1
302.8
322.1
126.9
1449
1.41.0
1.16.9
16.89
1:27.7
1.3566
114.5
1.19.3
119.3
Avg-mank
8.32
8.50
6.96
7.14
6.10
4,28
6.16
5.30
4.88
4.98
5.54
5.04
1.808
1.544
=.450
1:723
1.829
1.319
1.564
11.48
11.37
2.778
1:100
1.599
Reward
46.93
44.35
46.83
37.40
45.68
46.53
46.39
46.16
45.35
37.87
40.86
35.77
1.640
-.456
18.59
1.246
1.376
1.356
1:4.21
249.6
451.6
273.0
973.9
394.0
388.6
401.6
492.3
620.2
1024
889.6
1142
Diversity
Multi Facel
+22.7
#62.7
=31.9
+380
=201
1:3.9
+107
169.6
=92.5
=151
+:234
2:224
108.1
141.2
99.56
181.7
129.9
134.1
135.1
150.3
167.1
195.5
187.3
199.0
G-mean
14.94
1.0.3
=7.47
4:226
1.26.1
19.18
118.2
110.4
411.2
4.5.17
1.17.
1.6.94
6. 6.14
7.26
6,88
6.10
5.82
5.76
5.94
5.64
5.60
6.10
5.90
6.06
Avg-rank
L,22
1.656
-752
1.155
1.640
1.516
1,488
398
1.410
1.0632
1.237
1.102
Figure 2 further shows the learning curves of tested algorithms. On both tasks, the re-
MarioPuzzle Divanaty
Corru eins Noward
Oimczn
ward of all algorithms ascends over time steps. Meanwhile, except for NCERL and PMOE, the diversity scores of all other al- gorithms descend over time steps. On the MarioPuzzle task, the G-mean scores of NCERL and PMOE ascend, while on Mul- tiFacet, their G-mean values remain high. The G-mean values of all other algorithms descend on both tasks. As both NCERL and PMOE use multimodal policy, this ob- servation implies that the multimodal pol- icy is key to balancing reward and diver- sity. Overall, NCERL better balances re- ward and diversity.
50 166
6.
34
36
02
Multifacet
Cormuntive Devard
Divenity Scare
Grresn
200
100
T
J6
SUNAISE
DvD
PMOE
SAC
BGSAC
ASAC
0.0.0
1=0.1
2=02
A-0.5
Figure 2: Solid curves correspond to the learning curves of NCERL instances with different values of X. Dashed and dotted curves refer to the ones of com- pared algorithms. Shadow represents standard devia- tions over the five trials.
To analyse the performance of each in- dependent trial, we illustrate the locations of all trained generators in the reward- diversity objective space via scatter plots
(Figure 3) According to Figure 3 the compared algorithms are generally located in regions of low diversity, while NCERLS spread widely and contribute a major portion of the Pareto front. Most of the generators trained by the compared algorithms are dominated by NCERL generators, while the non-dominated ones are generally biased towards the reward. The observations further indicate that NCERL is able to train generators with varied trade-offs between reward and diversity, making it possible to cater to varied preferences.
The locations of NCERL generators trained under the same hyperparameters sometimes vary lot, revealing that NCERL can be instable over trials. Table T and Figure 2 also show the standard deviation of NCERL's performance is generally big. Meanwhile, PMOE also suffers from instability
8

---

Published as a conference paper at ICLR 2024
across trials, especially the MultiFacer task. As both PMOE and NCERL use multimodal policy, future work may investigate techniques to mitigate the instability of training multimodal policy. On the other hand, it is expected to integrate NCERL with multi-objective RL (Hayes al. 2022). to train a set of non-dominated generators in which the instability may not be a disadvantage.
MarioPuzzle
MultiFacet
1400
2000
1200
1000
Broarhyy
1500
800
1000
600
0.0
ASAC
0.0
1g
SAC
EGSAC
A-0.2
SAC
0-2
100m
500
SUNRISE
0.3
SUNRUSE
A 0-0.3
200
PHOE
0.5
PMDE
2-0.5
20
25
30
35
40
45
50
lask Reward
45
47
Figure 3: All trained generators' locations the reward-diversity objective space are visualised in these scatter plots. Coloured markers correspond to generators trained with NCERL, where shapes represent the ensemble size m (round: m 2. triangle: m 3, diamond: m 4, pentagon: 5). Grey curves indicate the Pareto front across all trained generators.
Verification of the Asynchronous Framework To verify our proposed asynchronous framework, SAC, EGSAC and ASAC are compared. According to Table [] the EGSAC, which trains SAC in synchronous framework (Wang et. 2022), gets lower rewards and higher diversity scores. ASAC's performance is very similar to SAC, especially in terms the cumulative reward. Therefore, is more reliable plug base algorithms into our proposed asynchronous framework. Meanwhile, our asynchronous framework is faster than the synchronous framework of EGSAC. We train generators with ASAC, EGSAC and standard SAC for one million time steps each computation platform with 64 CPU cores and GTX 2080 GPU to compare their time efficiency. Using 20 processes for evaluation, ASAC costs 4.93h while EGSAC costs 6.06h, i.e., ASAC 22.9% faster than EGSAC. The standard single-process SAC costs 34.26h, i.e., ASAC speeds up SAC by 596%.
Influence of Hypareparamters According to Table 1 and Figure 3 as X increases, the diversity score generally increases while the reward generally decreases. The influence of varying the ensem- ble size m does not show clear regularities. We investigate and discuss the influence of ensemble size and regularisation coefficient more comprehensively in Appendix
7 CONCLUSION
In this paper, we propose novel negatively correlated ensemble RL approach, enable online diverse game level generation. The NCERL approach uses a Wasserstein distance-based regulari- sation diversify the behaviour of a multimodal ensemble policy. Furthermore, an asynchronous off-policy training framework is designed to train online level generators faster. To show how the regularisation can be optimised in MDP, we derive the regularised RL. theorems, which facilitate NCERL. NCERL is shown to be able to generate diverse game levels with competitive performance on the reward. It achieves superior G-mean scores, which indicates that NCERL better balances the reward and diversity. The proposed method and theorems make it possible to further develop multi- objective RL algorithms that consider the diversity of generated levels as an objective, which can train set of non-dominated generators in single trial to cater to varied preferences. Because the levels generated by NCERL are diverse, it is likely to enable fresh and interesting gameplay experiences even after numerous levels have been generated and played.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported by the National Key R&D Program of China (Grant No. 2023YFE01063000 the National Natural Science Foundation of China (Grant No. 02250710682) the Shenzhen Science and Technology Program (Grant No. 20220815188 1188111710)0)) the Research In- stitute of Trustworthy Autonomous Systems, and the Guangdong Provincial Key Laboratory (Grant No. 2020B 10200121
REFERENCES
Alberto Alvarez, Steve Dahlskog, Jose Font, and Julian Togelius. Empowering quality diversity in Dungeon design with interactive constrained MAP-Elites. In 2019 IEEE Conference on Games, pp. 1-8. IEEE, 2019.
Alba Amato. Procedural content generation the game industry. Game Dynamics: Best Prac- fices in Procedural and Dynamic Game Content Generation, pp. 15-25. Springer International Publishing. 2017.
Michael Beukman, Christopher W Cleghorn, and Steven James. Procedural content generation using neuroevolution and novelty search for diverse video game levels. In Genetic and Evolutionary Computation Conference, pp. 1028-1037. ACM, 2022.
Rujikorn Charakorn, Poramate Manoonpong, and Nat Dilokthanakul. Generating diverse coopera- tive agents by learning incompatiibl policies. In International Conference on Learning Represen- tations, 2023.
Richard Cheng, Abhinav Verma, Gabor Orosz, Swarat Chaudhuri, Yisong Yue, and Joel Burdick. Control regularization for reduced variance reinforcement learning. International Conference Machine Learning, pp. 1141-1150. PMLR, 2019.
Brandon Cui, Andrei Lupu, Samuel Sokota, Hengyuan Hu, David Wu, and Jakob Nicolaus Foer- ster. Adversarial diversity in Hanabi. International Conference on Learning Representations, 2023. URLptttss wwwp://eeeee.e....e....e... formmf d= www..//orruunnaeeaassss3
Rafael Guerra de Pontes, Herman Martins Gomes, and Igor Santa Ritta Seabra. Particle swarm optimization for procedural content generation in an endless platform game. Entertainment Com- puting, 43:100496, 2022.
Thomas Degris, Martha White, and Richard Sutton. Off-policy actor-critic. In International Con- ference Machine Learning, pp. 179-186, 2012.
George C Derringer. A balancing act-optimizing a products properties. Quality Progress, 27(6):
51-58, 1994.
Sam Earle, Maria Edwards, Ahmed Khalifa, Philip Bontrager, and Julian Togelius. Learning con- trollable content generators. In 202/ IEEE Conference Games, pp. 1 1-9. IEEE, 2021.
Jesse Farebrother, Marlos C Machado, and Michael Bowling. Generalization and regularization in DQN. arXiv preprint orXiv:/810.000
2018
Matthew C Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K Hoover, and Stefanos Nikolaidis. Illminating Mario scenes in the latent space of generative adversarial network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 5922- 5930, 2021.
Alexandre Galashov, Siddhant Jayakumar, Leonard Hasenclever, Dhruva Tirumala, Jonathan Schwarz, Guillaume Desjardins, Wojciech M Czarnecki, Yee Whye Teh, Razvan Pascanu, and Nicolas Heess. Information asymmetry in KL-rregularized RI. In International Conference on Learning Representations. URL http:ttps:/cee /ttttp:://peeeevveee net/ htt.f/frmmmii//// www.oooomdniiiinioooo.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, volume 27, pp. 1-9. Curran Associates, Inc., 2014.
10

---

Published as a conference paper at ICLR 2024
Jordi Grau-Moya, Felix Leibfried, and Peter Vranex. Soft Q-learning with mutual-information regularization. In International Conference on Learning Representations, 2019. URL https:
joCqFX
Daniele Gravina, Ahmed Khalifa, Antonios Liapis, Julian Togelius, and Georgios N Yannakakis. Procedural content generation through quality diversity. In 2019 IEEE Conference Games, pp- 1-8. IEEE, 2019.
Stefan Greuter, Jeremy Parker, Nigel Stewart, and Geoff Leach. Real-time procedural generation of 'pscudo infinite' cities. In International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia, pp. 87-94, 2003.
Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In International Conference Roboties and Automation, pp. 3389-3396. IEFE, 2017.
Matthew Guzdial, Nicholas Liao, Jonathan Chen, Shao- Yu Chen, Shukan Shah, Vishwa Shah, Joshua Reno, Gillian Smith, and Mark O Riedl. Friend, collaborator, student, manager: How design of an Al-driven game level editor affects creators. In Proceedings of the 2019 CHI Con- ference on Human Factors in Computing Systems, pp. 1-13. ACM, 2019.
Matthew Guzdial, Sam Snodgrass, and Adam Summerville. Procedural Content Generation via Machine Learning: An Overview. Springer, 2022.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- on Machine Learning, pp. 1861-1870. PMLR, 2018a.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Schoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint arXiv: arXiv:/8/2.05905. 2018b.
Conor F Hayes, Roxana Rădulescu, Eugenio Bargiacchi, Johan Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstraeten, Luisa M Zintgraf, Richard Dazeley, Fredrik Heintz, et al. A practical guide to multi-objective reinforcement learning and planning. Autonomous Agents and Multi-Agent Systems, 36(1):26, 2022.
Chengpeng Hu, Yunlong Zhao, Ziqi Wang, Haocheng Du, and Jialin Liu. Game- based platforms for artificial intelligence research. arXiv preprint arXiv:2304. 122000.132665 13269, 2023.
Tobias Huber, Silvan Mertes, Stanislava Rangelova, Simon Flutura, and Elisabeth André. Dynamic difficulty adjustment in virtual reality exergames through experience-dree drivvnn procedural content generation. In Symposium Series on Computational Intelligence, pp. 1-8. IEEE, 2021.
Martin Jennings- Teats, Gillian Smith, and Noah WardrippFrrin Polymorph: A model for dynamic level generation. In Proceedings of the AAAI Conference Artificial Intelligence and Interactive Digital Entertainment, volume 6, pp. 138-143. AAAI, 2010.
Zehua Jiang, Sam Earle, Michael Green, and Julian Togelius. Learning controllable 3D level gener- ators. In Proceedings of the 17th International Conference on the Foundations of Digital Games, pp. 1-9. ACM, 2022.
Sergey Karakovskiy and Julian Togelius. The Mario Al benchmark and competitions. IEEE Trans- actions on Computational Intelligence and Al in Games, 4(1):55-67, 2012.
Ahmed Khalifa, Philip Bontrager, Sam Earle, and Julian Togelius. PCGRL: Procedural content generation via reinforcement learning. In Proceedings the AAAI Conference on Artificial Intel- ligence and Interactive Digital Entertainment, volume 16, pp. 95-101, AAAI, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. id= (0=88mmw
net forum?
11

---

Published as a conference paper at ICLR 2024
George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. In Advances in Neural Information Processing Systems, volume 22, pp. 1-9, 2009.
Raph Koster. Theory fun for game design. O'Reilly Media, Inc., 2013.
Kimin Lee, Michael Laskin, Aravind Srinivas, and Pieter Abbeel. SUNRISE: A simple unified framework for ensemble learning in deep reinforcement learning. In International Conference on Machine Learning. pp. 6131-6144 PMLR, 2021.
Antonios Liapis, Georgios N Yannakakis, and Julian Togelius. Enhancements constrained novelty search: Two-population novelty search for generating game content. In Conference on Genetic and Evolutionary Computation, pp. 343-350. ACM, 2013.
Jialin Liu, Sam Snodgrass, Ahmed Khalifa, Sebastian Risi, Georgios N Yannakakis, and Julian Togelius. Deep learning for procedural content generation. Neural Computing and Applications, (3(1):19337,20) 2021.
Shengcai Liu, Yu Zhang, Ke Tang, and Xin Yao. How good is neural combinatorial optimization? systematic evaluation on the traveling salesman problem. IEEE Computational Intelligence Magazine, 18(3):14-25 2023.
Yong Liu and Xin Yao. Ensemble learning via negative correlation. Neural Networks, 12(10):
1399-1404, 1999.
Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot coordination. In International Conference on Machine Learning, pp. 7204-7213. PMLR, 2021.
Athar Waamouudi-Nejanl Matthew Guzdial, and Pierre Boulanger. Arachnophobia exposure therapy using experience-driven procedural content generation via reinforcement learning (EDPCGRL). In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Enter- tainment, volume 17, pp. 164-171. AAAI, 2021.
Volodymyr Mnih Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning, pp. 1928-199 1937. PMLR, 2016.
Sang-Gyu Nam, Chu-Hsuan Hsueh, and Kokolo Ikeda. Generation of game stages with quality and diversity by reinforcement learning in turn-based RPG. IEEE Transactions on Games, 14(3): 488-501, 2021.
Ingram Olkin and Friedrich Pukelsheim. dispersion matrices. Linear Algebra and its Applications, 48:257-263, 1982.
The distance between two random vectors with given
Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effec- tive diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 18050-18062. MIT Press, 2020.
Shubham Pateria, Budhitama Subagdja, Ah-hwee Tan, and Chai Quek. Hierarchical reinforcement learning: A comprehensive survey, ACM Computing Surveys, 54(5):1335, 2021.
Mike Preuss, Antonios Liapis, and Julian Togelius. Searching for good and diverse game levels. In Conference on Computational Intelligence and Games, pp. 1-8. IEEE, 2014.
Jie Ren, Yewen Li, Zihan Ding, Wei Pan, and Hao Dong. Probabilistic mixture-of-expprts for efficient deep reinforcement learning. arXiv preprint arXiv: 104.0922 2021.
Sebastian Risi and Julian Togelius. Increasing generality in machine learning through procedural content generation. Nature Machine Intelligence, ((8):428-336 2020.
Rohan Saphal, Balaraman Ravindran, Dhcevatsa Mudigere, Sasikant Avancha, and Bharat Kaul. SEERL: Sample efficient ensemble reinforcement learning. In International Conference on Au- tonomous Agents and Multi Agent Systems, pp. 100-1108, 2021.
12

---

Published as a conference paper at ICLR 2024
Noor Shaker, Georgios N Yannakakis, Julian Togelius, Miguel Nicolau, and Michael O'neill. Evolv- ing personalized content for Super Mario Bros using grammatical evolution. In Proceedings of the AAAI Conference Artificial Intelligence and Interactive Digital Entertainment, volume 8, pp. 75-80. AAAI, 2012.
Hassam Sheikh, Mariano Phielipp, and Ladislau Boloni. Maximizing ensemble diversity in deep reinforcement learning. In International Conference on Learning Representations, 2022. URL net/ wtt..e/efoooounoo--tt-----------
Tianye Shu, Jialin Liu, and Georgios N Yannakakis. Experience-driven PCG via reinforcement learning: A Super Mario Bros study. In 2021 IEEE Conference Games, pp. 1-9. IEEE, 2021.
David Silver, Guy I Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. International Conference on Machine Learning, pp- 387-395. PMLR, 2014.
David Stammer, Tobias Günther, and Mike Preuss. Player-adaptive Spelunky level generation. In Conference on Computational Intelligence and Games, pp. 130-137. IEEE, 2015.
Evan Kusuma Susanto and Handayani Tjandrasa. Applying hindsight experience replay to proce- dural level generation. In Indonesia Conference on Computer and Information Technology, pp- 427-432 2021.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12. pp. 1-7. MIT Press, 1999.
Bryon Tjanaka, Matthew C Fontaine, Julian Togelius, and Stefanos Nikolaidis. Approximating gra- dients for differentiable quality diversity in reinforcement learning. In Genetic and Evolutionary Computation Conference, pp. 1102-1111. ACM, 2022.
Julian Togelius, Georgios N Yannakakis, Kenneth O Stanley, and Cameron Browne. Search-basee procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and Al in Games, 3(3):172-186, 2011.
Vanessa Volz, Jacob Schrum, Jialin Liu, Simon M Lucas, Adam Smith, and Sebastian Risi. Evolving Mario levels the latent space of a deep convolutional generative adversarial network. In Genetic and Evolutionary Computation Conference, pp. 221-228. ACM, 2018.
Ziqi Wang and Jialin Liu. Online game level generation from music. In 2022 IEEE Conference Games, pp. 119-126. IEEE, 2022.
Ziqi Wang, Jialin Liu, and Georgios Yannakakis. The fun facets of Mario: Multifaceted experience-driven PCG via reinforcement learning. In Proceedings of the 17th International Conference on the Foundations of Digital Games, pp. 1-8. ACM, 2022.
Ziqi Wang, Tianye Shu, and Jialin Liu. State space closure: Revisiting endless online level gen- eration via reinforcement learning. IEEE Transactions on Games, Early Access, 2023. doi: 10.1109/TG.22233322222
Zhengyu Yang, Kan Ren, Xufang Luo, Minghuan Liu, Weiqing Liu, Jiang Bian, Weinan Zhang, and Dongsheng Li. Towards applicable reinforcement learning: Improving the generalization and sample efficiency with policy ensemble. International Joint Conference on Artificial Intelli- gence, pp. 3659-3665 IJCAI Organization, 2022.
Georgios N Yannakakis and Julian Togelius. Experience-drive procedural content generation. IEEE Transactions on Affective Computing, 2(3):147-161, 2011.
Georgios N. Yannakakis and Julian Togelius. Artificial Intelligence and Games. Springer, 2018.
Qingquan Zhang, Jialin Liu, Zeqi Zhang, Junyi Wen, Bifei Mao, and Xin Yao. Mitigating unfairness via evolutionary multi-objective ensemble learning. IEEE Transactions on Evolutionary Compu- fation, (7(4))888886) 2022.
13

---

Published as a conference paper at ICLR 2024
Shangtong Zhang and Hengshuai Yao. ACE: An actor ensemble algorithm for continuous control with tree search. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5789--9776.. AAAI, 2019.
A PROOFS
The proofs of Lemma
Lemma
2 Theorem D and Theorem 2 are provided in this section.
A.1 BEHAVIOUR REGULARISED POLICY ITERATION
Our proof of regularised policy iteration follows the similar line of soft policy iteration (Haarnoja et al. 8018a) but considers general decision distribution regularisation setting rather than the spe- cific maximising entropy setting.
Lemma I (Qg -Function Evaluation). By repeatedly applying Qh+1 To Q from an arbitrary Qe functio Qa the sequence oo. ... Qb converges to Q7 as k: + oc.
Proof. As the policy π to be evaluated is fixed at this stage, we can treat (1)) (s')] as reward function f(s, a), and then treat Q7 a) Q-function since
(s, EM,T
* (S St = A, =a
-EM
7Mt (Sc+*++))) S = =, 8, A. =
k=0
-,M.
7/th Reth
S: = A, =
k=u
where the last expression is the same as the definition of standard Q-function. Then we can simply borrow the theoretical results of standard policy evaluation (Sutton & Barto 2018
Lemma (Regularised Policy Improvement). For any Told and Tnew derived via equation 5
it is guaranteed that Tnew > Vold if Told is not optimal.
Recap of equation
vs E S, Tnew (-1s) = arg max a(-))))l1(-1+)
(te + Ea-x(19) [Q (s, a)]
5
Proof. By taking the operator described in equation it is definite that Vs S, Am + Ep- [2 QF a)] 2 (M) + En ())
Q Toa (s, a)] (s). With (s, =
r(s, a) + Es (s.) 1>V* (s))), we have:
you < Tar( (s) + E Earttm (-1a)
(s,
Ne (s) + E En ( (-1s)
((s, a) -E [TDm)
B (-10) Toom (8)
r(,, a)] + M. (S ) St = []
Earster (18)) Ta (s) + rs,, a)] + -EE, (S )+ + EarnE F (1S111) [QTHe (S S. =
Σ' km 2 * (S Rethl S = 3 (St22) Se = s]
EMM Exe (t + Retke) Vivee (s). (s))
14

---

Published as a conference paper at ICLR 2024
Hence, Vs S, Vi Vinw (s) Nnew Told- If it the former case, then V E S we have:
V (8) max Axe + Ba (11)) (s. (s.
max Ae= (s) s) + -a (r(s,a) a) + y:Bs' (1,0) D (s')l]
sEll
E,M, [ee" (St) R2 Viorr (S 1) =
En (S+4k) + Rosss) S₁ =
max
EM,=
xEll
indicates that both new and Fold are optimal. Therefore, Nnew > Told if Wold is not optimal.
Theorem 1 (Regularised Policy Iteration). Given a finite stochustic policy space II, regularised policy iteration converges to an optimal policy over II from any To E II.
Proof. Collecting Lemma and Lemma 2 with the theoretical result of standard Q-value evaluation
Sutton et al. 1999) and the condition that is finite, evidently the policy converges to optimal. L
A.2 STOCHASTIC POLICY GRADIENT FOR BEHAVIOUR REGULARISATION
Our proof for Theorem draws lessons from the proof of stochastic policy gradient (Sutton al., 1999) for basic ideas, and deterministic policy gradient (Silver et al. (014) for dealing with con- tinuous space. We alter the superscript between т and 7 and sometimes drop the 0 term in the formulation of policy, such denotation rule aims at emphasising whether the term requires gradient w.r.t. not, but all the terms are induced by the parametric model . (-I-).
We assume that the state space and action space are continuous, and the discounted regularisation objective considered. Furthermore, we assume the involved functions are continuous over the space and have real number supremum whenever we exchange the orders of derivations and inte- grals.
Theorem 2 Aoglicy-Regularisatiinn Gradient, PRG). The grudient of a policy regularisation objective J E., EE=
x(e((Se) w.rl. 0 follows
9
JJ
(0)
+ / (5(s,a)
(als)
0
(s((s)
da
ds
00
00
00
(3ee(s)
(als)
(s,
Srit" a~1)(11s)
00
00
Proof. According the definition of the value functions of regularisation, we have
Vi (s) = =s)() Ra) (1) [)) (s) / (sals) da
and
(8, hV2 / (p) ds'
15

---

Published as a conference paper at ICLR 2024
Then derive the bootstrap equation of (s)
00 as follows:
(s)
0
/ x
e (s())
(als)
+
00
00
0el
(10 (2 + *(ass)
(alss)))
(0g(s.a)
da
00
00
00
0ul (6)
/A (als)
(s) da + / x(als)
00 / rpl 1p ds' da
00
00
(s)
(als)
17 (s. do [ (3/// T(als)p(s')s (s,a) (s))s) da
(v
+
00 ds
00
A
00
00
On
O (0 d / yP(s + s' (5)
+
00 ds'.
00
00
(10)
Note / P(ss S u,
[ Plu + s', (s'(s') ds' du P(s " s (s' ds' is held for any
Js
as the Markov property is satisfied by any MDP. So we can unroll the result of equation I0 as follows:
(s)
20
(s'
(als')
PPPls 48,4]
Og a) da do',
(1I)
00
00
00
t=
(0)
where the item of t = 0 an improper integral that represents
O (s, a) da.
00
00
As S
EMA
En re [Se((S))
Po(s) (s) ds, together with equation
11 we have
0. 0
(v
po(s)V?(s) ds po(s)
ds
00
00 Is
00
= (o(s) (18 rPlss s m|
(00
(als')
(5(5',a)
da
ds' ds
00
00
/
Po(s) s. 00'(5")
SA (alss)
(5 a) da ds ds'
00
Σ / ('Po(s)P(s Ss/ w/ ds
(00((0)
+ /A
On (5's da ds
08
00
= 1 (3) (00(5))
+ + 1
θ (als')
da
ds'.
00
00
(12)
For the / 03(5',a)
(als)s
da term, we can apply the log-derivative trick as follows:
00
(5
On (als')
da =
/ ())(aa)
3 da T(a|s')08 Ol 1 (als') da
00
/ <lals))
(13)
ae Iln T (als') 00
(00(s',))
Concluding equation 12 and equation 13
get equation 6
16

---

Published as a conference paper at ICLR 2024
B EXPLAINING ENTROPY REGULARISED RL WITH GENERAL POLICY REGULARISATION THEOREMS
The soft policy iteration Haarnoja et al. 2018b) improves a policy Wold by
exp Q7 (s, -/))))))))))))))))) ZTt
nnw (-|s) arg min DKL TT-ss) #Ell
This is specific case of equation entropy, since
with e=(ss) H(T(-11)) and A = a, where H denotes the
exp (xp (s, (8, 1/2)
arg min DKL. #Ell
(111))
7mau(s) T T(als)7zuul
/ a(aas) log
arg min mell
da
exp( Tio (s, a)/2)
x ((als) log exp(2x (s, a)/)) da + / I(als) z (s) da
arg min well
log da
M(T((-s)) 1 1 (fals) (s) da
arg min
arg max (s) 11 wEll
At the same time, the gradient of actor loss of SAC, can be viewed weighted summation of standard SPG and PRG in terms entropy. The actor loss of SAC (Haarnoja et al., (018b) is written
Jo (eND,aNt"(1e) (og((" (x(x,))).
We borrow idea from (Degris et al. 2012). consider a behavioural policy so that 8 dT = D. then we have
Jo = B amm
(115) Ja log((" (-1s) - @x(s,a)
H²)ss) / N (als)((((() (Q*(s, da
Bannto
OJe 00
On (als)
(s)
/A (al()))))
Exndd
00 Qs, a) da
+ AB
Qx(s, da
00
Standard SPG
PRG for entropy
Similarly, by s d= = =s~ D, we can explain NCERL as optimising a weighted summation of behavioural SPG and behavioural PRG.
C ADDITIONAL DETAILS
C.I ASYNCHRONOUS OFF-POLICY TRAINING FRAMEWORK
We employ an evaluation pool to enable asynchronous evaluation. The pool contains capacited queue and multiple processes. Once task is submitted, the pool assigns the task free process available, otherwise, the task will stored in the queue temporarily. If the queue is full, the pool will be blocked until any process is finished. Algorithm describes asynchronous framework.
17

---

Published as a conference paper at ICLR 2024
Algorithm 1 Main Procedure of the Asynchronous Off-Policy Training
Framework.
Require: Number of evaluation workers horizon of MDP h, update
interval itv
1: Create multi multi-processing evaluation pool with workers
2: credits 6-0
3: repeat
4: Sample a no-reward trajectory z via the agent
5: Submit 7 to the evaluation pool
6: T < collect evaluated trajectories from the pool
7: Update with T
8: credits <- credits
Itv
9: for u + min credits], [1.25=11] do
< sample a batch from D
11:
Update agent with B
12: credits + credits
13:
end for
14: until run out of interaction budget
15: Waiting for all remaining tasks finished
16: T + collect all trajectories from the pool
Update D with 7
do 19: B + sample a batch from D
for u + credits + ity
20: Update agent with via the base algorithm
21: end for
The coefficient 1.25 in line of Algorithm i arbitrarily set. We just arbitrarily assign a number slightly higher than aiming submit the simulation tasks uniformly, which reduces the suspends of simulation workers. The coefficient should be larger than 1 so that the credits can be used up.
C.2 2- WASSERSTEIN DISTANCE
The 2- Wassersstein distance for pair of probability distributions X and Y is defined
w(X,Y) Y) = inf E(awy~ [||= v1l2]
ZEZ(X,Y)
where Z is a joint distribution of X and Y and Z is the set of all joint distribution of X and Y. In case both and are Gaussian, the 2-Wasserstein distance can be expressed as follows.
w² (N1, ||m -
3 Trace E1 [E++ Σg 2(z
where N2, are the two Gaussian distribution to be compared, 141 and μl are the means of N1, and E Σ2 are the covariance matrices of A2, respectively.
D ADDITIONAL EXPERIMENT DETAILS
D.1 ONLINE LEVEL GENERATION TASKS
In our tasks, the state space is a dn-dimensional continuous vector space, where d is the dimension- ality of the latent vector of the action decoder and the number of recently generated segments considered in the reward function. A state is concatenated vector of fixed number of latent vec- tors of recently generated segments. If there are not enough segments have been generated (< n) construct state, zeros will be padded in the vacant entries. The action space is d-dimensional continuous vector space. An action is a latent vector which can be decoded into a level segment by the decoder. The decoder is trained GAN in this work.
The reward functions the two tasks considered in this paper consist several reward terms. Those reward terms are described and formulated follows.
18

---

Published as a conference paper at ICLR 2024
The work of (Shu al.) 2021) and (Wang al. 2022) different formulation of playability. We use the one of (Wang et al. 2022) as is the most recent one. Formally, the playability reward is
Playability
0, if 8t- @ xe playable, P(x1) - (-,
otherwise,
where ① represents appending level segment with another. The playability is judged by the strongest game-playing agent the Aario-Al-Framework benchmark (Karakovskiy & 'Toellius 2012).
The fun reward (Shu al. 2021 uses four configuration parameters lb, ub, ó and Further- more, a metric TPKL(; is used to measure the dissimilarity of levels. Formally, the fun reward
Fun
(D(x))-1 1b) if D(x,) < lb, (D(x)) - -D(a)))ub)² ub)? if D(x,) > ub,
F(a))
otherwise,
where
D(a)) = Σ SW, 16),
where SW(x,, (æ,, id) represents the level segment extracted by sliding window from 2; backward with a stride of ió tiles.
Historical Deviation Historical deviation (Shu et al 2021 uses two configuration parameters m and n with > Formally, the historical deviation reward is
H(ra) = min Σ (P,,( x'EX
s.t. X C {xr-m:" I1-1 |X| =
Level Novelty Level novelty (Wang et al. 2022) uses two configuration parameters g and Fur- thermore, a metric TPJS(;,)) is used to measure the dissimilarity of levels. Formally, the level novelty reward function is
I(xx)) E AC(TPJS(# 2t (1
E
in which r; n+1
and
lu
AC(ugg,r) min {r,
Gameplay Novelty Gameplay novelty (Wang al., 2022) shares the form with the level novelty but replaces the TPJS metric with another metric Da(:,)) -) evaluating the distance between the simulated gameplay trace of two levels or level segments. Let gp(x) be simulated gameplay of arbitrary level segment r, formulation of gameplay novelty is
G(x,) ACDDalppll))
Σm Ti
All the configuration parameters are set as suggested in the corresponding papers and are sum- marised in Table
The two tasks use weighted sums of their proposed reward terms as the final reward function. The observation space varies over different tasks since different reward functions depend different numbers of latest level segments. Table summarises the information six tasks tested this paper.
19

---

Published as a conference paper at ICLR 2024
Table 2: Configuration parameters of the reward functions.
Indicator
F
Parameter
1b
ub
g
Value
0.26
0.94
21
10
5
0.3
5
0.14
5
Table 3: Summary of the OLG tasks.
Task
Reward Function
Obsevation Space
MarioPuzzle
R₂ = 3H()))) +
10d = 200
MultiFacet
R. I(x,) G(z) P(m))
5d 100
D.2 HYPERPARAMETERS
The hyperparameters are listed in Table
Using discounted rate at 0.9 which is not close is counter-intuitive as it induce large bias to the optimal policy in the average reward criterion being considered in OLG. However, we consider the OLG tasks satisfying a perfectible property. In this case, using any y > does bias the optimal policy, so we can use a relatively small which reduces the variance of gradient estimation. The next subsection details the assumed property.
D.3 PERFECTIBLE PROPERTY AND SETTING DISCOUNT FACTOR
Two criteria are typically considered in RL, namely the average reward criterion JA (A(T) lim E,, A 2 Rg and the discounted reward criterion Jp(T) = EM, 12t= PRe), where 7 E [0, is the discount factor. In principle, the average reward criterion should consid- ered in OLG. However, found that in some OLG tasks, relatively small (e.g., 0.9) ensures superior average reward despite that it may make Jn badly approximate JA-
To explain the aforementioned phenomenon, assume that the MDP of some OLG tasks permits perfect policy after investigating the formulations of reward function OLG (see Appendix [D.]] for the reward functions). A perfect policy always gains the maximum reward. An MDP is said to be perfectible if it permits perfect policy. Let S* be the set of all the states that possibly appear at any time step given a policy æ. and r* be the maximum value of reward r(s, a) over S A, the assumption is formalised as follows.
Assumption (Perfectible MDP). For the MDP of OLG tasks considered this work, there exists a perfect policy x² that satisfies Vs S= PP(((s = " ~ T (-1s)]
Under Assumption D we have the following proposition. Proposition For a perfectible MDP, any optimal policy terms of JA and any optimal policy in terms of JD (with 0 < T 1) are all perfect policies.
The proof of Proposition T straightforward. If an optimal policy x is not perfect, then there must be Es E Sx" V" (s) V (s), terms of both JA and Jp criteria. This in contrast to that n' is optimal. Therefore, we can use a that is not close to 1 to optimise JA without bias of optimal policy perfectible MDP. Intuitively, smaller y can reduce the variance, while larger 7 is likely to induce fewer local optima. One may need to set 7 carefully to enable superior average return in perfectible MDP.
D.4 PERFORMANCE CRITERIA
Let 500 and h 25 be the number of levels generated by each generator for the test and the number of segments in each level (h = 25 is used because this slightly longer than the longest level in the training level set of the GAN.), the performance criteria are described below.
20

---

Published as a conference paper at ICLR 2024
Table 4: Hyperparameter settings.
Hyperparameter
Value
Optimiser (all networks and a)) Learning rate (all networks and Hidden layer activation (all networks)
Adam Kingma & Ba 2015
3.0 10
ReLU
Number of hidden layers (all networks)
2
Size of hidden layer(all networks)
256
Batch size
256
Replay buffer size
10
Target smoothing coefficient
0.02
Target entropy
dim((A) 20
Discount factor
0.9
Number of evaluation workers
Size of waiting queue
Update interval (see Algorithm)
2
Cumulative Reward Cumulative reward for generator is calculated R Ei= Rg for each level, i.e., each MDP trajectory, then averaged over the 500 levels.
Diversity Score
Diversity score of a generator calculated
D 2
A 2zy)
n(n
Sight
where (..-)) indicates the Hamming distance, i.e., how many different tiles are there between the two levels be compared; and Ty indicate the h one and the j"h one in the levels.
Geometric Mean G-Mean for generator is calculated as = VRD. is suitable to combine and D even though they are in different scales. Because given any scaling coefficients sæ > 0 and 8D rescale the cumulative reward and diversity score, the ratio between any two generators' G-mean values is constant since
GK C²
VanRisDDr
D G1 VR G2'
VanRisDD,
where the subscripts and 2 indicate the two generators being compared in terms G-mean.
Average Ranking For the average ranking, we first rank the 60 generators (K = 12 algorithm instances being compared T independent trials) in terms of reward and diversity, respectively, from the highest to the lowest. With kR and &D denoting the ranks of generator in terms of reward and diversity out of the KT generators, respectively, the average ranking of this generator is calculated A = ] kp)/T.
E ADDITIONAL EXPERIMENT RESULTS
E.1 INFLUENCE OF HYPAREPARAMTERS
We add tables 5 and 6 to show the performance of each independent NCERL generator to better analyse the training results, especially the effect of varying hyperparameters.
21

---

Published as a conference paper at ICLR 2024
Table 5: Reward and diversity of all NCERI. generators trained MarioPuzzle. Trials 1-5 indicate the five independent training trials. In each row, the five trials are sorted according to the reward of trained generators.
Trial
Trial
Trial
Trial 4
Trial 5
A
Reward
Diversity
Reward
Diversity
Reward
Diversity
Reward
Diversity
Reward
Diversity
0.0
59.21
769.8
58.28
743.1
56.26
1141
56.24
1206
51.54
1775
0.1
57.71
1213
56,79
1221
53,68
1481
50.24
1626
45.81
2144
0.2
55.11
1762
53.99
1588
52.53
1664
45.92
2017
27.21
1660
2
0.3
59.07
950.8
54.85
1580
52.62
2171
52.21
1366
27.31
1706
0.4
55.64
1450
54,96
1614
53.53
1676
50.94
1668
50,16
1980
0.5
54.25
1943
52.75
1952
52.39
1784
48.47
2344
27.68
1654
0.0
61.76
811.5
60.62
818.7
55.52
1184
54.31
1304
52.72
1479
0.1
58.15
1272
55.76
1380
54.70
1703
53.65
1513
47.91
1779
0.2
58.96
1242
56.82
1522
56,06
1412
55.19
1406
53.88
1792
3
0.3
56.79
1867
55.43
1548
53.31
1729
47.19
2026
32.10
1772
0.4
60.13
1288
55.85
1471
55.22
1681
54.37
1644
47.33
2025
0.5
55.63
1523
55.02
53.90
51.56
42.95
0.0
62.85
680.0
61.23
802.3
59.71
803.7
58.11
898.9
53.11
1642
58.53
1528
56.83
55.53
55.22
0.2
58.35
1270
56.73
1743
54.35
1675
53.61
1876
25.11
1562
0.3
58.67
1295
56,02
1769
55.99
1551
55.16
1931
49.61
2074
0.4
1400
1664
56.77
$6.36
45.09
0.5
57.76
1650
55.01
1739
53.62
2058
$3.36
1920
53.05
2022
0.0
57.46
976.5
$7.00
1240
$5.80
1063
54.66
1593
51.29
1839
0.1
59.49
1133
58.69
1232
55.97
1794
52.74
1966
30.23
1723
0.2
57.15
1925
55.89
2057
54,80
1764
54.47
2015
46.59
1940
0.3
58.41
1351
58.20
1313
55.62
1702
54.66
1974
39.23
2098
0.4
58.73
1212
56.20
1808
54,50
51.88
1946
51.63
0.5
57.89
1434
53.99
2167
53.86
1954
52.76
2178
47.82
2102
According to the table, the generators with larger m seem to perform more stable since there are more bad generators found in the group of m 2. By increasing X, the diversity is generally improved while reward is generally decreased. However, the change in performance is not monotonic. The reason may be summed up that the regularisation is not identical to the diversity score and it also promotes the exploration, making the effeet of À not fully predictable. Reward and diversity are generally conflicted, but there examples that generator performs better than another in terms of both reward and diversity, i.e., dominate another. For example, Trial of m = 2. 0.5. Some bad generators fail to gain good rewards while their diversity scores are not superior either (e.g.. Trial 5 m = 2, 0.2, Trial of m 2, 0.3, Trial 5 of m 3, 0.3). That means NCERL is not totally stable. Probably the regularisation objective sometimes leads to some local optima during training.
2, A 0.5 dominates Trial of
22

---

Published as a conference paper at ICLR 2024
Table 6: Reward and diversity of all NCERL generators trained MultiFacet. Trials 1-5 indicate the five independent training trials. In each row, the five trials are sorted according to the reward of trained generators.
Trial
Trial
Trial
Trial 4
Trial 5 Diversity
A
Reward
Diversity
Reward
Diversity
Reward
Diversity
Reward
Diversity
Reward
0.0
47.16
242.7
47.15
248.4
46.84
280.2
46.74
263.7
46.69
370.6
0.1
46.12
487.5
37.65
1031
35.11
1084
33,91
1147
28.23
1452
0.2
46.46
424.5
45.24
681.1
42.77
761.4
35.16
1120
28.16
1417
2
0.3
45.34
684.4
44.81
755.3
42.10
818.4
30.82
1296
29.48
1382
0.4
45.80
735.1
40,48
978.3
40.07
1043
32.23
1282
31,56
1329
0.5
38.65
1063
38.21
978.7
34.16
1172
29.73
1371
28.90
1396
0.0
47.42
201.7
46.88
246.8
45.67
543.9
44.85
666.7
35.79
1099
0.1
46.38
444.2
45.81
600.9
45.55
677.9
44.27
732.3
43.73
848.1
0.2
46.19
523.9
46.07
583.5
44.13
623.7
40.91
945.7
39.97
971.0
3
0.3
45.81
461.3
44.84
684.1
43.93
787.5
38.88
1035
29.41
1382
0.4
46.37
445.5
45.88
430.1
43.07
844.6
42.74
839.7
42.32
937.3
0.5
46.31
417.3
46.01
761.3
45.43
575.6
39.49
37.77
0.0
47.11
245.2
46.16
461.7
45.82
48
45.44
505.2
44,60
613.4
558.2
589.8
45.97
45.95
45.85
0.2
46.14
609.7
45.87
543.8
45.76
610.0
40.87
926.5
38.46
1016
0.3
45.92
606.7
45,48
591.1
41.40
822.7
40.73
998.0
38.67
1016
0.4
46.70
420.5
648.3
44.05
739.1
43.85
41.18
927.7
0.5
43.42
789.2
43.03
900.4
32.09
1237
31.15
1290
29.84
1364
0.0
47.08
248.3
46.43
314.3
46.33
420.9
46.08
531.3
46.02
493.4
0.1
46.70
384.7
46.40
506.1
46.07
444.1
45.88
561.8
45.72
565.0
0.2
46.24
529.9 9
46.01
501 .4
45.95
627.5
45.38
716.5
43.18
725.8
0.3
41.38
849.7
41.04
905.6
39.68
960.1
34.38
1180
32.87
1226
0.4
46.37
480.5
42.66
817.9
42.31
948.8
39.20
33.77
0.5
43.18
802.0
39.15
1018
36.94
1154
32.39
1276
27.21
1460
The observation of this table is similar to the Table 5 the generators with larger m seem to perform more stable while À is positively correlated to diversity but negatively correlated to reward. The diversity of those generators generally smaller than the ones trained on MarioPuzzle, That means the reward function of MultiFacet may not allow super highly-diverse generators.
23

---

Published as a conference paper at ICLR 2024
E.2 INDIVIDUAL ACTOR SELECTION PROBABILITY
To see whether each of the sub-policy is used, we report the selection probability of each sub-policy for NCERL generators trained with 0.5 and À 0.1, in Tables 7 aaddd g
Table 7: Selection probability each step in stochastic generation trials with the initial
state. An NCERL generator trained with À = 0.5 and m 5 on MarioPuzzle is picked to showcase. Levels generated in these two trials are presented in Figure Bold text indicates the sub-policy of the corresponding row is selected at the corresponding time step. The probabilities smaller than 0.001 are notated as
0.5
[-1
2
t--
9
10
- 12
13
.062
.081
.388
.091
.117
.117
.144
.171
.137
.179
.181
.208
.206
.009
.357
.209
Run
-259
2116
225
233
-447
2222
255
-256
211
.191
2000
2208
195
1995
.001
259
-25
196
237
219
2005
2033
.201
.29
.211
.188
.196
.178
.197
0
.202
195
.216
184
.193
.194
.192
.212
.172
.201
.211
.212
.216
.208
-332
.149
.198
.203
.357
-233
Run 2
.239
1152
2114
.218
-241
.225
1222
1195
.2122
2218
1200
.2118
.218
.198
84
.101
285
2776
.210
.212
.209
.208
.204
.227
2009
.191
.199
.216
.278
.198
2216
.178
-202
-193
-196
-2033
1150
-213
-211
-158
-210
(a) Run
(b) Run
Figure 4: Generated levels of the two generation trials illustrated in Table 7
Table 7 shows that the selection probability of the generator trained with À 0.5 is adjusted adap- tively during the generation process, and all the sub-policies are used within the two generation trials.
24

---

Published as a conference paper at ICLR 2024
Table 8: Selection probability each step in stochastic generation trials with the initial state. An NCERL generator trained with À = 0.1 and m 5 on MarioPuzzle is picked to showcase. Levels generated in these two trials are presented in Figure Bold text indicates the sub-policy of the corresponding row is selected at the corresponding time step. The probabilities smaller than 0.001 are notated as
0.1
[-1
10
[
-
12
13
8:
1.00
.822
.531
5001
.809
522
483
.539
.900
.513
.610
.711
.661
.687
-522
Run
00
.003
.016
.005
.003
.055
.618
.400
.499
.391
.478
.517
.461
.437
.477
.370
.284
.336
.313
.420
0
0
F2
R2
R2 0
R3 0
R2
82
F2
.003
88 0
F:
.015
1.00
.435
.502
.502
.150
.430
.534
.502
.470
.453
.350
.506
.174
4000
Run
0
2:
R8 0
F:
9:
.46
0
001
4226
.565
.171
-198
498
.550
.570
.666
/998
.530
.468
.650
.479
.326
.516
As
1=0
0
89 0
9:
.021
0
.002
.016
(a) Run
(b) Run
Figure 5: Generated levels of the two generation trials illustrated in Table
Table 8 shows that some of the selection probability is near zero. Sub-policies 2 and are never used within the two trials. This because is small.
25

---

Published as a conference paper at ICLR 2024
E.3 GENERATED SAMPLES
The following pages show partial examples generated by several trained NCERL generators, with comparison the examples generated by standard SAC. Performance in terms of reward and diver- sity is reported. Our anonymous code repository includes generated examples of all the generators trained in this work.
hnttps://annnymoous sci otspaa/eeee///eeeiooeeeeeeeoee-/ 4F25/
26

---

Published as a conference paper at ICLR 2024
(a) Example levels generated by NCERL generator trained with X 0.5, m on the MultiFacet task.
The reward and diversity scores of this generator 36.9 and 1154, respectively.
(b) Example levels generated by SAC generator trained on the MultiFacct task. The reward and diversity scores of this generator are 46.7 and 256.1, respectively.
Figure 6: Example levels generated by an NCERL generator trained on MultiFacet with À = 0.5, m 5 and a SAC generator. SAC generated similar levels while NCERL generated diverse levels.
27

---

Published as a conference paper at ICLR 2024
(a) Example levels generated by an NCERL generator trained with À = 0.3, m on the MultiFacet task. The reward and diversity scores of this generator are 39.7 and 160.1, respectively.
(b) Example levels generated by a SAC generator trained on the MultiFacet task. The reward and diversity scores of this generator are 16.7 and 256.1, respectively.
Figure 7: Example levels generated by NCERL generator trained MultiFacet with À 0.3, m = 5 and SAC generator.
28

---

Published as a conference paper at ICLR 2024
(a) Example levels generated by an NCERL generator trained with X 0.1, m the MultiFacet task.
The reward and diversity scores of this generator are 45.9 and 561.8, respectively.
(b) Example levels generated by SAC generator trained on the MultiFacet task. The reward and diversity scores of this generator are 46.7 and 256.1, respectively.
Figure 8: Example levels generated by an NCERL generator trained on MultiFacet with À 0.1, 5 and SAC generator.
29

---

Published as a conference paper at ICLR 2024
Metl
(a) Example levels generated by an NCERL generator trained with À = 0.5, m = 5 on the MarioPuzzle task.
The reward and diversity scores of this generator are 17.8 8 and 2102, respectively.
(b) Example levels generated by SAC generator trained on the MarioPuzzle task. The reward and diversity scores of this generator are 57.4 and 656.8, respectively.
Figure 9: Example levels generated by NCERL generator trained on MarioPuzzle with À
0.5, m = 5 and a SAC generator. SAC generated similar levels while NCERI. generated diverse levels.
30

---

Published as a conference paper at ICLR 2024
(a) Example levels generated by NCERL generator trained with À 0.3, 5 the MarioPuzzle task.
The reward diversity scores of this generator are 54.7 and 1974, respectively.
(b) Example levels generated by a SAC generator trained on the MarioPuzzle task. The reward diversity scores of this generator are 57.4 and 656.8, respectively.
Figure 10: Example levels generated by an NCERL generator trained on MarioPuzzle with 0.3, 5 and SAC generator.
31

---

Published as a conference paper at ICLR 2024
(a) Example levels generated by NCERL generator trained with À 0.1, 5 the MarioPuzzle task.
The reward diversity scores of this generator are 58.7 and 1232, respectively.
(b) Example levels generated by a SAC generator trained on the MarioPuzzle task. The reward diversity scores of this generator are 57.4 and 656.8, respectively.
Figure 11: Example levels generated by an NCERL generator trained on MarioPuzzle with 0.1, 5 and SAC generator.
32


Reviews:
[{"review_id": "rjDWhsidFM", "reviewer": "Reviewer_NGar", "summary": "This paper introduces a method for online generating diverse game levels through an ensemble of negatively correlated RL generators. The authors derived a policy update operator under the diversity bonus. Apart from that, the authors propose an async framework for speeding up the training. Experiments show that the method is able to generate a wide range of policies through tunning the diversity coefficient $\\lambda$.", "questions": "It is similar to (adversarial) diversity in populations of policies that learn incompatible policies or impose distance(entropy) regularization. Can the authors provide their view of how it compares to population-based methods with diversity regularization?\n\n[1] Xing, D., Liu, Q., Zheng, Q., Pan, G., & Zhou, Z. H. (2021). Learning with Generated Teammates to Achieve Type-Free Ad-Hoc Teamwork. In IJCAI (pp. 472-478).\n\n[2] Lupu, A., Cui, B., Hu, H. &amp; Foerster, J.. (2021). Trajectory Diversity for Zero-Shot Coordination. <i>Proceedings of the 38th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 139:7204-7213 Available from https://proceedings.mlr.press/v139/lupu21a.html.\n\n[3] Cui, B., Lupu, A., Sokota, S., Hu, H., Wu, D. J., & Foerster, J. N. (2022, September). Adversarial Diversity in Hanabi. In The Eleventh International Conference on Learning Representations.\n\n[4] Rahman, A., Fosong, E., Carlucho, I., & Albrecht, S. V. (2023). Generating Teammates for Training Robust Ad Hoc Teamwork Agents via Best-Response Diversity. Transactions on Machine Learning Research.\n\n[5] Charakorn, R., Manoonpong, P., & Dilokthanakul, N. (2022, September). Generating Diverse Cooperative Agents by Learning Incompatible Policies. In The Eleventh International Conference on Learning Representations.\n\n[6] Rahman, A., Cui, J., & Stone, P. (2023). Minimum Coverage Sets for Training Robust Ad Hoc Teamwork Agents. arXiv preprint arXiv:2308.09595.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is written in clarity. Hypotheses are well supported by the experiments.\n2. Originality looks good to me (or maybe I am not following the OLG line of research, but I study MARL diversity, in which no noticeable significantly similar methods to my knowledge)", "weaknesses": "To my understanding, this method adds a reward bonus/diversity constraint to the diversity among the policies, where the proof is kind of established in the literature. The effect of adding diversity regularization is similar to the quality diversity methods, where you are pursuing optimal in the new reward space. The role of $\\lambda$ is close to the Lagrange multiplier in the dual formulation of the original problem with a diversity constraint. I think it is ok to include them as contributions to the paper but building theoretical analysis on the interactions among ensemble policies or regularization effect would be more interesting. My ratings are subject to change.", "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": "", "extra_scores": {}}, {"review_id": "ZhWv4N9YLa", "reviewer": "Reviewer_qX6Q", "summary": "**Problem Setting**\n\nWe want to do level generation but we want to induce some diversity in how the levels are generated. Here the policies define level generators which build the level through an MDP.\n\n**Algorithm / NN Structure**\n\nThe policies are defined as mixtures of Gaussians, implemented by creating a set of sub-policies along with a weighting. The weighting itself id modelled by a selector policy, creating a form of hierarchy.\n\nThe sub-policies are regularized to be diverse from each other using a Wasserstein distance. This distance is clipped, encouraging policies to be diverse only if their decisions are too close. Sub-policies have Gaussian action heads. Regularization is implemented as an auxilliary reward.\n\nA regularized version of policy iteration of the policy gradient are presented. Thus the agent is trained not only to optimize for diversity in the current timestep, but in future timesteps via a reguarlized value function.\n\nThe practical implementation is built off SAC.\n\nExperiments are presented on the Mario level generation benchmark. Results show that NCERL is able to achieve comparable reward to other methods, and outperform in terms of diversity.", "questions": "See above for questions related to the experimental section.\n\nThe section on asynchronous evaluation seems orthogonal to the main contribution of the work. Asynchronous RL has been explored in the actor-critic setting (e.g. A3C), which this work uses as it builds off SAC. Is there a specific connection between the asynchronous implementation and the novel contribution here?\n\nWhat does the behavior of the weighting-selector policy look like? It would provide more clarity into the method to showcase how often this selector policy utilizes specific sub-policies, or if certain sub-policies go unused.\n\nIt may help to label the other comparison methods in Figure 4.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper proposes a clean and thorough study of a method to induce diverse level generation. The idea is to define policies as a mixture of sub-policies, then regularize those sub-policies so that diversity is increased. While this is a straightforward idea, it is especially applicable in a domain such as level generation where diversity is desired in itself rather than as simply a means towards exploration. The quality of the writing and presentation is solid and clear. Theoretical results are presented re-deriving the policy iteration and policy gradient update explicitly in terms of regularizing the diversity between sub-policies, and proofs are presented regarding convergence. The significance of this work stems from its thorough theoretical contributions.", "weaknesses": "Because the experiments are largely domain-specific and improve on diversity rather than pure performance, the significance of this work is limited. \n\nWhile there are novel derivations and a clean interpretation of regularizing the policy gradient, the idea of representing an agent as sub-policies has been explored in fields such as skill discovery and hierarchical reinforcement learning, which were not referenced in this work. \n\nThe description of the domain is unclear to me as a reader, e.g. what is the action space of an agent generating Mario levels? What are the criteria used to evaluate reward and diversity? I would have liked to see examples of the generated levels.", "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": "", "extra_scores": {}}, {"review_id": "9h3SCvHZeX", "reviewer": "Reviewer_t3p4", "summary": "The paper proposes an ensemble reinforcement learning approach for generating diverse game levels. The approach uses multiple sub-policies to generate different alternative level segments, and stochastically selects one of them following a selector model. The paper also integrates a novel policy regularisation technique, which is a negative correlation regularisation that increases the distances between the decision distributions determined by each pair of actors. The regularisation is optimised using regularised versions of the policy iteration and policy gradient, which provide general methodologies for optimising policy regularisation in a Markov decision process. The paper's contributions are:\n1. The proposed ensemble reinforcement learning approach for generating diverse game levels.\n2. The novel policy regularisation technique that encourages the sub-policies to explore different regions of the state-action space.\n3. The regularised versions of the policy iteration and policy gradient algorithms that provide general methodologies for optimising policy regularisation in a Markov decision process.", "questions": "Q1: can the proposed approach be directly applicable to 3D game levels or other types of game content? or what are the difficulties in this extension, such as complex reward design or high computational burden?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "originality: the paper proposes a novel approach for generating diverse game levels using ensemble reinforcement learning and policy regularisation. The paper develops two theorems to provide general methodologies for optimizing policy regularisation in a Markov decision process. The first theorem is a regularised version of the policy iteration algorithm, which is a classic algorithm for solving MDPs. The second theorem is a regularised version of the policy gradient algorithm, which is another classic algorithm for solving MDPs.\n\nquality: the paper provides a detailed description of the proposed approach and the regularisation technique. The paper also provides theoretical proofs of the regularised versions of the policy iteration and policy gradient algorithms. \n\nclarity: the paper is well-written and easy to follow. The authors provide clear explanations of the proposed approach and the regularisation technique.", "weaknesses": "the proposed approach assumes that the reward function is known and fixed. However, in practice, the reward function may be unknown or may change over time. Therefore, the proposed approach may not be applicable in such scenarios.\n\nthe paper only considers a single game genre (platformer) and a single game engine (Super Mario Bros.). The proposed approach may not be directly applicable to other game genres or engines.", "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": "", "extra_scores": {}}, {"review_id": "dAz7rrHpgb", "reviewer": "Reviewer_cq3K", "summary": "This paper proposes NCERL, an ensemble Reinforcement Learning (RL) method for game level generation with more diversity. NCERL uses a set of different Gaussian actors which outputs actions in the latent space, and the output is decoded into different level segments by a GAN decoder. The final output segment is chosen with the probability generated by a learned selector. To encourage diversity between different actors, a regularizer of Wasserstein distance between policy distributions (and weighted by selector) is added to the reward. The paper also gives a modified gradient and convergence proof on the new reward, as the regularizer depends on the whole policy instead of a single action. On a well known level-generation benchmark, NCERL achieves comparable reward (measuring game-design goals) with better level diversity, and can also perform a well trade-off between diversity and reward by controlling its regularization coefficient.", "questions": "I have two questions:\n\n1. In Table 1, the trade-off of NCERL between reward and diversity in some of the environments does not follow the trend; for example, in Mario Puzzle, the diversity with $\\lambda$ seems to have two peaks (0.2 and 0.5), and the reward at $\\lambda=0.1$ is the worst despite of low diversity. Could the author explain this?\n\n2. Currently, there is only comparison between NCERL, ensemble RL methods and non-ensemble RL methods, and the encoding is over GAN. What is the performance of non-RL solutions, such as scripted (possibly with learnable parameters) solution, or supervised/self-supervised learning over more recent generative models such as diffusion models or VAEs?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. As this paper uses a latent space for policy and existing decoder for segment generation, the problem addressed by this paper is not only interesting, but actually quite general: how to achieve a trade-off between policy diversity and performance, with game level generation being one of its real-world applications.\n\n2. The paper has a sound theoretical basis, with a convergence proof for the new reward (which, similar to soft actor-critic, depends on policy distribution instead of action) and a rigorous, modified version of gradient update.\n\n3. The proposed work is scalable, with a well-designed and parallelized reward evaluation framework.", "weaknesses": "**Some details of the papers are not presented clearly enough.**\n\n1. Figure 1 has many math symbols and no caption on high-level ideas of each component; in addition, the meaning of $i\\leftarrow 2$ in the figure is unclear.\n\n2. There is no clear definition on what a state is in the paper; the readers can only speculate that it is a latent vector from the end of Section 2.1 (\"... a randomly sampled latent vector is used as the initial state\").\n\n3. There is no description on how Wasserstein distance is calculated. It is true that 2-Wasserstein distance between Gaussian distributions can be easily calculated, but it would be better if the Gaussian property can be emphasized at the beginning of Section 3.2, a formula can be given to make the paper self-contained, and \"2-Wasserstein\" instead of \"Wasserstein\" is specified.\n\n4. typos: in conclusion, bettwe -> better.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)