How to teach space invaders to your computer

Speaker 1 [00:03]

Hello everyone, do you hear me? It's okay? Great. My talk today is how to teach space invaders to your computer. And this talk could also be taught a very, very brief introduction to reinforcement learning. And I hope that at the end of the talk you will probably not be able to reproduce everything I've shown you, but you maybe have a mere idea what is reinforcement learning, how could you apply it, and what could be possible issues that you face along the way. To do so, I will give you a little motivation to begin with, so basically why I care about space and data. I will try to very glimpse, surface-y, scratch-y thingy about reinforcement learning theory. I will show you an example algorithm that I've actually trained for you to showcase, and I will show you some results and everything, and in the end, obviously, a little summary. So let's go. Before I start, obviously, a little advertisement block. I work at the FZI Research Center for Information Technology, located here in Karlsruhe. And we see ourselves as a transfer institution between universitary research and applied information technology in the industry. So we try to transfer the research knowledge to the industry and get impulses back to the research. That's, in my opinion, a very nice place to work. That's why I like to advertise a little bit. We have a lot of interesting fields like cybersecurity, software engineering, robotics, ambient assisted living. That's technology that helps elderly people, new transportation, autonomous vehicles, and last but not least, also the energy domain. And that's where I work on. And one second, please. We're always looking for project partners. That is people who like to have a paid research project. We look for partners that will apply for research funding with us. We also have usually a lot of open jobs for students, theses, and we always look for scientists, research scientists, that is people that usually do a PhD aside. And if you're interested in that, well, talk to me, go on our website, check the open positions. It's very nice to work there, really. Okay, that's enough advertisement for today. My research basically tries to improve the energy efficiency of buildings, and I try to do so by using smart algorithms. And the idea is basically that you try to, well, consider that that building that you see in the picture, yet there might be a PV system, photovoltaic system on the roof, and it might generate some energy for you, but how much energy, how that energy is worth for you kind of depends on when you receive the energy. So when it always generates energy when you're not at home, then you will feed it into the grid, so we receive some money out of it. But if you can store it in a battery and can use it later, then you might save more money out of it. And the question is now how to control that battery in order to, for example, optimize your own consumption or in order to maybe stabilize the grid if you consider some smart grid approach. There's a lot of research going on in the field. It's more than 20 years of research now. And most people actually do explicit modeling. What I'm trying to do is actually I try to develop a self-learning system. That is, an algorithm that interacts with the building and figures out how to optimize that building. And if you want to optimize the building, you usually have to take sequential decisions. That means I have to decide now what to do in the next minute, and then one minute later what to do next. And these decisions will usually influence each other. So if I now decide to charge the battery to full, I will not have a chance of charging it any further in the next time step. Also, this interaction means that my algorithm will change the world that it will see in the later time. And that's basically the two very fundamental definitions of reinforcement learning in contrast to deep learning, that you have sequential decisions and that you have interaction, and that is you get some feedback from the environment which you interact with. So, why should you study Space Invaders then? Well, it turns out that Atari games have developed something as a benchmark problem for reinforcement learning. It's a bit like MNIST for deep learning people. That means that whatever paper you open, you usually will find somewhere a little section about this is how good our algorithm has performed on this and that Atari games. So from my point of view, that's a good starting point because that means that you have a way lot of actual papers where you can have a look how they implemented their stuff and you can try to reproduce it to get started. So a little, very overview about terminology that you can, well, may understand the rest easier. Well, if you consider the game of Space Invaders as you've seen it on the title slide, then the environment is the actual game of Space Invaders and that environment usually proceeds in discrete time steps and after each time step the environment will emit an observation and this observation is the screenshot so it's the last last game image you get from the screen and you will also receive a reward signal that reward signal means how much score have you received during that last time step while you probably shot an alien ship so you received some 25 points for that you will give that reward signal and the observation signal to the agent and the agent is It's the program that decides what to do next. And this agent will pick an action. And you will give that action back to your environment. The environment will proceed the next time step and so on and so on. And I think you see very soon that this is, or very easily that this is a loop. And this loop will usually proceed until the game is over. And then you have a full episode. Okay, go on. Well, how can we now approach this? Well, one common approach, that is, where most of research is actually happening, I would call it classic reinforcement learning approach. That works like you try to abstract a state, and a state is an absolute position, where are you in your search space? In your abstract search space, over all your search dimensions, where are you? And what you're trying to do is you try to estimate how good is it to be in any particular state of that search space that you can access, And then you try to, for every state that you're actually then in, you try to evaluate, given the possible states I can reach, which one is that that receives most information or the highest reward, and I will then usually enter that state next. But as you already probably see now, this is a complicated construct. And actually, if you want to get deeper into that, and I would actually recommend it because the theory about it is very beautiful, you will need probably a few months of reading and looking and I've collected some textbook and a lecture series and some exercises for you on the links. It's not my content. It's by, well, common researchers that are very easy and newcomer-friendly entries to that material. But obviously, that theory is far beyond 30-minute talk at PyCon. So we have to find something else. And what we can actually do is called evolutionary method. Evolutionary method means we use black box optimization. So we try to find a direct mapping from our observations to actions. And that also means that our optimizer or optimization algorithm will usually not have any information about how the game proceeded intermediately. But he will just receive a finite signal like he will put in some parameters and then in the end he will receive a reward for that. and that's all he sees, in contrast to the other approach before that had very close interaction for every time step. In the next slide, I will try to give you a very brief overview how you could implement such a thing, such an evolutionary method, using existing building blocks. I follow a concept of a paper called World Models by David Ha and Jürgen Schmidhuber. I actually can recommend everybody to read that paper if you care for reinforcement learning because it's very well written and has nice applications. In that paper, they try to solve those two environments you see as a video in the back. So the videos are actually credited to them. And yeah, let's go further, please. Yes. So first, we need an optimizer, okay? So I said we made black box optimization, so we need to optimize something. And the optimizer of choice In that case, it's called CMAES, which stands for Covariance Metrics Adaption Evolution Strategy. That is usually a very defaulty choice in reinforcement learning and also in other optimization problems, as long as the dimensionality of your problem you're trying to solve is roughly below 1,000. That's a reference publication if you want to know more about it. And it's especially well often chosen because it's, well, relatively stable, and it has only very few hyperparameters to tune, and that's a nice thing, isn't it? And just to show you that it's actually very easy to apply, there's a little code which is actually functional, so that code works and produces the solution you see below, how you could use such an optimizer. In the first block, we will import the module, set our hyperparameters, that is our initial solution, standard deviation, so how far should we look left and right, population size which is the only true hyperparameter and get a or define a reward function in that case reward function means that would be the game you know consider this as the game but as i can't show you the game in two lines of code this is i will use the rosenberg function instead it's very common test function for optimization problems and it has the nice that no matter how many dimensions you request from it, the optimal solution is always at one, one, one, one, one, and then there are so many ones following as much dimension you are having. And the second block is then just the loop that will actually execute the code or would let the optimizer run, and all it does is it's three steps for the optimization. You will, in the first step, sample from a multivariate Gaussian, that's the mathematics behind CMAES, you will compute the rewards corresponding to the candidates you got from the algorithm, and you will tell the algorithm back how good their candidates have been. And after what the algorithm then does, as is, he will see like, okay, you have sampled 25 candidates, 25 candidates, these were the rewards for these candidates, now I know which ones have been performed good and which ones have been performed worse. And I would try to get my multivariate Gaussian or modify it in such a way that I get more good results. And as you also can see on the very end of the code, it nearly found the optimal point. So I hope that's a little proof it works. So now go on. Now we have that abstract optimization algorithm. How can we apply it to space invaders? Well, the most simple approach that you can use is actually you make a direct mapping from observations to actions. And the actions in that case are six integers actually which correspond to left, right, fire, do nothing, left and fire, and right and fire. And for space invaders, well the input is actually the image we receive. And now comes the tricky part, the image consists of 210 times 160 times three color channels, and that's roughly 100,000, and then you have to map it to six outputs, so that leaves you with roughly 600,000 weights that you need to optimize. But I told you before that CMA-S works only if you have a dimensionality below 1,000, and 600,000 is very much larger than 1,000, obviously. So the solution proposed in the paper is to use an autoencoder to reduce the dimensionality of your problem. So next theory, and I promise hopefully last theory slide, what is an autoencoder? Well, an autoencoder is a usual neural network, or actually two neural networks, one for encoding, one for decoding. And what you do is you map your input, like say your image, usually it's an image, to a network, and that network tries to compress it, and in the end it will have some bottleneck. So that's a reduced, or you could say compressed representation. In my case, it's 64 float numbers. And after that, you have a decoder, which then tries to reconstruct the original image. And you train an autoencoder by comparing your original input with the reconstructed input and put that in a supervised learning algorithm. So it's not really supervised because it has no labels, but it still uses supervised learning. So many people call it semi-supervised learning. If you want to know more about autoencoders, there's a nice blog spot from Keras where they have their interactive code examples and anything, and you can play around with that. That's all the depth for me for today. So let's see what happens if we actually do that. The training algorithm I've implemented looked as follows. Well, in the end, sorry, in the beginning, I have built and trained the autoencoder with episodes generated by random policy. Random policy means I've told the game that it just pushes a button like you probably did when you were younger and you played Tekken, you know, or I did at least. That's the same thing the game does, to get images for the, or to create images for the autoencoder. And afterwards, next step, we will build the agent model. That's a neural network, 64 inputs, 6 outputs, fully connected, no hidden layers. We will initialize CMES and then enter our repeat loop. for each loop we will sample 32 candidates compute the average reward over three episodes because the Space Invaders environment is kind of stochastic so it always behaves a little bit different and we want to have a solution that performs good like many times, not just once and afterwards we trigger the optimization step giving all the 32 rewards back to CMAES and let it work and what comes out of there is actually the plot you see on the right side and what's in the plot on the y-axis you see the reward on the x-axis you see the generation and the blue line is actually the average reward over all members of that popular of that generation and the orange line is the best agent found through that generation and actually the best agent I found through all the training time is at generation 86 and it has produced well at least in the training a reward of 630 but if you evaluate it later like said let it play for another 50 episodes and average that you will see that the agent only received an award of 252 which is roughly 100 points better than just pushing buttons. So the question that's a little bit it's okay, it's better than doing random, so that's at least good that it means that it does optimize anything, but it's still much below what I've expected when I started this and when I handed in this talk or when I applied for it. And now I ask myself, why didn't it get any better? In the end or in the beginning, it found a solution very fast, like in few generations found a good solution, and then it didn't learn anything any further. So why is that the case? So let's have a look at the actual gameplay. What you see here is the agent on the left side. You see an average episode of the best agent. And on the right-hand side, you will see the reconstructed image as it is given by the autoencoder. So you put that image, which you see on the left side, through a decoder, encoded, now it's re-encoded and decoded again. and then you will receive that image. So that's an indication what the algorithm actually has seen of the game. And if you now have a closer look in it, you will see that actually there are no lasers. So it's pretty pointless to play Space Invaders if you can't see the laser shots because you will just randomly die and you don't know why. What you can also see is that the player ship disappears once it enters the right side. And you will also see that the right column, that one, that column here, will be shot by the agent later in the game, but it still remains there. So it doesn't disappear what we've expected. And you will also see that the mothership, which is this thing here, which gives good scores if you shoot at it, it's also not visible. So, okay, one finding is the autoencoders actually, or autoencoders in general have actually a problem with finding details or encoding details. And about the right-hand side, like now, where this player ship just disappeared, well, the answer lies in the training algorithm. And because I told you that we just pushed buttons, what the actual agent or the training agent, random policy agent did was, it was just going a little bit to the left and a little bit to the right, but on average, it stayed where it spawned. And that's exactly the behavior you see here. So here, it has a good chance of actually shooting away these aliens here, and it has also a good chance of being here. So as long as the ship is here, the autoencoder learns that, and then says, okay, that's the ship, I know how to reconstruct it. And also, if the aliens disappear here, they will disappear here too. So that's great. But I was actually a bit shocked how low the generalization ability of the autoencoder actually is, because I thought, like, you know, come on, this here, it's not so far away. It's the same ship, it's the same game. You could have learned that, but obviously you can't, or the code can't. Yeah. So that leads me to a little of a pre-conclusion slide. What can you now actually do to teach space invaders to your computer after you've seen that the approach I showed you before didn't work out so well? Well, you can use classic reinforcement learning method. So that's the method I've told you before with the state space, you can pick an algorithm from scientific publishing, publications, that's very nice, because it means that you can have just go to the journals, see which algorithm performed best for that game you do want to train, and pick that algorithm, and you have to reimplement it. It's also, maybe you don't even have to reimplement it, and can just use these nice open source libraries like TensorFlow or Baselines, which are, say, It kind of depends. I think if you are a data scientist, you will find that familiar. If you're like a usual Python developer, you will say like, ah, this code is really messy. Depends on your view, but you may have a starting point. The point is, if you want to do so, you probably need to know about or have some domain knowledge or learn something about classic reinforcement learning theory, because if you don't, you will have a very hard time optimizing these algorithms or tweaking them because you don't really understand what's happening there and why people have done and implemented what they have implemented. You always need some deep supervised learning knowledge too because most of the reinforcement learning theory builds up somehow on deep supervised learning. Well, the good thing is if you're going to do so, you have a very high chance of success because, well, obviously other people have done that before and they've proved in papers that they can do so. So you probably can do so too. But the point is, most of these algorithms are kind of tweaked towards Space Invaders because that's the benchmark problem, or like Atari games. So it's not very certain how good they do generalize on other problems you might want to solve. Like in my case, how good is it now to control a building with that? The other option is obviously try to fix the evolutionary reinforcement learning method I've shown you. You could start where I ended in the end, optimizing. You could try to add a loop around the autoencoder and the training of the agent. That would give the autoencoder a chance of learning also states which he hasn't seen by the random agent. For example, that's a thing where the ship was on the very right-hand side of the screen. I think if you would give some training examples to the autoencoder, he could learn that too. you could also support learning the laser shots you could easily make a big white box around each laser shot and actually try that out so that works to improve the visibility and that would also give the autoencoder a bit more chance of of learning that and learning all relevant features but the kind of takeaway is actually from autoencoders that autoencoders are well teaching autoencoders what is actually relevant of the picture or of the video you show them is non-trivial and hard thing to do and if you want to stick with that evolutionary reinforcement learning method you better be very good in computer vision and know how autoencoders are really detailed and how to tweak them maybe then this might be an easier approach for you you also need obviously tube supervised learning because that's what the autoencoder is all about nevertheless it's uncertain if you have good success but it might translate well if you well at least if you find a way to tweak that autoencoder in such a way that it handles the game nicely okay that leaves me with a summary so i hope to show you that reinforcement learning is actually beautiful and it has interesting applications but it's kind of also challenging and to solve reinforcement learning problems you may wish to study the extent of the theory which I can recommend to you. Well, if you don't want to do that you can still use the evolutionary method. If you want to do so CMAS is a reliable choice to begin with but only if your dimensionality is below 1000 or roughly 1000. If it's above 1000 you may still use autoencoders or try it at least. But you should know that if you want to use autoencoders, you must really take care of the details. And you must take care that all the observations that this autoencoder should encode are actually in the training. So, alternatively, many common reinforcement learning algorithms are available and free to use. That's a nice thing, but you, again, need to know the theory to use them. So, after all, if you want to have a look at it, all the code I used for training, The examples you've seen on the screen is online on my GitHub repository. Also, PDF version of the slides if you want to have a look at the links and everything. And if you want to contact me because you now want to apply it after I, I'm very happy for your application. Now, just a joke aside. Also, if you have any other questions, contact me. And please, if you're interested, connect on LinkedIn. Thank you. So thank you very much for the great talk other some questions Hi nice talk one clarification question for the auto encoder coda did you use convolution and deconvolution or versus? Okay, and still didn't work well, so it's three three convolutional layers and then it's laying after that. I mean, autoencoders need a lot of fine-tuning and maybe different configurations. Yeah, I think I've spent, like, I don't know, 150 hours of GPU time on fine-tuning the autoencoder, and actually, if you, in the very beginning, like this result I've shown you in the end, that's actually very good. If you compare what the other people from the world models paper have as a result, then I think there are less details in the picture compared to that, especially because the picture is kind of high-dimensional. Like, usually autoencoders are trained on 64 by 64 pixel images. So I'm at least a little bit proud about the result, actually. Okay, thanks. Okay, some more questions. Thank you for the talk. So for games like Space Invaders, you have kind of a simulation environment where you can run your reinforcement learning algorithm. But will you have the same for controlling a building? Kind of depends. Actually, I think to start with, we will have to build something similar to get a very, say, first training example. If I have to do something similar in this building, I would actually start in a simulation, then move to one building and try to do some transfer learning to transfer these results to another building because what actually other people did, they tried to do that and they just found out that their reinforcement learning algorithm works really good after just two and a half years. And if your reinforcement learning algorithm will shut down the heating for two and a half years, well, that's probably not going to happen in real life, is it? Okay, time is over, so please let's thank David again.