Population-Based Search and Open-Ended Algorithms

this is huge it's just one hall and most people I guess are still waiting for registration yeah but definitely the size of these things is ginormous so tutorials have just started I'll be go finding a place hi so um I just wanted to give a little update on a tutorial that I liked which was the population-based search and open-ended learning tutorial which happened on Monday here as I was pleasantly surprised by this tutorial because I knew almost nothing about these techniques and they seem really cool seems to be a really cool line of research so started out with what is

population-based search and basically in population-based search you don't want to just reach one solution of a problem but you want to kind of maintain a population of solutions that you develop over time so um natural evolution would be an example of that so this can have many benefits that will kind of that were explored in the tutorial so the kind of culprit of traditional optimization let's say you have a classification problem you just train one classifier on it is what they call deception meaning that okay a better example is an RL problem where you need to reach some goal but since the goal might be very hard to reach your algorithm has basically nothing to go on sis there's no stepping stones so usually people go and construct a reward function in a very clever way but this can be overcome with these techniques as well so just imagine like the hardest video game in the Atari suite this would be something like Montezuma's Revenge where you first need to collect some key and then go to some door and only then you get a score right so this reward function is too ambitious and would lead is a problem they call your deception an observation they make is if you look at nature and natural evolution it is very successful even without a goal so there's no goal in mind to natural evolution except reproduction creates other reproduction but it's not a goal that's simply a kind of underlying mechanic mechanism and if you look at nature all this variety of life was produced without a goal in mind and all this variety of life filling different niches and basically reproducing their own at their own pace and so it's a very interesting observation that the goal of this entire field is kind of to model to go into the this direction of what if we don't really go after only the cost function but what if we so in the most extreme case what if we build a search algorithm that only wants to create novel things so we're kind of novelty is the only goal what happens then and it turns out some interesting things can be achieved with that so they introduced this notion of quality diversity which basically means if you look at let's again take life on earth you want all the achievable behaviors that there are so maybe one achievable behavior is a very fast life form that can hunt other life-forms and another achievable behavior is one that camouflage is very well and so on and you want to kind of find for each of these behaviors you want to find the best possible example so that's the direction that these algorithms go into and an algorithm that

they present it was map elites so n AP elites which goes as follows so let's say you have a bunch of dimensions you care about say how fast the creature is how tall it is how well it is camouflage and so on now you would want to discretize each of those dimensions so this will give you cells basically so each of these discretization will introduce a grid of cells and what you now do is you want to keep the best examples of each cell so if a if you have a creature that's very fast but not very well camouflaged at some cell you look at how well it's doing at the goal that you have in mind and you want to keep the best one of those you have a population and whichever ones are in that cell you keep the best and then you go ahead and do kind of change them you could do this with your evolutionary process like you can mutate them or it could do it could be the gradient kind of gradient descent something so but you mutate them and they will I guess they will probably end up in a different cell so you go look at that cell are these new ones better than the ones that you remembered from that old cell and if so replace them kinda you wanna yeah for each cell keep the best one and then kind of start continue developing from those sort of like Dijkstra's shortest path algorithm and this will so what it will return is like an entire landscape of possible behaviors and for each behavior will give you the best result now it doesn't mean they all do equally some will be better some cells will be not as good in your in with regards to your cost function but it will give you an entire landscape and you can could see then that there are many kind of modes in this landscape as I said some creatures are very fast hunters some camouflage very well so but then they're kind of slower so you be able to see these modes in that so that's I found this pretty interesting and very kind of opens the door to a lot different applications so a principle they employ is what is called goal

switching namely that means if like a line of development can benefit from inventions of another line so let's say the very fast hunters they they're good at that but then maybe they don't reach quite optimal performance but then another line develops somewhere else and these are camouflaged like the camouflaged life-forms develop so they invent kind of camouflage now because these the way this mutation and so on is you can keep the camouflaged ones around and the hunters and now the camouflage can kind of jump over to the hunters it's very difficult to explain like this but they call this goal switching and what it means is that yeah that the hunters can now adopt a little bit of camouflage through let's say mutating one of the camouflaged ones into the hunters or vice versa and then can kind of benefit from that invention over there so a good example of that they mentioned is that in order to discover the microwave you first had to work on radar technology which had nothing to do with microwaves but because of the inventions made in radar technology you could then invent the microwave easily so it kind of jumped over into the space of ovens basically before you only had to make food warm was just put it in an oven and heat it up now he had the microwave so that kind of these algorithms capture the spirit of this a book they that the people who gave the tutorial wrote is why greatness cannot be planned I'll definitely get that and I can't recommend it since I haven't read it yet but I'm going to get and read it should be fairly interesting so they give them a number they gave a number of examples of this for example robots that can recover from damage because so they had a robot with six legs they trained it to move now they disabled one leg now usually you have one solution like you trained your neural network I don't think it was even a neural network are you trained you're like your system to move this robot as efficiently as possible and now because you only had one solution one legs broken it doesn't work anymore but since you have the entire landscape of solutions you can easily kind of jump to other not as good solutions if you have all legs but you can jump to other solutions in the solution space and try them out which ones do still work if I only now have five legs since you have the entire landscape you're very well able to do that so that's pretty cool the another algorithm tape and it was go

