Mimicking Evolution with Reinforcement Learning

Abstract:
In nature, there are two processes driving the development of the brain: evolution 1 and learning. Evolution acts slowly, across generations, and amongst other things, 2 it defines what agents learn by changing their internal reward function. Learning 3 acts fast, within one’s lifetime, and it quickly updates agents’ policies to maximise 4 the evolved reward function. Although previous work has emulated both of these 5 processes working in tandem, the optimisation of the reward function in order to 6 serve the aims of the evolutionary process is very computationally expensive. This 7 work proposes a fixed reward function, the evolutionary reward, that aims to max8 imise the number of current (and future) genetically similar agents. Furthermore, 9 we propose a way to approximate the joint action value by averaging the action 10 values of other agents weighted by their genetic similarity. In a finite environment 11 with limited resources this techniques drives improved survival mechanisms and 12 reproductive success. Given that this reward function is fixed, we avoid the com13 putationally intense process of optimising it. We demonstrate the viability of our 14 evolutionary reward by testing it in two bio-inspired, open-ended environments and 15 monitoring a number of metrics such as population size and life expectancy. We 16 compare our technique with the state-of-the-art evolutionary algorithm: CMA-ES, 17 and show the superiority of work at producing agents that maximise the number of 18 its genes across time. 19

In nature, there are two processes driving the development of the brain: evolution1 and learning. Evolution acts slowly, across generations, and amongst other things,2 it defines what agents learn by changing their internal reward function. Learning3 acts fast, within one’s lifetime, and it quickly updates agents’ policies to maximise4 the evolved reward function. Although previous work has emulated both of these5 processes working in tandem, the optimisation of the reward function in order to6 serve the aims of the evolutionary process is very computationally expensive. This7 work proposes a fixed reward function, the evolutionary reward, that aims to max-8 imise the number of current (and future) genetically similar agents. Furthermore,9 we propose a way to approximate the joint action value by averaging the action10 values of other agents weighted by their genetic similarity. In a finite environment11 with limited resources this techniques drives improved survival mechanisms and12 reproductive success. Given that this reward function is fixed, we avoid the com-13 putationally intense process of optimising it. We demonstrate the viability of our14 evolutionary reward by testing it in two bio-inspired, open-ended environments and15 monitoring a number of metrics such as population size and life expectancy. We16 compare our technique with the state-of-the-art evolutionary algorithm: CMA-ES,17 and show the superiority of work at producing agents that maximise the number of18 its genes across time.19
1 Introduction20
Evolution is the only process we know of today that has given rise to general intelligence (as demon-21 strated in animals, and specifically in humans). This fact has been inspiring artificial intelligence (AI)22 researchers to run evolution in artificial worlds that mimic key properties of life on Earth. One of23 these key properties is open-endedness. This means that, as in nature, the fitness function (or any24 goal function) of the environment is not defined anywhere but it simply emerges from the survival25 and reproduction of genes. For this reason, we call these environments open-ended evolutionary26 environments (OEEE). They are never-ending environments where adaptable agents are competing27 for a common limited-resource to survive and replicate their genes. Using them for research is the28 focus of the field of artificial life (ALife).29
Our ability to run evolution efficiently in OEEE will dictate the success of ALife. In this work30 we speed up the way evolution is ran in OEEE by introducing Evolution via Evolutionary Reward31 (EvER). In EvER, each agent is born with an evolutionary reward that, when maximised by a learning,32 it also maximises the survival and reproduction of the agent’s genes. Due to this property we say that33 this reward is aligned with evolution. This allows learning to search for policies with increasingly34 evolutionary fitness. Also, by guarantying this alignment we don’t need to go through the expensive35 process of aligning the agents’ reward functions through evolution. This reward function was designed36 to work on any OEEE.37
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
In the remaining part of this introduction we 1) describe how evolution changes what we learn;38 2) introduce our contribution and describe how maximising a reward function can lead to the39 maximisation of evolutionary fitness.40
1.1 Evolving what to learn41
In nature, there are two different mechanisms driving the development of the brain. Evolution acts42 slowly, across generations, and amongst other things, it defines what agents learn by changing their43 internal reward function. Learning acts fast, within one’s lifetime, and it quickly updates agents’44 policies to maximise pleasure and minimise pain. Combining these two methods has a long history45 in AI research [1, 42, 8]. This combination (illustrated in Appendix B, Figure 3) results in a very46 computationally expensive algorithm as it requires two loops 1) learning (the inner loop) where47 agents maximise their innate reward functions across their lifetimes and 2) evolution (the outer loop)48 where natural selection and mutation defines the reward functions for the next generation (amongst49 other things, such as NN topologies and initial weights).50
We say that a reward function is aligned with evolution when the maximisation of the reward leads51 to the maximisation of the agent’s fitness. Through evolution the most aligned reward functions52 get selected and increase their numbers. Intuitively, one can define the optimally aligned reward53 function as the reward function that allows a learner to learn most quickly how to maximise its fitness,54 assuming the conditions of the world (including other agents) remain the same. However, as agents55 evolve and learn, they change their environment and its corresponding fitness function. This change,56 increases the misalignment between the reward and fitness functions. Therefore, the optimally aligned57 reward function is always chasing the ever changing fitness function (see Appendix C for a formal58 description of this). However, in this paper, we show that in simulation it is possible to define a fixed59 reward function which is always aligned, although not guaranteed to be optimally aligned, with the60 essence of fitness: the ability of the individual to survive and reproduce its genes.61
Our work allows learning to single-handedly drive the search for policies with increasingly evolution-62 ary fitness by ensuring the alignment of the reward function with the fitness function. This greatly63 simplifies the two-loop algorithm used to combine evolution and learning that was described earlier in64 this section. We can do this because our reward is extrinsic to the agent and therefore, only possible65 within a simulation.66
1.2 Learning to maximise evolutionary fitness67
The distinction between an agent and a gene is key to understanding this paper. Formally, evolution is68 a change in gene frequencies in a population (of agents) over time. The gene is the unit of evolution,69 and an agent carries one or more genes. Richard Dawkins has famously described our bodies as70 throwaway survival machines built for replicating immortal genes [6]. His line illustrates well the71 gene-centered view of evolution [43, 6], a view that has been able to explain multiple phenomena72 such as intragenomic conflict and altruism that are difficult to explain with organism-centered or73 group-centered viewpoints [2, 10, 7]. From the gene’s perspective, the evolutionary process is a74 constant competition for resources. However, from the agent’s perspective, the evolutionary process75 is a mix between a cooperative exercise with agents that carry some of its genes (its family) and76 a competition with unrelated agents. Evolution pressures agents to engage in various degrees of77 collaboration depending on the degree of kinship between them and the agents they interact with (i.e.78 depending on the amount of overlap between the genes they carry). This pressure for cooperation79 amongst relatives was named kin selection [34].80
Evolution acts on the gene level, but RL acts on the agent level. RL can be aligned with the81 evolutionary process by noting what evolution does to the agents through its selection of genes:82 evolution generates agents with increasing capabilities to maximise the survival and reproduction83 success of the genes they carry.84
2 Related work85
Combining evolution and learning Combining evolution and learning has long history in AI86 research. The evolutionary reinforcement learning algorithm, introduced in 1991 [1], makes the87 evolutionary process determine the initial weights of two neural networks: an action and an evaluation88
network. During an agent’s lifetime, learning adapts the action network guided by the output of89 its innate and fixed (during its lifetime) evaluation network. NEAT+Q [42] uses an evolutionary90 algorithm, NEAT [36], to evolve topologies of NN and their initial weights so that they can better91 learn using RL. In NEAT-Q the reward function remains fixed. However, evolutionary algorithms92 have also been used to evolve potential-based shaping rewards and meta-parameters for RL [8].93
Competing in Arms-race Every time adaptable entities compete against each other an arms-race94 is created. Each entity’s task gets harder every time their competitors learn something useful. This95 arms race drives the continued emergence of ever new innovative and sophisticated capabilities96 necessary to out-compete adversaries. Evolutionary Algorithms (EA) have been successfully used97 to co-evolve multiple competing entities [32, 29]. However, in sequential decision problems EA98 algorithms discard most of the information by not looking at the whole state-action trajectories99 the agents encounter throughout their lifetime. This theoretical disadvantage limits their potential100 efficiency to tackle sequential problems when compared with RL. Empirically, EA algorithms101 usually have a higher variance when compared with gradient methods [30, 23, 24]. With regards102 to gradient methods (deep learning methods in particular), impressive results have been recently103 achieved by training NN, through back-propagation, to compete against each other in simulated games104 (OpenFive [4], AlphaZero [31], GAN [11]). More closely aligned with our proposed methodology,105 OpenAI has recently developed Neural MMO [37], a simulated environment that captures some106 important properties of life on Earth. In Neural MMO artificial agents, represented by NN, need to107 forage for food and water to survive in a never-ending simulation. Currently, Neural MMO agents108 can not reproduce and their goal is to maximise their own survival, instead of maximising the survival109 and reproduction success of their genes as it happens in nature. We extend this work by introducing110 genes, the ability for agents to reproduce and we align the agents’ reward with evolution. These111 are key properties of life on Earth that we must have in simulation environments if we hope to have112 them evolve similar solutions to the ones evolved by nature (in other words, these are key properties113 to achieve convergent evolution - see Appendix ?? for more details on why this important for AI114 research).115
Cooperative MARL Cooperative MARL is an active research area within RL that has been116 experiencing fast progress [26, 3, 9]. The setting is usually approached in a binary way [4, 41, 20].117 Agents are grouped into teams and agents within the same team fully cooperate amongst each other118 whilst agents from different teams don’t cooperate at all (cooperation is either one or zero); we define119 this scenario as the binary cooperative setting. The teams may have a fixed number of members or120 change dynamically [19, 27, 40, 5]. The most straightforward solution for this setting would be to121 train independent learners to maximise their team’s reward. However, independent learners would122 face a non-stationary learning problem. The MADDPG [22] algorithm tackles this problem by using123 a multi-agent policy gradient method with a centralised critic and decentralised actors so that training124 takes into account all the states and actions of the entire team but during execution each agent can125 act independently. More relevant to our work, factored value functions[12, 27] such as Transfer126 Planning [40] Value Decomposition Networks (VDN) [38] and Q-Mix [28] use different methods to127 decompose the team’s central action-value function into the decentralised action-value functions. We128 build on top of VDN (which is further explained in the Appendix D) to extend the concept of team to129 the concept of family and introduce continuous degrees of cooperation.130
3 Background131
Reinforcement Learning We recall the single agent fully-observable RL setting [39], where the132 environment is typically formulated as a Markov decision process (MDP). At every time step,133 t = 1, 2, . . . , the agent observes the environment’s state st ∈ S , and uses it to select an action at ∈ A.134 As a consequence, the agent receives a reward rt ∈ R ⊂ R and the environment transitions to the state135 st+1. The tuple (st+1, rt) is sampled from the static probability distribution p : S ×A → P(S ×R)136 whilst the actions at are sampled from the parametric policy function πθ : S → P(A):137
st+1, rt ∼ p(st+1, rt|st, at), at ∼ πθ(at|st) (1)
The goal of the agent is to find the optimal policy parameters θ∗ that maximise the expected return138 R̄ = E[ ∑∞ t=0 γ
trt], where γ is the discount factor. In the more general framework, the state is139 only partially observable, meaning that the agent can not directly observe the state but instead it140
observes ot ∈ O which is typically given by a function of the state. In this situation, the environment141 is modelled by a partial observable Markov decision process (POMDP) and the policy usually142 incorporates past history ht = a0o0r0, . . . , at−1ot−1rt−1.143
Q-Learning and Deep Q-Networks The action-value functionQπ gives the estimated return when144 the agent has the state history ht, executes action at and follows the policy π on the future time145 steps. It can be recursively defined byQπ(ht, at) = Est+1,rt∼p [ rt+γEat+1∼π[Qπ(ht+1, at+1)] ] . Q-146 learning and Deep Q-Networks (DQN) [25] are popular methods for obtaining the optimal action value147 function Q∗. Once we have Q∗, the optimal policy is also available as π∗ = arg maxat Q
∗(ht, at).148 In DQN, the action-value function is approximated by a deep NN with parameters θ. Q∗θ is found by149 minimising the loss function:150
Lt(θ) = Eht,at,rt,ht+1 [(yt −Qπθ (ht, at))2], where yt = rt + γmax a′ Qπθ′(at+1, ht+1), (2)
where π is the -greedy policy which takes action arg maxat Q π(at, ht) with probability 1− , and151 takes a random action with probability . θ′ are the parameters of a target network that are periodically152 copied from θ and kept constant for a number of iterations.153
Multi-Agent Reinforcement Learning In this work, we consider the MARL setting where the154 underlying environment is modelled by a partially observable stochastic game [13]. In this setting,155 the environment is populated by multiple agents which have individual observations and rewards and156 act according to individual policies. Their goal is to maximise their own expected return.157
4 Evolution via Evolutionary Reward158
In this section, we propose a reward function that enables RL algorithms to search for policies with159 increasingly evolutionary success. We call this reward the evolutionary reward because it is always160 aligned with the fitness function. We also propose a specific RL algorithm that is particularly suited161 to maximise the evolutionary reward in open-ended evolutionary environments however other RL162 algorithms could also be used.163
Evolutionary reward The evolutionary reward of an agent is proportional to the number of copies164 its genes have in the world’s population. Maximising this reward leads to the maximisation of the165 survival and reproduction success of the genes an agent carries. We start by defining the kinship166 function between a pair of agents i and j, who carry N genes represented by the integer vectors gi167 and gj (we chose to use g for genome, which in biology is the set of genes an agent carries):168
k : ZN × ZN → [0, 1], k(gi, gj) = 1 N N∑ p=1 δgip,g j p , (3)
where δgip,gjp is the Kronecker delta which is one if g i p = g j p and zero otherwise. When agent i is alive169 at time t+ 1, it receives the reward:170
rit = ∑
j∈At+1
k(gi, gj), (4)
where At+1 is the set of agents alive at the instant t + 1. Note that since agent i is alive at t + 1,171 At+1 includes agent i. T i− 1 is the last time step that agent i is alive and so, at this instant, the agent172 receives its final reward which is proportional to the discounted sum of the number of times its genes173 will be present on other agents after its death:174
riT i−1 = ∞∑ t=T i γt−T i ∑ j∈At k(gi, gj), (5)
with this reward function, the agents are incentivised to maximise the survival and replication success175 of the genes they carry. In the agent-centered view, the agents are incentivised to survive and replicate,176 but also to help their family (kin) survive and replicate; and to make sure that when they die their177 family is in a good position to carry on surviving and replicating. The degree of collaboration with178 other family members depends on the overlap between their genotype as it happens in nature.179
The discount factor, γ, needs to be in the interval [0, 1[ to ensure the final reward remains bounded.180 Due to the exponential discounting we can compute the final reward up to an error of by summing181 over a finite period of time denoted by the effective horizon (he). To see how to compute the he for182 a given environment and see the Appendix G.1. By computing the final reward this way, we can183 now use RL algorithms like Q-learning to train agents with this evolutionary reward. However, in the184 next section we introduce a more practical algorithm that allows us to estimate the final reward more185 efficiently.186
Evolutionary Value-Decomposition Networks We propose Evolutionary Value-Decomposition187 Networks (E-VDN) as an extension of VDN [38] (explained in the Appendix D) from the binary188 cooperative setting with static teams to the continuous cooperative setting with dynamic families.189 E-VDN helps us reduce the variance of the value estimation and allows us to estimate the final190 evolutionary reward without having to simulate the environment forward for he iterations.191
Within a team, each agent fully cooperates with all the other members of the team, and it does not192 cooperate at all with any agent outside of the team. Moreover, if a and b are members of the same193 team and c is a member of a’s team then c and b are also in the same team. Within a family, the194 degrees of cooperation amongst its members depends on their kinship degree (which can be any real195 number from 0 to 1). Also, if a and b are members of the same family and c is part of a’s family, c is196 not necessarily part of b’s family.197
Each agent i sees the members of its family from an unique perspective, based on the kinship degree it198 shares with them. In E-VDN, each agent i has a joint action-value function, Qi. E-VDN assumes Qi199 can be composed by averaging the action-value functions across the members of i’s family weighted200 by their kinship with agent i (this is similar to the VDN’s assumption):201
Qi((h1t , h 2 t , . . . , h |At| t ), (a 1 t , a 2 t , . . . , a |At| t )) ≈
1
nit ∑ j∈At k(gi, gj)Q̃j(hjt , a j t |θ̃j), (6)
where nit is a normalisation coefficient defined as n i t = ∑ j∈At k(g
i, gj), Q̃jt is the output of a NN202 with parameters θ̃j and with the input (h j t , a j t ). Composing Q
i with an average, instead of a sum203 as it happens in VDN, is necessary as E-VDN allows the number of value functions contributing to204 the composition to vary as the family gets bigger or smaller (agents born and die). This averaging205 allows us to incorporate the local observations of each family member and reduce variance in the206 value estimation.207
More importantly, E-VDN allows us to deal with the difficulty of estimating the final reward (5) in a208 particularly convenient way. As is clear from its definition (5), the final reward is the expected sum209 (over time) of kinship that agent i has with other agents j after its death. The key idea is to note that210 this value (riT i−1) can be approximated by the Q-value of other agents j that are close to (have high211 kinship with) agent i:212
r̂iT i−1 =
{ 1 ni Ti ∑ j∈ATi k(gi, gj)Q̃jT i(. . . ) ≈ Q i T i(. . . ) if n i T i > 0
0 if niT i = 0 (7)
The final reward is zero if, and only if, at the time of its death the agent has no surviving family.213
Each Q̃it is trained by back-propagating gradients, g i t, from the Q-learning rule:214
git = ∇θi(yit − 1
nit ∑ j∈At k(gi, gj)Q̃j(hjt , a j t |θ̃j))2 ≈ ∇θi(yit −Qit(. . . |θi))2, (8)
where θi is the concatenation of all the parameters θ̃j , used in each Q̃j , contributing to the estimation215 of Qi; i.e. θi := {θ̃j}j s.t. k(gi,gj)>0. Note that Q̃i are neural networks with parameters θ̃i and Qi is216 simply the average stated in (6).217
The learning targets yit are given by:218
yit =
{ rit + γmaxat+1 Q i t+1(. . . )|θ′i) if t < T i − 1
r̂iT i−1 if t = T i − 1 , (9)
rit is the evolutionary reward (4), r̂ i T i−1 is the estimate of the final evolutionary reward (7) and θ ′ i219 are the parameters of the target network that get periodically copied from θi. We don’t use a replay220
buffer in our training (which is commonly used in DQN) due to the non-stationary of multi-agent221 environments (more about this in the Appendix G.2).222
Since the joint action-value Qi increases monotonically with increasing Q̃i, an agent acting greedily223 with respect to its action-value function will also act greedily in respect to its family action-value224 function: arg maxait Q i t(. . . ) ≈ arg maxait Q̃ i(hit, a i t).225
5 Experimental Setup226
We want to test two hypotheses: 1) E-VDN is particularly well suited to make agents climb the fitness227 landscape in open-ended evolutionary environments; 2) E-VDN is able to increase the evolutionary228 fitness of agents in non-binary cooperative environments. To test the first hypothesis we need to229 compare E-VDN with another popular evolutionary algorithm. To make it easier to implement the230 competing algorithm we are going to use a binary cooperative environment to test the first hypothesis.231 To test the second hypothesis we will use a non-binary cooperative environment. Note, if an agent232 carries more than one gene (like it happens in nature) we have a non-binary environment.233
In this section, we give a quick overview of these two multi-agent environments, as well as details234 of the network architectures and the training regime. For a more complete description of the235 environments, you can refer to the Appendix E. In the binary environment, we compared our236 algorithm with a popular Evolution Strategies algorithm (CMA-ES [14]), and describe the training237 regime used for CMA-ES in the Appendix F.238
The Binary Environment The binary environment is a 2-dimensional grid world, which is ini-239 tialised with five agents carrying five unique genomes (Figure 1). At each time step, each agent may240 move one step and produce an attack to another agent in an adjacent tile. When an agent moves to241 a tile with food it collects all the food available in it. If an agent chooses to produce an attack, it242 decreases its victim’s health by one point, if the victim’s health reaches zero it dies and 50% of its243 collected food is captured by the attacker. The food is used to survive (one unit of food must be244 consumed every time step to remain alive), and to reproduce. When agents are within their fertile245 age and they have stored enough food, they reproduce themselves asexually and give birth to an246 agent carrying an exact copy of their genome. Each genome has only a single gene and there are no247 mutations. These rules make the cooperation between agents binary, agents either fully-cooperate248 (they have the exact same genome) or they don’t cooperate at all (their genome has no overlap).249
The Non-binary Environment The non-binary environment has the same rules as the binary250 environment with the difference that the agents now have 32 genes in their genome and they reproduce251 sexually instead of asexually. When two fertile agents are adjacent, they give birth to an agent who’s252 genome is composed by two halves of the genes of each parent, selected randomly. There are no253 genders, any agent can reproduce with any other agent. These rules give rise to different levels of254 collaboration: from 0 to 1 in steps of 132 .255
Policy Each agent observes a 5x5 square crop of the surrounding state (Figure 1). The agent256 sees six features for every visible tile; i.e. the input is a 5x5x6 tensor. This includes two features257
corresponding to tile properties (food available and whether it is occupied or not) and four features258 corresponding to the occupying agents’ properties (age, food stored, kinship and health). Besides259 these local inputs, each agent also observes its absolute position, family size and the total number260 of agents in the world. We intend to remove these extra inputs in future work as we provide agents261 with memory (we’re currently providing our policy with oit instead of h i t). The NN has ten outputs262 (five movement actions with no attack and five movement actions with an attack). In this work, we263 used two different feed forward architectures: one is simply a fully connected NN with three hidden264 layers and 244, 288 parameters in total, the other architecture is composed by convolutional and265 dense layers and it is much smaller containing only 23, 616 parameters. The smaller NN was used to266 compare our algorithm with an evolutionary algorithm which doesn’t scale well to larger networks.267
Training details In this work, the genome does not directly encode the policy, however, we think268 it would be interesting to do that in future work. In the binary environment, we train five different269 policies (with the same architecture but different weights) simultaneously. At each training episode,270 we sample five policies with replacement and assign each one to one of the five unique genomes.271 We do this, to force each policy to interact with all other policies (including itself), increasing their272 robustness in survival and reproduction. During the test episodes, no sampling occurs, each policy is273 simply assigned to each unique genome. The training episodes had a length between 450 and 550274 (note that the reward is computed as if there was no episode end), and the test episodes had a length275 of 500 steps.276
In the non-binary environment, due to the large number of unique genomes, it is unfeasible to assign277 a unique policy to each unique genome. To keep things simple, we chose to use only one policy in278 this environment. This was not possible to do with CMA-ES, so we did not implement it in this279 environment (more about CMA-ES on Appendix F).280
Traits encoded by the genes In the non-binary environment, we can think of each of the 32 genes281 to change some visual feature (e.g. facial feature) of their agent so that it can be better recognised by282 its family. In the binary environment, besides the gene encoding this visual feature it also encodes283 which policy, chosen from a set of 5 policies, the agent is going to have. Note that the genes encode284 fixed traits (they don’t change during an agent’s lifetime) and their frequency in the population evolve285 through normal evolution (death and birth). With EvER we don’t need evolution to create the reward286 function and continuously align it with the fitness function. The agent’s brain is always trying to learn287 the right things for the survival of its genes, however, the actual genes are evolving at the normal pace288 of evolution.289
To analyse the impact of our reward function, we deliberately chose to minimise entanglement290 between genes and other aspects of the agents. However, EvER can be easily used in environments291 where genes encode more traits like the agent’s abilities, visual features, initial weights and the292 topology of its policy.293
Evaluation Metrics In our simple environments, fitter policies can use the environment resources294 more efficiently and increase their population size to larger numbers. Therefore, to evaluate the295 performance of the algorithms in generating increasingly fitter species we track the average population296 size along training time.297
6 Results298
Training agents with E-VDN generates quite an interesting evolutionary history. Throughout the299 binary environment history, we found four distinct eras where agents engage in significantly distinct300 behaviour patterns (1st row of fig. 2). In the first era (the blue line - which lasts only a few hundred301 iterations), the agents learned how to survive, and through their encounters with the other founding302 agents, they have learnt that it was always (evolutionary) advantageous to attack other agents. In the303 second era (orange line), the agents’ food-gathering skills increased to a point where they started to304 reproduce. In this era, the birth-rate and population numbers increased fast. However, with the extra305 births, intra-family encounters became more frequent, and intra-family violence rose to its all-time306 maximum driving the average life span down. This intra-family violence quickly decreased in the307 third era (green line), as agents started to recognize their kin. Kin detection allowed for selective308 kindness and selective violence, which took the average life span to its all-time maximum. Finally,309
in the fourth era (red line), agents learned how to sacrifice their lives for the future of their family.310 Old infertile agents started allowing the younger generation to eat them without retaliation. Through311 this cannibalism, the families had found a system for wealth inheritance. A smart allocation of the312 family’s food resources in the fitter generation led to an increase in the population size with the cost313 of a shorter life span. This behaviour emerges because the final reward (5) incentivises agents to314 plan for the success of their genes even after their death. This behaviour is further investigated in315 the Appendix H.1. These results show that optimising open-ended evolutionary environments with316 E-VDN does indeed generate increasingly complex behaviours.317
The 2nd row of Figure 2, shows the macro-statistics obtained by training the smaller NN with CMA-318 ES and E-VDN. From the figure, we observe that E-VDN is able to produce a larger population of319 agents with a longer life-span and a higher birth rate. A small population means that many resources320 are left unused by the current population, this creates an opportunity for a new and more efficient321 species to collect the unused resources and multiply its numbers. These opportunities are present in322 the CMA-ES environment, however the algorithm could not find them, which suggests that E-VDN323 is better at finding the way up the fitness landscape than CMA-ES. Video 1, shows that each family324 trained with CMA-ES creates a swarm formation in a line that moves around the world diagonally.325 When there is only one surviving family, this simple strategy allows agents to only step into tiles326 that have reached their maximum food capacity. However, this is far from an evolutionarily stable327 strategy [35] (ESS; i.e. a strategy that is not easily driven to extinction by a competing strategy), as328 we verify when we place the best two families trained with CMA-ES on the same environment as the329 best two E-VDN families and observe the CMA-ES families being consistently driven quickly to330 extinction by their competition (fig. 4.a of Appendix B).331
Our results, in the non-binary environment, show that in a non-binary cooperative setting E-VDN332 also improves the ability of the trained policy to survive and replicate its genes (Figure 4.b,c and d333 of Appendix B). This is a key feature that evolutionary algorithms should have in order to take the334 research in open-ended evolutionary environments further. Note, that the non-binary environment335 is much harder than the binary one. To replicate, agents need to be adjacent to other agents. In the336 beginning, all agents are unrelated making it dangerous to get adjacent to another agent as it often337 leads into attacks, but it is also dangerous to get too far away from them since with a limited vision it338 is hard to find a fertile mate once they lose sight of each other. Video 2 shows a simulation of the339 evolved policy being run on the non-binary environment, it seems that agents found a way to find340 mates by moving to a certain region of the map (the breeding ground) once they are fertile.341
7 Conclusion & Future Work342
This paper has introduced an evolutionary reward function that when maximised also maximises the343 evolutionary fitness of the agent. This allows RL to be used as a tool for research of open-ended344 evolutionary systems. To implement this reward function, we extended the concept of team to the345
concept of family and introduce continuous degrees of cooperation. Future work could explore three346 directions: 1) Explore a different reward function that makes agents maximise the expected geometric347 growth rate of their genes; 2) Research the minimum set of requirements to emerge natural cognitive348 abilities in artificial agents such as identity awareness and recognition, friendship and hierarchical349 status (by following our proposed methodology for progress in AI (Appendix ??)) 3) Extend the use350 of genes to encode more fixed traits in the agent like its initial weights and the topology of its policy.351
Broader Impact352
Simulating the key processes that generated life and intelligence in nature is a promising path to353 further our understanding in this field and unlock ever more intelligent algorithms able to solve useful354 problems for the world. However, embodying AI with the goal to survive and self-reproduce can be355 dangerous, and should never be done outside of a sand-boxed environment.356
References357 [1] David Ackley and Michael Littman. Interactions between learning and evolution. Artificial life358 II, 10:487–509, 1991.359
[2] BURT Austin, Robert Trivers, and Austin Burt. Genes in conflict: the biology of selfish genetic360 elements. Harvard University Press, 2009.361
[3] Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent362 complexity via multi-agent competition. arXiv preprint arXiv:1710.03748, 2017.363
[4] Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemysław Dębiak, Christy364 Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large365 scale deep reinforcement learning. arXiv preprint arXiv:1912.06680, 2019.366
[5] Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. arXiv367 preprint arXiv:1910.00091, 2019.368
[6] Richard Dawkins. The selfish gene. 1976.369
[7] Richard Dawkins. Twelve misunderstandings of kin selection. Zeitschrift für Tierpsychologie,370 51(2):184–200, 1979.371
[8] Stefan Elfwing, Eiji Uchibe, Kenji Doya, and Henrik I Christensen. Co-evolution of shaping372 rewards and meta-parameters in reinforcement learning. Adaptive Behavior, 16(6):400–412,373 2008.374
[9] Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon375 Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on376 Artificial Intelligence, 2018.377
[10] Andy Gardner and Francisco Úbeda. The meaning of intragenomic conflict. Nature ecology &378 evolution, 1(12):1807–1815, 2017.379
[11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil380 Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural381 information processing systems, pages 2672–2680, 2014.382
[12] Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored mdps. In383 Advances in neural information processing systems, pages 1523–1530, 2002.384
[13] Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially385 observable stochastic games. In AAAI, volume 4, pages 709–715, 2004.386
[14] Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos. Reducing the time complexity of387 the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary388 computation, 11(1):1–18, 2003.389
[15] Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. CMA-ES/pycma on Github. Zenodo,390 DOI:10.5281/zenodo.2559634, February 2019. URL https://doi.org/10.5281/zenodo.391 2559634.392
[16] Verena Heidrich-Meisner and Christian Igel. Evolution strategies for direct policy search. In393 International Conference on Parallel Problem Solving from Nature, pages 428–437. Springer,394 2008.395
[17] Verena Heidrich-Meisner and Christian Igel. Variable metric reinforcement learning methods396 applied to the noisy mountain car problem. In European Workshop on Reinforcement Learning,397 pages 136–150. Springer, 2008.398
[18] Verena Heidrich-Meisner and Christian Igel. Hoeffding and bernstein races for selecting policies399 in evolutionary direct policy search. In Proceedings of the 26th Annual International Conference400 on Machine Learning, pages 401–408. ACM, 2009.401
[19] Jelle R Kok, Eter Jan Hoen, Bram Bakker, and Nikos Vlassis. Utile coordination: Learning402 interdependencies among cooperative agents. In EEE Symp. on Computational Intelligence and403 Games, Colchester, Essex, pages 29–36, 2005.404
[20] Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michał Zając, Olivier Bachem, Lasse Espeholt,405 Carlos Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research406 football: A novel reinforcement learning environment. arXiv preprint arXiv:1907.11180, 2019.407
[21] Richard L Lewis, Satinder Singh, and Andrew G Barto. Where do rewards come from? In408 Proceedings of the International Symposium on AI-Inspired Biology, pages 2601–2606, 2010.409
[22] Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. Multi-410 agent actor-critic for mixed cooperative-competitive environments. In Advances in Neural411 Information Processing Systems, pages 6379–6390, 2017.412
[23] Simon M Lucas and Thomas P Runarsson. Temporal difference learning versus co-evolution for413 acquiring othello position evaluation. In 2006 IEEE Symposium on Computational Intelligence414 and Games, pages 52–59. IEEE, 2006.415
[24] Simon M Lucas and Julian Togelius. Point-to-point car racing: an initial study of evolution416 versus temporal difference learning. In 2007 iEEE symposium on computational intelligence417 and games, pages 260–267. IEEE, 2007.418
[25] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G419 Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.420 Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.421
[26] Frans A. Oliehoek and Christopher Amato. A Concise Introduction to Decentralized POMDPs.422 SpringerBriefs in Intelligent Systems. Springer, May 2016. doi: 10.1007/978-3-319-28929-8.423 URL http://www.fransoliehoek.net/docs/OliehoekAmato16book.pdf.424
[27] Frans A Oliehoek, Shimon Whiteson, Matthijs TJ Spaan, et al. Approximate solutions for425 factored dec-pomdps with many agents. In AAMAS, pages 563–570, 2013.426
[28] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob427 Foerster, and Shimon Whiteson. Qmix: monotonic value function factorisation for deep428 multi-agent reinforcement learning. arXiv preprint arXiv:1803.11485, 2018.429
[29] Craig W Reynolds. Competition, coevolution and the game of tag. In Proceedings of the Fourth430 International Workshop on the Synthesis and Simulation of Living Systems, pages 59–69, 1994.431
[30] Thomas Philip Runarsson and Simon M Lucas. Coevolution versus self-play temporal difference432 learning for acquiring position evaluation in small-board go. IEEE Transactions on Evolutionary433 Computation, 9(6):628–640, 2005.434
[31] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur435 Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general436 reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science,437 362(6419):1140–1144, 2018.438
[32] Karl Sims. Evolving 3d morphology and behavior by competition. Artificial life, 1(4):353–372,439 1994.440
[33] Satinder Singh, Richard L Lewis, Andrew G Barto, and Jonathan Sorg. Intrinsically motivated441 reinforcement learning: An evolutionary perspective. IEEE Transactions on Autonomous Mental442 Development, 2(2):70–82, 2010.443
[34] J Maynard Smith. Group selection and kin selection. Nature, 201(4924):1145, 1964.444
[35] J Maynard Smith and George R Price. The logic of animal conflict. Nature, 246(5427):15,445 1973.446
[36] Kenneth O Stanley and Risto Miikkulainen. Evolving neural networks through augmenting447 topologies. Evolutionary computation, 10(2):99–127, 2002.448
[37] Joseph Suarez, Yilun Du, Phillip Isola, and Igor Mordatch. Neural mmo: A massively449 multiagent game environment for training and evaluating intelligent agents. arXiv preprint450 arXiv:1903.00784, 2019.451
[38] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi,452 Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. Value-453 decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05296,454 2017.455
[39] Richard S Sutton, Andrew G Barto, et al. Introduction to reinforcement learning, volume 2.456 MIT press Cambridge, 1998.457
[40] Elise Van der Pol and Frans A Oliehoek. Coordinated deep reinforcement learners for traffic458 light control. Proceedings of Learning, Inference and Control of Multi-Agent Systems (at NIPS459 2016), 2016.460
[41] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun-461 young Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster462 level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350–354, 2019.463
[42] Shimon Whiteson and Peter Stone. Evolutionary function approximation for reinforcement464 learning. Journal of Machine Learning Research, 7(May):877–917, 2006.465
[43] George C Williams. Adaptation and natural selection: a critique of some current evolutionary466 thought, volume 833082108. Princeton science library OCLC, 1966.467
1. For all authors...468 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s469 contributions and scope? [Yes]470 (b) Did you describe the limitations of your work? [Yes]471 (c) Did you discuss any potential negative societal impacts of your work? [Yes]472 (d) Have you read the ethics review guidelines and ensured that your paper conforms to473 them? [Yes]474 2. If you are including theoretical results...475
(a) Did you state the full set of assumptions of all theoretical results? [Yes]476 (b) Did you include complete proofs of all theoretical results? [Yes]477
3. If you ran experiments...478 (a) Did you include the code, data, and instructions needed to reproduce the main experi-479 mental results (either in the supplemental material or as a URL)? [No]480 (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they481 were chosen)? [Yes]482 (c) Did you report error bars (e.g., with respect to the random seed after running experi-483 ments multiple times)? [No]484 (d) Did you include the total amount of compute and the type of resources used (e.g., type485 of GPUs, internal cluster, or cloud provider)? [Yes]486 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...487
(a) If your work uses existing assets, did you cite the creators? [N/A]488 (b) Did you mention the license of the assets? [N/A]489 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]490
491
(d) Did you discuss whether and how consent was obtained from people whose data you’re492 using/curating? [N/A]493
(e) Did you discuss whether the data you are using/curating contains personally identifiable494 information or offensive content? [N/A]495
5. If you used crowdsourcing or conducted research with human subjects...496
(a) Did you include the full text of instructions given to participants and screenshots, if497 applicable? [N/A]498
(b) Did you describe any potential participant risks, with links to Institutional Review499 Board (IRB) approvals, if applicable? [N/A]500
(c) Did you include the estimated hourly wage paid to participants and the total amount501 spent on participant compensation? [N/A]502

