MIT 6.S094: Deep Reinforcement Learning for Motion Planning

All right. Hello everybody. Welcome back. Glad you came back. Today we will unveil the first tutorial, the first project, this deep traffic, codenamed deep traffic, where your task is to solve the traffic problem using deep reinforcement learning. And I'll talk about what's involved in designing a network there, how you submit your own network, and how you participate in the competition. As I said, the winner gets a very special prize to be announced later. What is machine learning? Several types. There's supervised learning. As I mentioned yesterday, that's what meant. Usually when you discuss about, you talk about machine learning and talk about its successes. Supervised learning requires a data set where you know the ground truth, you know the inputs and the outputs, and you provide that to a machine learning algorithm in order to learn the mapping between the inputs and the outputs in such a way that you can generalize to further examples in the future. Unsupervised learning is the other side. When you know absolutely nothing about the outputs, about the truth of the data that you're working with, all you get is data. And you have to find underlying structure, underlying representation of the data that's meaningful for you to accomplish a certain task, whatever that is. There's semi supervised data where only parts, usually a very small amount, is, has, is labeled. There's ground truth available for just a small fraction of it. If you think of images that are out there on the Internet, and then you think about ImageNet, a data set where every image is labeled, the size of that ImageNet data set is a tiny subset of all the images available online. But that's the task we're dealing with as human beings, as people interested in doing machine learning is how to expand the size of that, of the part of our data that we know something confidently about. And reinforcement learning sits somewhere in between. It's, it's semi supervised learning where there's an agent that has to exist in the world and that agent knows the inputs that the world provides, but knows very little about that world except through occasional time delayed rewards. This is what it's like to be human. This is what life is about. You don't know what's good and bad. You kind of have to just live it. And every once in a while you find out that all that stuff you did last week was pretty bad idea. That's reinforcement learning. That's semi. So supervised in the sense that only a small subset of the data comes with some ground truth, some certainty that you have to then extract knowledge from. So first, at the core of anything that works currently in Terms of, in a practical sense, there has to be some ground truth. There has to be some truth that we can hold onto as we try to generalize, and that's supervised learning. Even as in reinforcement learning, the only thing we can count on is that truth that comes in the form of a reward. So the standard supervised learning pipeline is you have some raw data, the inputs, you have ground truth, the labels, the outputs that matches to the inputs. Then you run a certain, any kind of algorithm, whether that's a neural network or another pre processing processing algorithm that extracts the features from that data set. You can think of a picture of a face. That algorithm could extract the nose, the eyes, the corners of the eyes, the pupil, or even lower level features in that image. After that, we insert those features into a, into a model, a machine learning model. We train that model. Then we, as we, whatever that algorithm is, as we pass it through that training process, we then evaluate, after we've seen this one particular example, how much better are we at other tasks. And as we repeat this loop, the model learns to perform better and better at generalizing from the raw data to the labels that we have. And finally you get to release that model into the wild to actually do prediction on data as never seen before that you don't know about. And the task there is to predict the labels. Okay, so neural networks is what this class is about. It's one of the machine learning algorithms that has proven to be very successful. And the building block, the computational building block of a neural network is a neuron. A perceptron is a type of neuron. It's the original old school neuron where the output is binary, a 0 or 1. It's not real valued. And the process that a perceptron goes through is it has multiple inputs and a single output. The inputs, each of the inputs have weights on them, shown here on the left as 0.7, 0.6, 1.4. Those weights are applied to the inputs and a perceptron. The inputs are ones or zeros, binary. And those weights are applied and then sum together. A bias on each neuron is then added on top and a threshold. There's a test whether that summed value plus the bias is below or above a threshold. If it's above a threshold, produces a 1. If it's below a threshold, it produces a 0. Simple. It's one of the only things we understand about neural networks confidently. We can prove a lot of things about this neuron. For example, what we know is that a neuron can Approximate a NAND gate. A NAND gate is a logical operation. A logical function that takes this input has two inputs, A and B, here on the diagram on the left, and the table shows what that function is. When the inputs are zeros, 0, 1 in any order, the output is a 1, otherwise it's a 0. The cool thing about a NAND gate is that it's a universal gate that you can build up. Any computer, you have your phone in your pocket today can be built out of just NAND gates. So it's functionally complete. You could build any logical function out of them if you stack them together in arbitrary ways. The problem with NAND gates and computers is they're built from the bottom up. You have to design these circuits of NAND gates. So the cool thing here is with the perceptron, we can learn this magical NAND gate, we can learn this function. So let's go through how we can do that, how a perceptron can perform the NAND operation. Here's the four examples. If we put the weights of negative 2 on each of the inputs and a bias of 3 on the neuron, and if we perform that same operation of summing the weights times the inputs plus the bias in the top left, we get, when the inputs are zeros, their sum to the bias, we get a three. That's a positive number, which means the output of a perceptron will be a one. In the top right, when the input is a zero and a one, that sum is still a positive number, again produces a one and so on. When the inputs are both ones, then the output is a negative one less than zero. So while this is simple, it's really important to think about. It's a sort of the one basic computational truth you can hold onto as we talk about some of the magical things neural network can do. Because if you compare a circuit of NAND gates and a circuit of neurons, the difference while a circuit of neurons, which is what we think of as a neural network, can perform the same thing as the circuit of NAND gates, what it can also do is it can learn, it can learn the arbitrary logical functions that arbitrary circuit of NAND gates can represent. But it doesn't require the human designer. We can evolve, if you will. So one of the key aspects here, one of the key drawbacks of Perceptron is it's not very smooth in its output. As we change the weights on the inputs and we change the bias and we tweak it a little bit, it's Very likely that when you get, it's very easy to make the neuron output a zero instead of a one or one instead of a zero. So when we start stacking many of these together, it's hard to control the output of the thing as a whole. Now, the essential step that makes a neural network work, that a circuit of perceptrons doesn't, is if the output is made smooth, is made continuous with an activation function. And so instead of using a step function like a perceptron does, shown there on the left, we use any kind of smooth function, a sigmoid, where the output can change gradually as you change the weights and the bias. And this is a basic but critical step. And so learning is generally the process of adjusting those weights gradually and seeing how it has an effect on the rest of the network. You just keep tweaking weights here and there and seeing how much closer you get to the ground truth. And if you get farther away, you just adjust the weights in the opposite direction. That's neural networks in a nutshell. There is what we'll mostly talk about today is feed forward neural networks on the left, going from inputs to outputs with no loops. There is also these amazing things called recurrent neural networks. They're amazing because they have memory, they have a memory of state. They remember the temporal dynamics of the data that went through. But the painful thing is that they're really hard to train. Today we'll talk about feedforward neural networks. So. So let's look at this example, an example of stacking a few of these neurons together. Let's think of the task, the basic task, now famous using the classification of numbers. You have an image of a number, handwritten number, and your task is given that image to say what number is in that image. Now, what is an image? An image is a collection of pixels. In this case, 28 by 28 pixels. That's a total of 784 numbers. Those numbers are from 0 to 255 and on the left of the network. The size of that input, despite the diagram, is 784 neurons. That's the input. Then comes the hidden layer. It's called the hidden layer because. It has no interaction with the input or the output. It is simply a block used. It's at the core of the computational power of neural networks is the hidden layer. It's tasked with forming a representation of the data in such a way that it maps from the inputs to the outputs. In this case, there is 15 neurons in the hidden layer. There is 10 values on the output corresponding to each of the numbers? There are several ways you could, you can build this kind of network. And this is what the magic of neural networks is. You can do it a lot of ways. You only really need 4 outputs to represent values 0 through 9. But in practice it seems that having 10 outputs works better. And how do these work? Whenever the input is a 5, the output neuron in charge of the 5 gets really excited and output a value that's close to 1, from 0 to 1, close to 1, and then the other ones get output a value hopefully that is close to zero. And when they don't, we adjust the weights in such a way that they get closer to zero and closer to one, depending on whether it's the correct neuron associated with the picture. We'll talk about the details of this training process more tomorrow when it's more relevant. But what we've discussed just now is the forward pass through the network. It's the pass when you take the inputs, apply the weights, sum them together, add the bias, produce the output and check which of the outputs produces the highest confidence of the number. Then once those probabilities for each of the numbers is is provided, we determine the gradient that's used to punish or reward the weights that resulted in either the correct or the incorrect decisions. And that's called back propagation. We step backwards through the network applying those punishments or rewards. Because of the smoothness of the activation functions, that is a mathematically efficient operation. That's where the GPUs step in so far. Example of numbers. The ground truth for number six looks like the following in the slides. Y of X equals to a ten dimensional vector where only one of them, the sixth value is a one, the rest are zero. That's the ground truth that comes with the image, the loss function. Here, the basic loss function is the squared error, Y of X is the ground truth and A is the output of the neural network resulting from the forward pass. So when you input that number of a 6 and it outputs whatever it outputs, that's a a 10 dimensional vector and it's summed over the inputs to produce the squared error. That's our loss function, the loss function, the objective function. That's what's used to determine how much to reward or punish the back propagated weights throughout the network. And the basic operation of optimizing that loss function, of minimizing that loss function is done with various variants of gradient descent. It's hopefully a somewhat smooth function, but it's a highly Nonlinear function. This is why we can't prove much about neural networks. It's a highly high dimensional, highly nonlinear function that's hopefully smooth enough where the gradient descent can find its way to at least a good solution. And there has to be some stochastic element there that doesn't get, that jumps around to ensure that it doesn't get stuck in a local minima of this very complex function. Okay, that's supervised learning. There's inputs, there's outputs. Ground truth. That's our comfort zone because we're pretty confident we know what's going on. All you have to do is just, you have this data set, you train and you train a network on that data set and you can evaluate it, you can write a paper and try to beat a previous paper. It's great. The problem is when you then use that neural network to create an intelligent system that you put out there in the world, and now that system no longer is working with your data set, it has to exist in this world that doesn't. That's may be very different from the ground truth. So the takeaway from supervised learning is that neural networks are great at memorization, but in a sort of philosophical way. They might not be great at generalizing at reasoning beyond the specific flavor of data set that they were trained on. The hope for reinforcement learning is that we can extend the knowledge we gain in a supervised way to the huge world outside where we don't have the ground truth of how to act, of what does, how good a certain state is or how bad a certain state is. This is a kind of brute force reasoning. And I'll talk about kind of what I mean there, but it feels like it's closer to reasoning as opposed to memorization. That's a good way to think of supervised learning as memorization. You're just studying for an exam. And as many of you know, that doesn't mean you're going to be successful in life just because you get an A. And so a reinforcement learning agent, or just any agent, a human being, or any machine existing in this world can operate in the following way. From the perspective of the agent, it can execute an action. It can receive an observation resulting from that action in a form of a new state, and it can receive a reward or a punishment. You can break down every, you can break down our existence in this way. Simplistic view, but it's a convenient one on the computational side. And from the environment side, the environment receives the action, emits the observation. So your action changes the world. Therefore that world has to change and then tell you about it and give you a reward or punishment for it. So let's look at again, one of the most fascinating things I'll try to convey why this is fascinating a little bit later on is the work of DeepMind on Atari. This is Atari Breakout, a game where a paddle has to move around. That's the world it's existing in. It's a paddle. The agent is a paddle. And there's a bouncing ball. And you're trying to move your actions to the right. Move right, move left. You're trying to move in such a way that the ball doesn't get past you. And so here is a human level performance of that agent. And so what does this paddle have to do? It has to operate in this environment. It has to act, move left, move right. Each action changes the state of the world. This may seem obvious, but moving right changes visually the state of the world. In fact, what we're watching now on the slides is the world changing before your eyes for this little guy. And it gets rewards or punishments? Rewards it gets in the form of points. They're racking up points in the top left of the, of the video. And then when the ball gets past the paddle, it gets punished by dying, quote, unquote. And that's the number of lives there's left. Going from five to four to three, down to zero. And so the goal is to select at any one moment the action that maximizes future reward. Without any knowledge of what a reward is, in a greater sense of the word, all you have is an instantaneous reward or punishment, instantaneous response of the world to your actions. And this can be modeled as a Markov decision process. Markov decision process is a mathematically convenient construct. It has no memory. All you get is you have a state that you're currently in. You perform an action, you get a reward, and you find yourself in a new state. And that repeats over and over. From state zero, you go to state one. You once again repeat an action, get a reward, go to the next state. Ok? That's the formulation that we're operating in. When you're in a certain state, you have no memory of what happened two states ago. Everything is operating on the instantaneous, instantaneously. And so what are the major components of a reinforcement learning agent? There's a policy that's, that's the agent, the function broadly defined of an agent's behavior. That means that includes the knowledge of how for any given state, what is an action that I will take with some probability value function is how good each state and action are in any particular state. And there's a model. Now this is a little, a subtle thing that is actually the biggest problem with everything you'll see today is the model is how we represent the environment. And what you'll see today is some amazing things that neural networks can achieve on a relatively simplistic model of the world. And the question whether that model can extend to the real world where human lives are at stake. In the case of driving. So let's look at the simplistic world. A robot in a room. You start at the bottom left. Your goal is to get to the top right. Your possible actions are going up, down, left and right. Now this world could be deterministic, which means when you take, when you go up, you actually go up. Or it could be non deterministic. As human life is when you go up, sometimes you go right. So in this case, if you choose to go up, you move up 80% of the time, you move left 10% of the time, and you move right 10% of the time. And when you get to the top right, you get a reward of plus one. When you get to the second block from that four, two, you get negative one, you get punished, and every time you take a step, you get a slight punishment of.04. Okay, so the question is, if you start at the bottom left, is this a good solution? Is this a good policy by which you exist in the world? And it is. If the world is deterministic, if whenever you choose to go up, you go up, when you choose to go right, you go right. But if the actions are stochastic, that's not the case in what I described previously with 0.8 up and probability of 0.1 going left and right, this is the optimal policy. Now, if we punish every single step with a negative 2 as opposed to negative 0.04, so every time you take a step, it hurts, you're going to try to get to a positive block as quickly as possible. And that's what this policy says. I'll walk through a negative one if I have to as long as I get stop getting the negative 2. Now if the reward for each step is negative 0.1, you might choose to go around that negative 1 block, slight detour to avoid the pain. And then you might take an even longer detour as the reward for each step goes up or the punishment goes down, I guess. And then, And then if the there is an actual positive reward for every step you take, then you'll never, you'll avoid going to your the finish line. You'll just wander the world. We saw that with the coast racer yesterday, the boat that chose not to finish the race because it was having too much fun getting points in the middle. So let's look at the world that this agent is operating in as a value function. That value function depends on a reward, the reward that comes in the future. And that reward is discounted because the world is stochastic. We can't expect the reward to come along to us in the way that we hope it does based on the policy, based on the way we choose to act. And so there's a gamma there that over time, as the reward is farther and farther into the future, discounts that reward diminishes the impact of that future reward in your evaluation of the current state. And so your goal is to develop a strategy that maximizes the discounted future reward. The sum. This discounted sum and reinforcement learning. There's a lot of approaches for coming up with a good policy. A near optimal, an optimal policy. There's a lot of fun math there. You could try to construct a model that optimizes some estimate of this world. You can try in a Monte Carlo way to just simulate that world and see how it unrolls. And as it unrolls, you try to compute the optimal policy. Or what we'll talk about today is Q learning. It's an off policy approach where the policy is estimated as we go along. The policy is represented as a Q function. The Q function shown there on the left is I apologize for the equations. I lied. There'll be some equations. The the input to the Q function is a state at time t st and an action that you choose to take in that state at. And your goal is in that state to choose an action which maximizes the reward. In the next step, and what Q learning does, and I'll describe the process, is it's able to approximate through experience the optimal Q function. The optimal function that tells you how to act in any state of the world. You just have to live it. You have to simulate this world. You have to move about it. You have to explore in order to see every possible state, try every different action, get rewarded, get punished, and figure out what is the optimal thing to do. That's done using this Bellman equation. On the left. The output is the new state. The estimate, the Q function estimate of the new state for new action. And this is the update rule at the core of Q learning. You take the estimate the old estimate and add based on the learning rate alpha from 0 to 1, update the evaluation of that state based on your new reward that you received at that time. So you've arrived in a certain state st, you try to do an action and then you got a certain reward and you update your estimate of that state and action pair based on this rule. When the Learning rate is 0, you don't learn. When Alpha is 0, you never change your worldview based on the new, the new incoming evidence. When alpha is one, you every time change your evaluation, your world evaluation, based on the new evidence. And that's the key ingredient to reinforcement learning. First you explore, then you exploit. First you explore in a non greedy way, and then you get greedy. You figure out what's good for you and you keep doing it. So if you want to learn an Atari game, first you try every single action, every state. You screw up, get punished, get rewarded, and eventually you figure out what's actually the right thing to do and you just keep doing it. And that's how you win against the greatest human players in the world. In a game of Go, for example, as we'll talk about. And the way you do that is you have an epsilon greedy policy that over time, with a probability of 1 minus ε, you perform an optimal greedy action. With a probability of epsilon, you perform a random action. Random action being explore. And so as epsilon goes down from 1 to 0, you explore less and less. So the algorithm here is really simple. On the bottom of the slide there, it's the algorithm version, the pseudocode version of the equation, the Bellman equation update. You initialize your estimate of state, action pairs arbitrarily a random number. Now this is an important point. When you start playing or living or doing whatever you're doing, whatever you're doing with reinforcement learning or driving, you have no preconceived notion of what's good and bad. It's random or however you choose to initialize it. And the fact that it learns anything is amazing. I want you to remember that that's one of the amazing things about the Q learning at all. And then the Deep Neural Network version of Q learning, the algorithm repeats the following step. You step into the world, observe an initial state. You select an action A. So that action if you're exploring will be a random action. If you're greedily pursuing the best action you can, it will be the action that maximizes the Q function. You observe a reward after you take the action and a new state that you find yourself in. And then you update your estimate of the previous state you were in, having taken that action using that Bellman equation. Update and repeat this over and over. And so there on the bottom of the slide is a summary of life. Yes. Hey. The Q function. Yeah. Yes, yes. Yeah. It's a single. The question was, is the Q function a single value? And, yes, it's just a single continuous value. So the question was, how do you model the world? So the way you model. So let's start this very simplistic world of Atari. Paddle. You think you model it as a paddle that can move left and right and there's some blocks, and you model the physics of the ball. That requires a lot of expert knowledge in that particular game. So you sit there handcrafting this model. That's hard to do even for a simplistic game. The other model you could take is looking at this world in the way that humans do visually. So take the model in as a set of pixels. Just the model is all the pixels of the world. You know nothing about paddles or balls or physics or colors and points. There's just pixels coming in. That seems like a ridiculous model of the world, but it seems to work for Atari. It seems to work for human beings. When you're born, you see there's light coming into your eyes, and you don't have any, as far as we know. You don't come with an instruction. When you're born, you know, there's people in the world, and there is good guys and bad guys, and there's. This is how you walk. No, all you get is light, sound, and the other sensors and. And you get to learn about the. Every single thing you think of as the way you model the world is a learned representation. And we'll talk about how a neural network does that. It learns to represent the world. But if we have to hand model the world, it's an impossible task. That's the question. If we have to hand model the world, then that world better be a simplistic one. That's a great question. So the question was, what is the robustness of this model if the way you represent the world is at all even slightly different from the way you thought that world is? That's not that well studied, as far as I'm aware. I mean, it's already amazing that if you construct, if you have a certain input of the world, if you have a certain model of the world, that you can learn anything. It's already amazing. The question is, and it's an important one, is we'll talk a little bit about it. Not about the world model, but the reward function. If the reward function is slightly different, the real reward function of life or driving or of Coast Runner is different than what you expected it to be. What's the negative there? Yeah, it could be huge. There was another question or. No, nevermind. Yep. Sorry, can you ask that again? Yes, you can change it over. So the question was, do you change the alpha value over time? And you certainly should change the alpha value over time. Yeah. What is the. So the question was what is the. The complex interplay of the epsilon function with the Q learning update that's 100% fine tuned, hand tuned to the particular learning problem. So you certainly want to. The more complex, the larger the number of states in the world and the larger the number of actions, the longer you have to wait before you decrease the epsilon to zero. But you have to play with it. It's one of the parameters you have to play with, unfortunately. And there's quite a few of them, which is why you can't just drop a reinforcement learning agent into the world. Oh, the effect in that sense. No, no, it's just a coin flip. And if that ε is 0.5, half the time you're going to take a random action. So there's no specific. It's not like you'll take the best action and then with some probability take the second best and so on. I mean you could certainly do that. But in the simple formulation that works is you just take a random action because you don't want to have a preconceived notion of what's a good action to try when you're exploring. The whole point is you try crazy stuff if it's a simulation. Okay, so good question. So representation matters. This is the question about how we represent the world. So we can think of this world of Breakout, for example, of this Atari game as a paddle that moves left and right and the exact position of the different things it can hit. Construct this complex model, this expert driven model that has to fine tune it to this particular problem. But in practice, the more complex this model gets, the worse that Bellman Equation update Trying to construct a Q function for every single combination of state and actions becomes too difficult because that function is too sparse and huge. So if you think of looking at this world in a general way, in the way human beings would, this is a collection of pixels. Visually, if you just take in a pixel, this game is a collection of 84 by 84 pixels, an image, an RGB image and Then you look at not just the current image, but look at the temporal trajectory of those images. So like, if there's a ball moving, you want to know about that movement. So you look at four images, so current image and three images back and say they're gray scale with 256 gray levels. That size of the Q table that the Q value function has to learn is whatever that number is, but it's certainly larger than the number of atoms in the universe. That's a large number. So you have to run the simulation long enough to touch at least a few times most of the states in that Q table. So as Elon Musk says, you may need to run, you know, we live in a simulation. You may run, have to run a universe just to, to, to compute the, the. The Q function in this case. So that's where deep learning steps in. As, instead of modeling the world as a Q table, you estimate, you try to learn that function. And so the takeaway from supervised learning, if you remember that it's good at memorizing, we're good at memorizing data. The hope for reinforcement learning with a Q Q learning is that we can extend the occasional rewards. We get to generalize over the operation, the actions you take in that world leading up to the rewards. And the hope for deep learning is that we can move this reinforcement learning system into a world that doesn't need to be, that can be defined arbitrarily, can include all the pixels of an Atari game, can include all the pixels sensed by a drone or a robot or a car. But still it needs a formalized definition of that world, which is much easier to do when you're able to take in sensors like an image. So deep Q learning, deep version. So instead of learning a Q table, a Q function, we try in estimating that Q prime. We try to learn it using machine learning. So it tries to learn some parameters this huge.