This is lecture 3 of course 6.S094: Deep Learning for Self-Driving Cars (2018 version). This class is free and open to everyone. It is an introduction to the practice of deep learning through the applied theme of building a self-driving car.

OUTLINE:
0:00 - AI Pipeline from Sensors to Action
8:25 - Reinforcement Learning
23:50 - Deep Reinforcement Learning
36:00 - AlphaGo
41:50 - DeepTraffic
54:35 - Conclusion

INFO:
Slides: http://bit.ly/2HcI7Ns
Website: https://deeplearning.mit.edu
GitHub: https://github.com/lexfridman/mit-deep-learning
Playlist: https://goo.gl/SLCb1y

CONNECT:
- If you enjoyed this video, please subscribe to this channel.
- AI Podcast: https://lexfridman.com/ai/
- Show your support: https://www.patreon.com/lexfridman
- LinkedIn: https://www.linkedin.com/in/lexfridman
- Twitter: https://twitter.com/lexfridman
- Facebook: https://www.facebook.com/lexfridman
- Instagram: https://www.instagram.com/lexfridman
- Slack: https://deep-mit-slack.herokuapp.com

LINKS:
Playlist: https://goo.gl/SLCb1y
Lecture 1: Deep Learning - https://youtu.be/-6INDaLcuJY
Lecture 2: Self-Driving Cars - https://youtu.be/_OCjqIgxwHw
Lecture 3: Deep Reinforcement Learning - https://youtu.be/MQ6pP65o7OM
Lecture 4: Computer Vision - https://youtu.be/CLOAswsxudo
Lecture 5: Deep Learning for Human Sensing - https://youtu.be/Z2GfE8pLyxc

Guest talk: Sacha Arnoud, Waymo - https://youtu.be/LSX3qdy0dFg
Guest talk: Emilio Frazolli, nuTonomy - https://youtu.be/dWSbItd0HEA
Guest talk: Sterling Anderson, Aurora - https://youtu.be/HKBhP9JISF0

2017:
Guest talk: Sertac Karaman, MIT - https://youtu.be/0fLSf3NO0-s
Guest talk: Chris Gerdes, Stanford - https://youtu.be/LDprUza7yT4

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 an artificial intelligence system needs to accomplish.

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 build a taxonomy, a library of knowledge.

An agent is tasked to reason, to aggregate, to connect pieces of data as 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 deeper enforcement 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.

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 IMU.

The raw sensory data is then processed, features are formed, representations are formed, and multiple higher and higher order representations.

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 tasks The generative tasks and the unsupervised clustering tasks through machine learning.

That's what we talked about a little in lecture 1 and will continue tomorrow and Wednesday.

And you can think about the output of those networks as simple, clean, useful, valuable information.

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 the 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 in machine learning over the past 3 decades has been.

Mapping from raw sensory data to knowledge.

That's where The success, the automated representation 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 do, 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.

So today let's talk about reinforcement 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 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 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 devolves through time in some, some sort of predictable way to take sparse information and generalize it over the entirety of the experience that's being learned.

Today we'll talk about deep traffic As a method, as a way to introduce deeper enforcement 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 with a neural 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.

The competition is hosted on the website selfdrivingcars.mit.edu slash deeptraffic.

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 1 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 their reward.

And 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 is 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 their 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 1 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 in 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.

There's a state as 0, action A0, and reward received.

Again, action reward state, action reward state.

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 A 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 3x4, 12 squares.

We start at the bottom left and they're tasked with walking about this world to maximize reward.

The reward at the top right is a plus 1 and a 1 square below that is a negative 1.

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 a 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 0.1 you go right.

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, our reward is a negative 2.

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 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 is increases the reward Then there's a significant incentive to 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.

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 in a much larger action space.

We move about this world or 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 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, 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.

The 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 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.

But the better and better your estimate becomes, the less and less exploration has a benefit.

So usually want to explore a lot in the beginning 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 the optimal action according to the Q-value function.

And everything I'm talking about now is parametrized 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, 4 states S1,2,3,4 and the X axis is actions A1,2,3,4 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 a 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 it becomes exponential in size.

When we take in raw sensory 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 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 as 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 Bellman 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 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.

It's much more capable to deal with the raw stuff of sensory data, which means it's much more capable to deal with the 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 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.

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, DeepMind, the success came of playing the different games, including Atari games.

The Bellman equation up top, it 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 a forward pass through a 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.

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.

So given a transition of SAR, S' S current state taking an action receiving a reward and achieving S' state The update is Do a feedforward pass to the network for the current state.

Do a feedforward pass for each of the possible actions taken in the next state.

And that's how we compute the 2 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.

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 seems like a subtle trick, but it's a really important 1 So the system doesn't overfit a particular evolution of the game of the simulation Another important, again, subtle trick As 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 GQN network, to estimate the value of the current state and action pair and the next.

And as you perform that operation, you're updating the network.

Which means the target function inside that loss function is always changing.

So you're, 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 to 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 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 general 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 1 and negative points are a negative 1.

And because a lot of the games are 30 FPS or 60 FPS and the actions are not, it's not valuable to take actions at such a high rate inside of these particular Atari games that you only take an action every 4 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 1 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.

Fixed target network and experience replay.

When both are used for the game of breakout, river raid, sea quest and space invaders, The higher the number, the better it is.

So when it gives you a sense that when replay and target both give significant improvements in the performance of the system.

And here is pseudocode of implementing DQN.

The key thing to notice, and you can look through the slides, is the loop, the while loop of playing through the games and selecting the actions to play, is not part of the training.

It's part of the saving the observations, 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 since a lot of incredible things.

Things that made the AI world think that we were onto something.

It's for the first time that raw sensor 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.

This DQN approach has been able to outperform a lot of the Atari games.

What I think, and perhaps biased, I'm biased, but 1 of the greatest accomplishments of artificial intelligence in the last decade, at least from the philosophical or the research perspective, is AlphaGo 0.

It's deep mind system that beat the best in the world in the game of Go.

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 1 time, especially the game evolves.

So that's why AI community thought that this game is not solvable.

Until 2016, When AlphaGo used 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.

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 a much higher order difficulty game and the quality of players that is competing in is much higher.

See all Lex Fridman transcripts on Youtube

MIT 6.S094: Deep Reinforcement Learning