Explorer which is an algorithm that kind of solved these really hard Atari games while a while back and what they do in specific is they kind of have an archive of states that they have reached in the past so it's a video game and you do some things and then you are in certain states so it's an archive of states and you just pick one of that right you pick like okay this state it means I'm like my little person I control is somewhere over there and then you just explore from it right you do a population based you just kind of go around from it and so on and then you look at the state you end up in and if is a known state like you've been there before so it's also in your archive then you compare the two did you get faster to that state via the new route or route that was already in your archive and if you're faster in that state via the new route you will you replace the archived one with the new one so this again is kind of like a Dijkstra's shortest path algorithm extrapolated to this do this kind of domain where you have to explore you don't actually have a graph so I think it's pretty cool it's all kind of the same principle but it can employ this goal switching thing right so you go to a certain state but then all of a sudden because you explored something else you find a much quicker way to that state which you never intended that it happens so this yeah this is a basic principle that kind of if you explore a lot then good things might happen so kind of a serendipity discovery mechanism and you could use those good things incorporate them into the things that already work the last topic they covered was open-ended search

so a distinction from what they've already discussed to open-ended is now they give the example again life on earth if you consider it it's a single run of an algorithm it's not that for every life form a different optimization was started and kind of started and finished optimized for a certain thing it's all one single run of the same algorithm and it doesn't really have a goal in mind so open-ended algorithms are like that they kind of define interesting notion is it still interesting if we were to just let it run for a billion years like would it still be interesting if yes consider it an open-ended algorithm which I find a really good than the definition so the fundamental property that open-ended algorithms have and research in this has defined is that constantly not only is the population shifting but also the environment is shifting so there's kind of a never static situation the environment is always shifting that also means there's always new opportunities opening up for kind of new life on earth for new creatures to evolve to kind of fill the niches that open up and the research community around this the open-ended search open and learning community is considering exactly those types of environments like how can they even describe those manufacture those and then learning those so pretty cool a cool experiment they've shown was

the pig breeder experiment or basically it's human-in-the-loop so they gave human humans could cooperate so as a human you go to a website you pick one picture and these pictures are procedurally generated so they start out with a very simple pattern and you just have the opportunity to kind of you pick one and it gives you a bunch of random perturbations of the procedurally generated image and you pick the ones that you like and then you continue exploring from there and if you're happy you can just save that to the database and someone else can look through the database and then pick yours for example to continue and the things that the humans came up with or that the result of that was extremely interesting so um so not only could you perturb but you could also kind of mix pictures as far as I remember not sure anymore but yeah so but the things they end up with is yeah you could breed pictures right you could kind of also put pictures together so the procedural generation of them and what you end up with or is remarkable remarkably interesting things and the point they made is it's really only from very few iterations these are like tens or hundreds of iterations of development not like a million like we're used to and there's real tree or phylogenies that emerge and the crucial lesson they say is people only find when they are not looking so if you had a certain goal in mind you will never be able to you know change the pictures in the way that this goal would appear but if you have no goal in mind you might discover all kinds of interesting things yeah so that is a kind of all I'm going to say of this they discussed many more things but I think these are the main takeaways

so population population-based search is interesting because it can kind of overcome the problems that if you only had one optimizer and one optimization run of one algorithm if you employ quality diversity in the algorithm map elites this enables this kind of goal switching it gives you back an entire landscape of IV of learned actors or systems that for each one you know it's kind of the best performing one in that particular constraint of the of the dimensions you care about and yeah open-ended algorithms open-ended search is definitely a cool research direction and I encourage you to check it out all right that was it so far thanks for listening bye