MIT 6.S094: Deep Reinforcement Learning

Today we will talk about deep reinforcement learning. The question we would like to explore is to which degree we can teach systems to act, to perceive and act in this world from data. So let's take a step back and think of what is the full range of tasks that an artificial intelligence system needs to accomplish. Here's the stack from top to bottom. Top the input, bottom output, the environment at the top, the world that the agent is operating in, sensed by sensors, taking in the world outside and converting it to raw data, interpretable by machines, sensor data. And from that raw sensor data, you extract features, you extract structure from that data, such that you can input it, make sense of it, discriminate, separate, understand the data, and as we discussed, you form higher and higher order representations, a hierarchy of representations based on which the machine learning techniques can then be applied. Once the machine learning techniques, the understanding, as I mentioned, converts the data into features, into higher order representations, and into simple, actionable, useful information. We aggregate that information into knowledge. We take the pieces of knowledge extracted from the data through the machine learning techniques and to build a taxonomy, a library of knowledge. And with that knowledge, we reason. An agent is tasked to reason, to aggregate, to connect pieces of data seen in the recent past or the distant past, to make sense of the world it's operating in, and finally to make a plan of how to act in that world based on its objectives, based on what it wants to accomplish. As I mentioned, a simple but commonly accepted definition of intelligence is a system that's able to accomplish complex goals. So a system that's operating in an environment in this world must have a goal, must have an objective function, a reward function. And based on that, it forms a plan and takes action. And because it operates in many cases in the physical world, it must have tools, effectors with which it applies the actions to change something about the world. That's the full stack of an artificial intelligence system that acts in the world. And the question is, what kind of task can such a system take on? What kind of task can an artificial intelligence system learn? As we understand AI today, we will talk about the advancement of deep reinforcement learning approaches in some of the fascinating ways. It's able to take much of this stack and treat it as an end to end learning problem. But we look at games, we look at simple formalized worlds. While it's still impressive, beautiful and unprecedented accomplishments, it's nevertheless formal tasks. Can we then move beyond games and into expert tasks of medical diagnosis, of design, and into natural language? And finally the human level tasks of emotion, imagination, consciousness, let's once again review the stack in practicality, in the tools we have. The input for robots operating in the world, from cars to humanoid to drones, is LiDAR camera, radar, GPS, stereo cameras, audio microphone, networking for communication and the various ways to measure kinematics. With I'm you, the raw sensory data is then processed, features are formed, representations are formed and multiple higher and higher order representations. That's what deep learning gets us. Before neural networks, before the advent of, before the recent successes of neural networks to go deeper and therefore be able to form high order representations of the data, that was done by experts, by human experts. Today networks are able to do that. That's the representation piece. And on top of the representation piece, the final layers of these networks are able to accomplish the supervised learning task, the generative tasks and the unsupervised clustering tasks through machine learning. That's what we talked about a little in lecture one and we'll continue tomorrow and Wednesday. That's supervised learning. And you can think about the output of those networks as simple, clean, useful, valuable information. That's the knowledge. And that knowledge can be in the form of single numbers. It could be regression, continuous variables, it could be a sequence of numbers, it could be images, audio, sentences, text, speech. Once that knowledge is extracted and aggregated, how do we connect it in multi resolutional ways, form hierarchies of ideas, connect ideas. The trivial silly example is connecting images, activity, recognition and audio. For example, if it looks like a duck, quacks like a duck and swims like a duck, we do not currently have approaches that effectively integrate this information to produce a higher confidence estimate that is in fact a duck. And the planning piece. The task of taking the sensory information, fusing the sensory information and making action, control and longer term plans based on that information, as we'll discuss today, are more and more amenable to the learning approach, to the deep learning approach. But to date have been the most successful non learning optimization based approaches, like with several of the guest speakers we have, including the creator of this robot ATLAS in Boston Dynamics. So the question how much of the stack can be learned end to end from the input to the output? We know we can learn the representation and the knowledge from the representation and to knowledge. Even with the kernel methods of SVM and certainly with neural networks. Mapping from representation to information has been where the primary success of machine learning over the past three decades has been. Mapping from raw sensory data to knowledge. That's where the success the automated representation was. Learning of deep learning has been a success going Straight from raw data to knowledge. The open question for us today and beyond is if we can expand the red box there of what can be learned end to end, from sensory data to reasoning, so aggregating, forming higher representations of the extracted knowledge and forming plans and acting in this world. From the raw sensory data, we will show the incredible fact that we're able to learn exactly what's shown here end to end with deep reinforcement learning on trivial tasks in a generalizable way. The question is whether that can then move on to real world tasks of autonomous vehicles, of humanoid robotics, and so on. That's the open question. So today let's talk about reinforcement learning. There's three types of machine learning. Supervised, unsupervised are the categories at the extremes relative to the amount of human input that's required for supervised learning. Every piece of data that's used for teaching these systems is first labeled by human beings. And unsupervised learning on the right is no data is labeled by human beings. In between is some sparse input from humans. Semi supervised learning is when only part of the data is provided by humans, ground truth. And the rest must be inferred, generalized by the system. And that's where reinforcement learning falls. Reinforcement learning as shown there with the cats. As I said, every successful presentation must include cats. They're supposed to be Pavlov's cats and ringing a bell. And every time they ring a bell, they're given food and they learn this process. The goal of reinforcement learning is to learn from sparse reward data from, from learn from sparse supervised data and take advantage of the fact that in simulation or in the real world, there is a temporal consistency to the world. There is a temporal dynamics that follows from state to state to state through time. And so you can propagate information even if the information that you received about the supervision, the ground truth, is sparse. You can follow that information back through time and to infer something about the reality of what happened before then, even if your reward signals were weak. So it's using the fact that the physical world evolves through time in some sort of predictable way to take sparse information and generalize it over the entirety of the experience that's being learned. So we apply this to two problems. Today we'll talk about deep traffic as a way to introduce deep reinforcement learning. So deep traffic is a competition that we ran last year and expanded significantly this year. And I'll talk about some of the details and how the folks in this room can on your smartphone today, or if you have a laptop Train an agent. While I'm talking training a neural network in the browser, some of the things we've added are we've added the capability, we've now turned it into a multi agent deep reinforcement learning problem where you can control up to 10 cars within your own network. Perhaps less significant, but pretty cool, is the ability to customize the way the agent looks so you can upload. And people have, to an absurd degree, have already begun doing so, uploading different images instead of the car that's shown there, as long as it maintains the dimensions. Shown here is a SpaceX rocket. The competition is hosted on the website selfdrivingcars. MIT. Edu deeptraffic. We'll return to this later. The code is on GitHub with some more information, a starter code and a paper describing some of the fundamental insights that will help you win at this competition is an archive. So from supervised learning in lecture one to today, supervised learning we can think of as memorization of ground truth data in order to form representations that generalizes from that ground truth. Reinforcement learning is we can think of as a way to brute force propagate that information, the sparse information through time, to assign quality reward to state that does not directly have a reward to make sense of this world. When the rewards are sparse, but are connected through time, you can think of that as reasoning. So the connection through time is modeled in most reinforcement learning approaches very simply that there's an agent taking an action in a state and receiving a reward. And the agent operating in an environment executes an action, receives an observed state, a new state and receives a reward. This process continues over and over. In some examples, we can think of any of the video games, some of which we'll talk about today, like Atari Breakout as the environment, the agent as the paddle. Each action that the agent takes has an influence on the evolution of the environment. And the success is measured by some reward mechanism. In this case, points are given by the game. And every game has a different point scheme that must be converted, normalized into a way that's interpretable by the system. And the goal is to maximize those points, maximize the reward. The continuous problem of cart pole balancing. The goal is to balance the pole on top of a moving cart. The state is the angle, the angular speed, the position, the horizontal velocity. The actions are the horizontal force applied to the cart, and the reward is one at each time step, if the pole is still upright. All the first person shooters, the video games and now Starcraft, the strategy games in case of first person shooter and Doom. What is the goal. The environment is the game. The goal is to eliminate all opponents. The state is the raw game pixels coming in. The actions is moving up, down, left, right, and so on. And the reward is positive when eliminating an opponent and negative when the agent is eliminated. Industrial ROBOTICS BIN packing with a robotic arm. The goal is to pick up a device from a box and put it into a container. The state is the raw pixels of the real world that the robot observes the actions or the possible actions of the robot, the different degrees of freedom and moving through those degrees, moving the different actuators to realize the position of the arm. And the reward is positive when placing a device successfully and negative otherwise. Everything can be modeled in this way. Markov decision process There's a state as zero, action a zero and reward received. A new state is achieved again. Action, reward state, action, reward state Until a terminal state is reached. And the major components of reinforcement learning is a policy. Some kind of plan of what to do in every single state, what kind of action to perform a value function, some kind of sense of what is a good state to be in, of what is a good action to take in a state. And sometimes a model that the agent represents the environment with some kind of sense of the environment it's operating in. The dynamics of that environment that's useful for making decisions about actions. Let's take a trivial example, a grid world of 3 by 412 squares where you start at the bottom left and are tasked with walking about this world to maximize reward. The reward at the top right is a plus one and the one squared below that is a negative one. And every step you take is a punishment or is a negative reward of 0.04. So what is the optimal policy in this world now, when everything is deterministic? Perhaps this is the policy when you start at the bottom left. Well, because every step hurts, every step has a negative reward. Then you want to take the shortest path to the maximum square with the maximum reward when the state space is non deterministic, as presented before, with a probability of 0.8. When you choose to go up, you go up, but with probability 0.1 you go left and.1 you go right. Unfair again, much like life. That would be the optimal policy. What is the key observation here? That every single state in the space must have a plan. Because you can't. Because then a non deterministic aspect of the control, you can't control where you're going to end up. So you must have a plan for every place. That's the policy Having an action, an optimal action to take in every single state. Now, suppose we change the reward structure. And for every step we take, there's a negative reward, is a negative two. So it really hurts. There's a high punishment for every single step we take. So no matter what, we always take the shortest path. The optimal policy is to take the shortest path to the to the only spot on the board that doesn't result in punishment. If we decrease the reward of each step to negative 0.1, the policy changes where there is some extra degree of wandering encouraged. And as we go further and further in lowering the punishment as before to negative 0.04, more wandering and more wandering is allowed. And when we finally turn the reward into positive, so every step, every step increases the reward, then there's a significant incentive to stay on the board without ever reaching the destination. Kind of like college for a lot of people. So the value function, the way we think about the value of a state or the value of anything in the environment, is the reward we're likely to receive in the future. And the way we see the reward we're likely to receive is we discount the future reward because we can't always count on it here at Gamma. Further and further out into the future, more and more discounts decreases the importance of the reward received. And a good strategy is taking the sum of these rewards and maximizing it, maximizing discounted future reward. That's what reinforcement learning hopes to achieve. And with Q learning, we use any policy to estimate the value of taking an action in a state. So off policy, forget policy. We move about the world and use the Bellman equation here on the bottom, to continuously update our estimate of how good a certain action is in a certain state. So we don't need this. This allows us to operate in a much larger state space and a much larger action space. We move about this world through simulation or in the real world, taking actions and updating our estimate of how good certain actions are over time. The new state at the left is the is the updated value. The old state is the starting value for the equation. And we update that old state estimation with the sum of the reward received by taking action s, tax, action A in state S, and the maximum reward that's possible to be received in the following states discounted. That update is decreased with the learning rate. The higher the learning rate, the more value we the faster we learn, the more value we assign to new information. That's simple. That's it. That's q learning. This simple update rule allows Us to explore the world and as we explore, get more and more information about what's good to do in this world. And there's always a balance in the various problem spaces we'll discuss. There's always a balance between and exploration and exploitation. As you form a better and better estimate of the Q function of what actions are good to take, you start to get a sense of what is the best action to take. But it's not a perfect sense. It's still an approximation. And so there's value of exploration. But the better and better your estimate becomes, the less and less exploration has a benefit. So usually you want to explore a lot in the beginning and, and less and less so towards the end. And when we finally release the system out into the world and wish it to operate its best, then we have it operate as a greedy system, always taking optimal action according to the Q to Q value function. And everything I'm talking about now is parameterized and our parameters that are very important for winning the deep traffic competition, which is using this very algorithm with a neural network at its core. So for a simple table representation of a Q function where the Y axis is state, four states s 1, 2, 3, 4, and the x axis is actions a 1, 2, 3, 4th, we can think of this table as randomly initiated or initiated, initialized in any kind of way that's not representative of actual reality. And as we move about this world and we take actions, we update this table with the Bellman equation shown up top. And here slides now are online. You can see a simple pseudocode algorithm of how to update it, of how to run this Bellman equation. And over time, the approximation becomes the optimal Q table. The problem is when that Q table becomes exponential in size. When we take in raw sensor information, as we do with cameras with deep crash or with deep traffic, it's taking the full grid space and taking that information, the raw, the raw grid pixels of deep traffic. And when you take the arcade games here, they're taking the raw pixels of the game, or when we take Go, the game of Go, when it's taking the units, the board, the raw state of the board as the input, the potential state space, the number of possible combinatorial variations of what states are possible, is extremely large, larger than we can certainly hold the memory and larger than we can ever be able to accurately approximate through the Bellman equation over time, through simulation, through the simple update of the Bellamy equation. So this is where deep reinforcement learning comes in. Neural networks are really good approximators. They're really good at exactly this task of learning the this kind of Q table. So as we started with supervised learning, where neural networks help us memorize patterns using supervised ground truth data, and we move to reinforcement learning that hopes to propagate outcomes to knowledge, deep learning allows us to do so on much larger state spaces, on much larger action spaces, which means it's generalizable, it's much more capable to deal with the raw stuff of sensory data, which means it's much more capable to deal with a broad variation of real world applications. And it does so because it's able to learn the representations. As we discussed on Monday, the understanding comes from converting the raw sensory information into, into simple useful information based on which the action in this particular state can be taken in the same exact way. So instead of the Q table, instead of this Q function, we plug in a neural network where the input is the state space, no matter how complex, and the output is a value for each of the actions that you could take. Input is the state, output is the value of the function. It's simple. This is Deep Q Network DQN. At the core of the success of DeepMind, a lot of the cool stuff you see about video games, DQN or variants of DQN are at play. This is what at first with a nature paper, deep mind, the success came of playing the different games, including Atari games. So how are these things trained? Very similar to supervised learning. The Bellman equation up top takes the reward and the discounted expected reward from future states. The loss function here for neural network. The neural network learns with a loss function. It takes the reward received at the current state. Does the forward pass through the neural network to estimate the value of the future state of the best action to take in the future state, and then subtracts that from the forward pass through the network for the current state in action. So you take the difference between what your q estimator, the neural network believes the value of the current state is and what it more likely is to be based on the value of the future states that are reachable based on the actions you can take. Here's the algorithm. Input is the state, output is the Q value for each action. Or in this diagram, input is the state in action and the output is the Q value. It's very similar architectures. So given a transition of S AR s prime s current state, taking an action, receiving a reward and achieving s prime state, the the update is do a feed forward pass through the network for the current state. Do a feed forward pass for each of the Possible actions taken in the next state. And that's how we compute the two parts of the loss function and update the weights using back propagation. Again, loss function back propagation is how the network is trained. This has actually been around for much longer than DeepMind. A few tricks made it really work. Experience replay is the biggest one. So as the games are played through simulation, or if it's a physical system as it acts in the world, it's actually collecting the observations into a library of experiences. And the training is performed by randomly sampling the library in the past, by randomly sampling the previous experiences in batches. So you're not always training on the natural continuous evolution of the system. You're training on randomly picked batches of those experiences. That's a huge, It's a, it's a, seems like a subtle trick, but it's a really important one. So the system doesn't over fit a particular evolution of the game of the simulation. Another important, again subtle trick. In a lot of deep learning approaches, the subtle tricks make all the difference is fixing the target network for the loss function. If you notice, you have to use the neural network, the single neural network, the DQN network, to estimate the value of the current state, an action pair, and the next. So you're using it multiple times. And as you perform that operation, you're updating the network, which means the target function inside that loss function is always changing. So the very nature of your loss function is changing all the time as you're learning. And that's a big problem for stability. That can create big problems for the learning process. So this little trick is to fix the network and only update it every, say, thousand steps. So as you train the network, the, the network that's used to compute the target function inside the loss function is fixed. It produces a more stable computation on the loss function so the ground doesn't shift under you as you're trying to find a minimal for the loss function. The loss function doesn't change in unpredictable, difficult to understand ways. And reward clipping, which is always true with systems that are operating, seeking to operate in a generalized way, is for these various games, the points are different. Some points are low, some points are high, some go positive and negative. And they're all normalized to a point where the good points or the positive points are a one and negative points are a negative one. That's reward clipping. Simplify the reward structure. And because a lot of the games are 30fps or 60fps and the actions are not, it's not valuable to take actions at such a high rate inside of these particularly Atari games that you only take an action every four steps while still taking in the frames as part of the temporal window to make decisions. Tricks but hopefully gives you a sense of the kind of things necessary for both seminal papers like this one and for the more important accomplishment of winning Deep Traffic is the tricks make all the difference here on the bottom is the circle is when the technique is used and the X when it's not looking at replay and target fixed target network and experience replay when both are used for the game of breakout. River Raid, Seaquest and Space Invaders. The higher the number the better it is, the more points achieved. So it gives you a sense that when replay and target both give significant improvements in the performance of the system order of magnitude improvements 2 orders of magnitude for breakout. And here is pseudocode of implementing DQN. The learning the key thing to notice and you can look through the slides is the. The. The loop. The while loop of playing through the games and selecting the actions to play is not part of the training. It's. It's part of the saving the observations. The the state action reward next state observations and saving them into replay memory into that library. And then you sample randomly from that replay memory to then train the network based on the loss function and with probability up top with the probability epsilon select a random action. That epsilon is the probability of exploration that decreases. That's something you'll see in Deep Traffic as well is the rate at which that exploration decreases over time through the training process. You want to explore a lot first and less and less over time. So this algorithm has been able to accomplish in 2015 and sense a lot of incredible things. Things that made the AI world think that we're onto something. That general AI is within reach. It's for the first time that raw sensory information was used to create a system that acts and makes sense of the world. Makes sense of the physics of the world enough to be able to succeed in it from very little information. But these games are trivial even though there is a lot of them. This DQN approach has been able to outperform a lot of the Atari games. That's what's been reported on outperform the human level performance. But again these games are trivial. What I think and perhaps biased. I'm biased. But one of the greatest accomplishments of of artificial intelligence in the last decade at least from the philosophical or the research perspective is AlphaGo Zero. First AlphaGo and then Alpha goes zero. It's deep mind system that Beat the best in the world in the game of Go. So what's the game of Go? It's simple, I won't get into the rules, but Basically it's a 19 by 19 board shown on the bottom of the slide for the bottom row of the table. For a board of 19 by 19, the number of legal game positions is 2 times 10 to the power of 170. It's a very large number of possible positions to consider at any one time. Especially the game evolves. The number of possible moves is huge, much larger than in chess. So that's why AI community thought that this game is not solvable until 2016 when AlphaGo used to use human expert position play to seed in a supervised way reinforcement learning approach. And I'll describe it in a little bit of detail in a couple of slides here. To beat the best in the world and then AlphaGo Zero, that is the accomplishment of the decade for me in AI is being able to play with no training data on human expert games and beat the best in the world in an extremely complex game. This is not Atari. This is a much higher order difficulty game and the quality of players that it's competing in is much higher. And it's able to extremely quickly here to achieve a rating that's better than AlphaGo and better than the different variants of AlphaGo and certainly better than the best of the Human players in 21 Days of Self play. So how does it work? All of these approaches, much like the previous ones, the traditional ones that are not based on deep learning, are using Monte Carlo tree search mcts, which is when you have such a large state space, you start at a board and you play and you choose moves with some exploitation, exploration, balancing, choosing to explore totally new positions or or to go deep on the positions you know are good until the bottom of the game is reached, until the final state is reached. And then you back propagate the quality of the choices you made leading to that position. And in that way you learn the value of board positions and play. That's been used by the most successful go playing engines before and alphago since. But you might be able to guess what's the difference with AlphaGo versus the previous approaches. They use the neural network as the intuition quote unquote to what are the good states, what are the good next board positions to explore? And the key things, again the tricks make all the difference. That made AlphaGo Zero work and work much better than AlphaGo is. First because there was no expert play instead of human games, AlphaGo used that very same Monte Carlo tree search algorithm MCTS to do an intelligent look ahead based on the neural network prediction. What are the good states to take? It checked that instead of human expert play, it checked how good indeed are those states. It's a simple look ahead action that does the ground truth, that does the target correction, that produces loss function. The second part is the multitask learning, or what's now called multitask learning is the network is is quote unquote two headed in the sense that first it outputs the probability of which move to take the obvious thing. And it's also producing a probability of winning. And there's a few ways to combine that information and continuously train both parts of the network depending on the choice taken. So you want to take the best choice in the short term and achieve the positions that are highest likelihood of winning for the player. That's whose turn it is. And another big step is that they updated from 2015. They updated the state of the art architecture which are now the architecture that won. ImageNet is residual networks resnet for ImageNet. That's it. And those little changes made all the difference. So that takes us to deep traffic and the 8 billion hours stuck in traffic, America's pastime. So we tried to simulate driving, that behavioral layer of driving. So not the immediate control, not the motion planning, but beyond that, on top of those control.