Review summaries:
The paper is concerned with optimisation in an open-ended ALife environment. The authors propose to directly maximise the number of current and future genetically similar agents via an adaptation of Value Decomposition Networks, named Evolutionary Value-Decomposition Networks (E-VDN). This is in contrast to applying a bi-level optimization procedure where evolution optimises the genes for population size and the inner learning algorithm adapts the policy for an objective set by the outer loop.

** Score revised after reading through initial author comments **  The papers compares and contrasts evolutionary processes with learning processes and discusses some of the links between the two in reinforcement learning problems. Subsequently, the authors describe some previous work on combining evolution with learning processes and set up a reward function that encourages the maintenance propagation of agents in the kin based on genetic encodings. The authors hypothesize that this reward function is provides a useful learning signal in open-ended environments. According to their review of previous work, this reward function solves the alignment problem between learning and evolution by ensuring that the learning policy learns to take actions that encourage the survival of a set of agents of similar kin. Next, the authors formulate a method to optimize that particular reward function named E-VDN, which is an extension of value decomposition networks with E-VDn taking into account the gene marker make-up of a particular agent. The authors then show experiments in a set of multi-agent reinforcement learning environments and analyze the resulting behavior of their trained agents and compare the results of their methods to agents trained with CMA-ES.

The article proposes an evolutionary simulation where agents use reinforcement learning to optimise fitness (in the sense of natural selection, number of genes in the population). Some of the ideas are interesting, but overall the contribution is limited, the applicability of the results is narrow, and the comparisons against evolutionary algorithms is not particularly fair. Fundamentally, it appears as though the authors have created a simulation where _greenbeard_ genes (see Dawkins 1976) are favoured. Basically, attacking individuals pays off if and only if the cost-benefit ratio exceeds their relatedness. This is Hamilton's rule, and a greenbeard makes it so that the relatedness is observable. This is at least the case of their "binary environment" and there are not enough details in the other environment to discern if this is also the case, but some language seems to suggest it is. This is not a novel insight in evolutionary biology, and seeing it work in reinforcement learning agents is not interesting when it is set as the _explicit reward_. Were this to emerge, then it would be much more interesting, particularly without observed relatedness, but also significantly more challenging.