Skip to main content
Loading Explore guides…
Deep Reinforcement Learning · Acedra
Home
Explore
Computer Science
Deep Reinforcement Learning
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
211 segments
Copy
Hide video
0:05
Welcome to our fifth lecture in person for Stanford deep learning CS230. Um today's lecture is going to be about deep reinforcement learning. I actually switched uh the original plan of talking about neural network interpretability and LLM visualization simply because you you haven't had the chance to study attention maps, you know, convolutional neural networks and so it would have been an overkill to do that week five. So we're going to talk about neural network interpretability
0:38
and visualization in a later lecture actually. Um but today our focus will be on deep reinforcement learning uh which is probably my favorite lecture of uh the class. I I feel like I say that every week but it's okay. I like it. Um the agenda is pretty packed. We're going to start with uh deep reinforcement learning which you can think of as the marriage between deep learning and reinforcement learning. Together the baby is called deep reinforcement learning. and we're going to see how
1:12
reinforcement learning works and how neural networks can play a part in building a reinforcement learning um agent. Um in the second half of the class we will focus on a very specific um you know concept called reinforcement learning from human feedback that you might have heard of. It's one of the core concept that really made the difference between what you might have remembered as GPT2 and chat GPT. You know, that's the leap. Uh that's really the the the technique
1:52
that had uh that has you know democratized um access to LLM because of the performance improvements and the alignment with humans. So, we're going to see what what is this concept of R LHF and how um does it work and why does it allow us to align a language model to human preferences. Ready to go? As always, let's try to make it interactive. So, the motivation behind deep reinforcement learning and as usual, you're going to have all the most important papers that are covered in the
2:26
class listed at the bottom of each slide. Um reinforcement learning has grown in popularity. Um one of uh uh the you know very popular papers called human level control through deep reinforcement learning is the work um from deep mind um has showed us that a single algorithm/training method can allow us to train AI that can play many many Atari games better than humans. single algorithm over 40 50 games where it exceeds human capability which is quite impressive when you
3:08
thought about the fact that you know machine learning used to be niche and you would have to train a really niche algorithm to perform different task here's an algorithm that can just learn sort of every Atari game a little later you might have heard of Alpho Alph Go is a is an algorithm that was developed to beat and exceed human performance performance in the game of Go. We'll talk about it a little more. The game of Go is a very complex game. Some would
3:36
argue way more complex than chess from a decision-m standpoint and from the possibilities that can happen on the board. And so, um, it it actually got solved, um, in 2017 again by the Deep M Deep Mind team and and David Silver's lab um, later on. And again another great paper from deep mind had showed us that reinforcement learning can also be used for strategy game that might be a touch more complex than chess or go that might actually involve multiple players
4:15
playing with each other or against each other. Some of you might have played Starcraft for example. That's an example of a game where um it requires a lot of long long-term thinking, short-term thinking. Another one is, you know, Dota. Some of you might have played Dota or League of Legend where you have a team playing against another team. Those are examples of games that involve multiple agents playing collaboratively. And it's pretty hard to develop systems
4:40
that can play with each other against multiple opponents. Um and finally most recently this is 2022 so alongside the release of Chad GPT um this paper that introduces the concept of reinforcement learning with human feedback applied to aligning language models with human preferences and we'll talk about that later. So all all this to say that reinforcement learning allowed um us to exceed human performance in a variety of tasks. The first one um I want us to think about is the the game of go. So
5:16
let's say that you were asked to solve the game of go with classic supervised learning. Okay, everything we've seen together so far labeled data. How would you solve the game of go with classic supervised learning? What data would you collect? What would be the label etc.
5:45
Yes.
5:54
>> Okay, good point. You look at history of plenty of games, hopefully from good players if you want the the algorithm to work. Um, and you look at X as the input being the current state of the board and Y as the next state of the board. And this would tell you what move was selected and you learn the move essentially. And hopefully if you do that across many many games, you know, you might you might see the the agent become more attuned to the game and and and develop better strategies. So, you
6:28
know, really hopefully it's a professional player. What are the disadvantages of that or the shortcomings that you can anticipate? >> Yes.
6:50
>> Yeah. Yeah. Great point. You might not see the entire space of possible states of the board, which is what you said. So you might miss out on a lot of different strategies. So the game of go is actually a game with two players. One player that uses the black stones and one player that uses the white stones. And iteratively they're going to place those stones on the grid, a 13 by13 grid that you can see on screen with the goal of surrounding their opponent. So you're
7:21
constantly trying to surround the stones of the opponent and the opponent is trying to surround your stones. And so you can imagine that for every intersection on the grid there is multiple possibilities. Either there's a black stone or a white stone or nothing. And on a 13 by13 grid you can imagine how many possibilities of a board state there are. It's um impossible to capture all of that with historical moves from professional players. It would just never cover that. The same thing could
7:52
be said in chess as well. you you know that even the professional players can plan X number of steps in advance but nobody knows where the game takes you and in the late stages of the games or the end games players always find themselves playing a different game and that's part of the magic of being good at chess. Um so yeah that's the problem. What's another problem or shortcoming beyond the fact that we can't observe possibly all the states?
8:21
Yes.
8:34
>> Correct. Correct. You, if I repeat what you said, well, first, you don't even know if this was a good move, you know? So, maybe it was not even a good move and you're learning something that was not a good move and you're labeling it as a good move. And second, um, you're actually only getting partial information, meaning you don't have the information of what's in the person's mind and what strategy they're trying to execute. So your store, you're sort of looking at a single example among a
9:00
long-term strategy and you can't expect the model to guess what's the long-term strategy because it was just trained on X and Y and matching the inputs to a possible output. So you you don't really have any concept of a strategy at that point. it looks one off at every decisions of the model. Okay, those are really good points. Um the other one is the ground truth might be illdefined. What I mean by that is um even the best humans in the world do not play their best game every day and even
9:37
their best game is not the ground truth. And that creates an issue because you're essentially training against a target that is off by a certain margin. You're never going to get better than the best human and the best human is not the best possible um existing the best possible strategy at every point. So you could argue what if we get a panel of experts that we're monitoring and those are the best players in the world. Even with a panel of expert that decides every move,
10:05
you're still have an illdefined ground truth, you know. So that's a big issue. Too many states in the game you mentioned and we will likely not generalize which is what you said meaning we're looking at one-off situations. We're not looking at entire strategies and so when we face a board state that we've never seen before because the model was not trained on strategy it sort of we get stuck. Yeah. Okay. And this is an example of a perfect application for reinforcement
10:36
learning because reinforcement learning is all about delayed labels and making sequences of good decisions. So if you had to remember in one sentence what's RL RL is making good sequences of decisions, sequences of good decisions, sorry.
11:01
and do that automatically. Another way to look at it is the difference between you know classic supervised learning and RL is in uh in classic supervised learning you teach by example. In reinforcement learning you teach by experience which is also a different concept. You're not just showing cats and non-cats to a model. You're actually letting the model experience an environment until it figures out what were the best decision it made and learns from them.
11:37
Some examples of reinforcement learning applications I'm going to mention them. We we have we have gaming of course that we already covered. What are other applications of AI where we need good sequences of decisions? Yes. autonomous driving. Yeah, correct. I mean, in driving, you could argue RL could work and there's some RL going on, but what you mean, I think, is you you have some sort of a dynamic planning algorithm that allows you to strategize. If you see a a red light ahead, you
12:12
might start slowing down over time, but maybe it will turn green, so you might not slow down completely. This is an example of a strategy that you need, of course. >> Yeah. robotic controlling. That's a great example also related to autonomous driving. But imagine you uh want to teach to a robot to move from point A to point B. The number of good decisions that the robot needs to make in terms of moving each of their joints is tremendous. Like it's actually super
12:43
unlikely that a robot would move from A to B if it's not trained to make good sequences of decisions. What else? Actually, the biggest one nobody mentioned yet. >> It's not a great application. I don't like it, but it happens to be the biggest one over enforcement learning. Yeah. >> Yeah. Yeah. Yeah. Advertisement. Yeah. Marketing. You're right. So, yeah, we talked about robotics. Advertisement is another example. Um, advertisement is a long game. Like companies are
13:26
showing you multiple ads before you buy. And in fact, the reason rein reinforcement learning is important is because, you know, they're planning a strategy that might lead a buyer to execute a purchase over time and it requires long-term thinking. So there's a lot of reinforcement learning applied to marketing, advertisement, real time bidding processes etc. Okay, clear on what RL is and how it differs from classic supervised learning? No. Okay. Um, so let's put some
14:01
vocabulary around that concept. In reinforcement learning, you have an agent and the agent interacts with an environment. As the agent interacts with the environment, the agent will perform certain actions that we will denote a t where t is a time step. And the environment will show you states that transition from time step t to time step t + one. So subject to an action at an environment may transition from a st to st plus one. You can think of the game of go. I take the action of putting my
14:40
black stone on a certain grid intersection and the environment has changed. It moved from the state has changed. It moved from state time step t to time step t + one where my stone is on the grid. After that um state update happens, there's two things that the agent observes. the the the agent observes an observation that we will note OT and a reward RT.
15:09
Okay, so those are the vocabulary words and of course the goal of the agent will be to maximize the rewards.
15:18
One thing to know about the observation, we'll talk about it a little more. Um the observation sometimes is equal to the state. Can someone guess why we might need two concepts instead of a single concept? Why is it important to have a state and an observation? >> Yes. >> Yes. Correct. So in some cases the environment may not be fully um you know transparent to the user and so for example in chess or in go the observation is actually equal to the state you see everything on your board
15:57
all the information is available to you if you play League of Legends or Starcraft you know the concept of you know I think in English it's called like a cloud or a fog I think it's a fog you only see certain part of the map until you have explored everything or until your friends are sort of visiting the other parts of the map. And so the observation is actually less information than the states of the environment. Okay. And then the last piece of vocabulary is a transition. When I refer
16:28
to a transition, I refer of the process of getting from state T plus one, which means we're in state T. The agent takes an action A. It observes OT and a reward RT and it transition to the next state ST plus one. Question.
16:55
Uh wait what do you mean? You mean is there are there examples of environment where the state is so large that the entire
17:08
>> Yeah. Possibly for computational reasons. Yeah. Yeah. You might have games. I mean, look at open world games. Like truly, you could you could argue, I don't know, there are some games where you might press start and you see the entire environment, but who cares of what's happening 20,000 kilometers west of you if you're in a certain location. That might not influence your strategy. So you might actually put some sort of a you know trust circle or like some sort
17:37
of a circle in which you observe which you think has 99% of the information you need possibly for computational reasons. That's a good point. Okay, let's get to a practical example of a reinforcement learning algorithm and develop it together. This example is called recycling is good because recycling is good but also because it's a simple example illustrative of reinforcement learning. So let's say we have a a small environment with uh five states. There is a starting state marked in brown
18:11
which is state two. It's our it's our initial state. And then on the right side, sorry, on the left side, you have state one, which is a garbage. And it's great to get to the garbage because you're going to be able to recite to to put in the garbage the, you know, the stuff that you have in your hands. You know, you're trying to throw away some garbage and the garbage can happens to be there and so we would expect there to be a reward. On the other side, if you
18:41
actually go to the right, you might pass by state three, which is empty. You might pass by stage four where there is a chocolate uh packaging that is left on the ground that you can pick up and it's good to pick it up. And then on stage five, state five, you have the recycle bean which is more valuable than the garbage can because you can recycle and you should get better rewards for that. So that's our game. In this game, we define a reward that is associated with
19:11
the type of behaviors that we want the agents to learn. Um, and the reward is as followed. That's just one example. Plus two for throwing your garbage in the normal can, plus one for picking up the chocolate packaging, and plus 10 if you manage to make it to the recycle bin. Is it clear? Now, the goal will be, and that's the case in reinforcement learning often time to maximize the return. We'll define formally the return but think about it as maximize the amount of
19:45
rewards that you get as you go through this journey and you make your decisions. In this specific game, we have five states and there's three types of state. In brown is the initial states. We have normal states and we have in blue terminal states. When you get to a terminal states in reinforcement learning, it will typically end the game. it will end one episode of the game. You move to another episode. You'll get back to the starting state or initial state and you'll redo another episode.
20:18
The possible actions for our agent here are going to be fairly simple. Left and right. And we're going to add an additional rule that is important, which is that the garbage collector comes in 3 minutes and it takes a minute to get from one state to the other. Why is that an important rule to add to the game? Can you guess? Yeah. >> Yeah. Otherwise, you just go back and forth between uh stage three and stage four. You just collect a bunch of chocolate packaging and you never make
20:54
it to the bin. And so, it's not what we want. Yeah. Okay. So, how do we define the long-term return? The long-term return is going to be defined as capital R, which is the sum of rewards with a discount. Discount is a very important concept in reinforcement learning. It's also a very natural concept to think about. Can you think of what what the discount would represent in for humans? Do you have an example of what it could be? Yeah. >> Huh? money. >> Yeah. The value of money and time.
21:35
Exactly. Or the energy that a robot might have, things like that. Yeah. You you would rather get, you know, a dollar now than a dollar in 10 years knowing that there's some inflation, for example. That's the example of a discount. In reinforcement learning is the same. You know, let's say you have a strategy that takes so much time. You need to discount it because your robot might lose energy as you're going through it. For example, these counts can vary, you know, but they stay
22:02
between zero and one. Um, so what is the best strategy to follow if gamma the discount is equal to one meaning you know time doesn't matter here if it's longer or shorter just want to maximize the return. Best strategy to follow.
22:27
Let's give it a try. Someone who hasn't spoken yet.
22:41
>> Yes.
22:47
>> Bounce around. But remember the rule of uh 3 minutes. You can't bounce around because you you will not get to the terminal state before the time allotted is done. But that would be a good idea if this rule was not true. What else could you do?
23:12
The idea? It's an easy one. No, it's not too hard.
23:19
best strategy for gamma equals 1 and give me also the maximum reward you would get.
23:30
People are are sleepy today. Yeah. >> Recycle. >> Go to the recycle. So, right, right, right. >> Yeah, that's right. Thank you. Right, right, right. And then what's your Sorry. What's your um what's your total reward? Yeah, that's right. 11. So that's where we get terminal state and we grab our reward of 11. Very good. Now assuming 0.9 for gamma. We're going to complexify things a little bit. I'm going to walk you through a very simple algorithm that you know allows us to sort of determine
24:08
the best strategy and we will put our numbers in a matrix. So for instance um we'll define a Q table and Q stands you know is a it's a it's a value function um where the the the name Q-learning Q star you might have heard um all of these things come from Q-learning and so let's say we have a Q table which has uh the size of number of states times number of actions so five rows two columns in our Every entry of the Q table is essentially representing how good it is to take action A in state B.
24:55
Do you agree that if we had a table with these numbers essentially we solve the problem meaning at any point the agent can just look in the table I am in state three let's look at column one that would tell me the value of action one and let's do that column two it would tell me the value of action two so I have everything I need to make my decisions so that table is really the the thing you want to find in this exercise now the way we will find the table is sort
25:26
of using a backtracking algorithm where we might actually codify the environment as a tree and traverse the tree. So here's what it looks like. I start in S2 and I have two options ahead of me. I can go to the left where I will get a reward of two. It's an immediate reward. The immediate reward is not discounted. It's an immediate reward. Remember the the formula for R. The immediate reward R0 is not discounted. That would take me to S1. It's a terminal state, so there's nothing to do after.
26:02
Second option, I go to the right and I get a reward of zero. That's my immediate reward. And I end up in state three. State three is not a terminal state. So I can go and do the same exercise from state three. In state three, I have two options. I can go to the left where I would see a reward of zero and I will end up in S2 or I will go to the right and I will get an immediate reward of plus one. It's an immediate reward. We're not discounting it. I will end up in S4 and from S4
26:32
again I have two options. Back to the left to S3 with zero reward or to the right with the amazing reward of plus 10 and the terminal state of S5. So that's my map of immediate rewards. That's not my discounted return. So what we're going to do now is we're going to backtrack up the tree in order to compute the discounted returns. Actually, if I'm in S3 right here, I see that I can get an immediate reward in S4 of one. And I want to compute my maximum return that I can get from when
27:13
I'm in S3. My maximum return is that in S4 I could get a plus 10, right? But I need to discount that. My discount is 0.9. So I multiply 10 by 0.9. What it tells me is that from S4 I can expect nine plus one, which I get as an immediate reward from moving from S3 to S4, I can update this number to 10. Meaning from S3 the best you can hope for is a discounted return of 10 which is 1 plus 0.9* 10. Everyone follows. Now let's do the same exercise one step before in S2. uh you know um in S2 um I
27:56
have um an immediate reward of zero for going to S3 or an immediate reward of two for going to S1. Um S1 is not going to be worth it. We already know that because when I'm in S3 I can actually expect 10 which I have to discount. 0.9 * 10 gives me 9 plus 0 immediate reward from S2 to S3. That tells me that the discounted return from state two which is our initial state is nine. Good follow just a simple backtracking. Now I can copy back this. So S3, I know that when I'm in S3, um uh you know, I
28:40
can expect zero immediate reward to um uh to sorry, if I if I'm if I'm in S2, I can expect uh zero immediate reward plus a discount times the plus 9 that I could expect in S3. And so that gives me values that should cover everything that we have in this Q table. So I I do that backtracking. I copy paste all of that into my Q table all the way up here. And this is what I get. We essentially finish the game at this point. We um can look uh at a certain row. So let's say I'm in state number
29:23
three. I look on the third row of that Q table and I see that I have two options. If I go back to S2, ultimately my discounted return will be 8.1, right? If I actually go to S4 on the right, I will get 10 because I will get 1 + 0.9 * 10, which is 10. So this is a toy example, but it tells you that if you were able to backtrack through the entire environment, you will be able to build a massive Q table and you will be able to give it to your agent to make its decisions. >> Yeah.
30:06
>> Sorry, can you repeat? >> Yeah, here I'm simplifying. I'm not considering the time uh remaining. But in practice um you if if I remove the time component so I remove the fact that there's a three minute deadline before the garbage collector comes then uh this would uh be slightly more difficult because you would have to do a time series essentially of adding the discount times the reward that you collect. Yeah, but I'm simplifying here and that's why I use the three-minut rule. [Music]
30:39
Any question on the Q table? Super. Okay. So, uh this was the Q table and in fact we can put together our strategy for gamma equals 0.9. The best strategy is still the same. You go to the right and you can expect a return of 9. Now, one of the most important concepts in reinforcement learning is this equation on the board called the Bellman optimality equation. Often time you'll see it noted as Q star of state S and action A equals R + gamma time the max of that
31:26
same function applied to S prime A prime. Let me explain this equation for you because it's super important. This equation is called the optimality equation because your optimal Q table will follow this equation. If you have finished the game, this equation can be applied to any state action pair and it will still be true. The intuition behind why the Bellman equation is the optimality equation is that um if you're in a if you have the perfect Q function Q table um and you're
32:05
in a certain state and you perform a certain action A you will observe a reward and this reward will uh you know you you have taken an action so you would be in a new state and from that new state you can repeat what you just did right and because uh you've done the backtracking and stuff like that, you will uh get this equation to be true because it's the reward plus discount times the best next action that you could be taking.
32:36
Does that make sense? Any question on that? That's exactly the backtracking that we did by the way. immediate reward plus discount times the best possible action that you can take in the next state s prime.
32:56
The last concept I cover in terms of vocabulary is the policy. The policy is the function that given your state is going to tell you what to do. And in Q-learning the way this policy is defined is argmax of Qstar um across the action. So essentially what it says is like look in the table and look at a certain state s you want the policy which is what you should do. It's the function that tells you our best strategy. You just look at the two possible actions which one has the
33:28
highest Q value and select that action. That's it.
33:37
This is a very simple example but it it's the core of um Q-learning that you know later on you will use policies widely. There's a lot of reinforcement learning algorithms but this concept of understanding the policies the function telling us our best strategy in Q-learning it's the argmax of the best Q value in the given state. It tells you which action to take that's the core thing you need to understand. So remember this belman equation because we're going to reuse it
34:06
in a bit. The main issue um with this approach um of a Q table is that state and action spaces can be super large and having a matrix that you discover through backtracking um and where every time you want to do an action you have to look up the given state the possible action it becomes impossible. Like imagine you using this algorithm for the game of go where there's so many states, there's so many possible actions, you can put your stone anywhere on the board. You can imagine
34:45
how big this matrix becomes and how impossible it is to use. So that's our problem and that's the moment where deep learning comes into play. So let's look at it. uh the the the oh actually before I go there I'm just going to cover some vocabulary. We said the environment, the agent, the state, the action, the reward, the total return and the discount factor. We learned all of that. We saw that the Q table is the matrix of entries representing how good is it to
35:15
take action A in state S. And the policy is the function that tells us what's the best strategy to adopt. And the bellman equation is satisfied by the optimal Q table.
35:29
So let's get to deep Q-learning which is what I was about to say is we are going to frame the problem slightly differently. So instead of using a Q table, we're going to use the fact that neural networks are universal function approximators and we're going to define a Q function that's essentially a neural network. So that the function can take a state S and an action A and tell you how good that action is in state S. So instead of a lookup in a matrix, you just run a forward pass in a neural
36:04
network and it gives you the answer. That feels like a better solution for games where there's a lot of states and a lot of actions. So here is a same problem statement. In the past we looked for a Q table and this time we will look for a neural network. One of the things we're going to do is to define the output layer to have two outputs. So given a certain state as input think about it as a one hot vector encoding the state. So this one is the example of state two 0 1 0 0
36:36
0. If you pass state two in this Q function with multiple layers, it will give you two outputs. One output that corresponds to Q of S action right and the other one Q of S action left because it's the two actions. If we had more actions to take, we would just increase the output layer and we might have many more neurons in the output layer.
37:07
So the big question is how the hell are we going to train that network? Because we're not in classic supervised learning. We don't have labels.
37:20
So this one is a hard question but u what do you what would you do given we we don't have traditional x and y pairs how are you going to train this neural network because remember at the beginning this neural network will give you garbage it will take a state s and it might tell you go to the left or to the right but it's completely random so how are you going to tune it to the level where it makes really Good decisions.
37:53
Yes.
37:58
>> Assume based on some prior knowledge. Tell me more. What?
38:09
>> So what are the things we know about this problem right now? What are the the the rules of the game that we could use in order to I'm I'm seeing what you say. You say we could estimate what good looks like but based on what?
38:32
>> Okay. So reward structure you're saying that's one thing we have in every game. We have a reward structure for every state that definitely should be used in order to estimate the good what a good decision looks like. Yeah. The problem is not in every state you will see a reward. And if you look at many games of like go you might not see a reward until 50 moves. >> So what do you do in this case? >> Yes. Can we run through a bunch of actions and space and see what the
39:05
output is and get more data? >> Yeah. So you could you're actually um bringing up a sort of a tree search, right? You go down the tree, you do every possible action and then you backtrack. >> Not every possible action. >> So which actions? >> Trying to spread it out of the >> Okay, that's that's we're getting there. So first possibility is we just go down the tree in the game of go. You could put your stone everywhere. So the tree already start by a 13 by3 options and
39:36
then it's exponentially grows impossible. It's intractable. But what you said is what if there are certain actions that are more likely than others? Do we need actually to explore the entire tree? What's this like? What are you using when you're saying that? How do you determine what action might be better than another one? >> Expected return. And we're getting close. Yeah. But you know, how do you know the expected return without going through the tree once? At least >> you can estimate both.
40:05
>> Okay. You can estimate it using what?
40:10
>> Yeah, maybe. Yeah. What? What? So that's exactly what we're going to do actually. But we're going to use the the Bellman equation because there are two things we know about this problem. We know the reward structure which you brought up and we also know that the perfect Q function will follow the Bellman equation that we know as well. At the end the Bellman equation should be respected meaning for every state if you want to know the Q value of that state given an action. The way you will get
40:42
that is you will look at the immediate reward plus the discount times the best Q value from the next state across all actions. that equation will be respected. So those are the only information we have and we're going to use them drastically to define our labels and sort of mimic a classic supervised learning approach. So here's what we have. We have our neural network. We have Q S to the left and QS to the right that represent how good it is to go to the left in that state
41:10
versus the right. And then I've pasted the Bman equation on top right of the screen. We're going to define a loss function. So let's say for the sake of simplicity because those are scalar values that will use you know L2 loss quadratic loss that compares a certain label Y to um a certain Q value of a state and a certain action. So what we would like is to minimize this loss function meaning Y and the Q value for a given action in a given state is as close as possible to each other. and
41:48
we're going to leverage the reward and the Bman equation. So let's do um two things. Right now we don't have a Y. So in supervised learning you will have a picture of a cat. There's a cat. The Y is one or zero. Here we don't have a Y. So we have to come up with an estimate of a good Y at least better than random. So let's say at this point in time when I send a state S in the network, it turns out that Q of going to the left is higher than Q of going to the right.
42:20
Which means that today at that moment the Q function tells me it's better to go to the left than to go to the right. That is random at the beginning. It's completely random. Right? So what I'm going to do is I'm going to use as my target value Y the immediate reward that I observe on the left plus gamma times the best Q value that I can get. So the best action that I could take in the next step based on my current Q value.
42:58
That's very important. So remember this target is off. It's not a perfect target, but it's better than nothing. Meaning, not only it tells us, hey, there is a good reward to the left. We should consider that in saying that that might be a good move because we're seeing an immediate reward. But on top of that, we also know that at the end of training, the Q value should follow the Bellman equation. So why don't we set the target as the Bellman equation? So we add the discounted maximum future
43:30
reward when you are in the next state. So you were in state S. You go to the left now you're in state S next left and you look again at your Q values and you select the best one. Then you add that number here. So there is actually two forward path in that process. Right? There's one forward path where you send the state S in Q and you look at the two options left or right and you're like okay I'm going to the left and then you're like I'm going to compare that value to a target Y but to get that
44:06
target Y I need to do another forward path. So I take my action left I perform it I get an S prime state s next and I send that S next into the Q network. I look at the two options I have. I pick the best one and I add it here with a discount. So fundamentally what's happening is is the following is we have a Q network that's random at the beginning. It has never observed the rewards. We just know that at some point it will get to the Q um it will get to a perfect you know
44:42
policy. It will get to a perfect Q function. But the best we can do right now is to say as a guide to for our agent, we will look at the immediate reward and we will look at the Bellman equation which should tell us a better estimate than where we are right now and we will try to catch up to that estimate and then we do that again and again. So remember every time your Q gets better it gets better for the next state as well. So you know the Bellman equation tells you estimate it with the second
45:13
forward path and you just keep getting better and better as you're observing more rewards.
45:30
left and >> uh how would it so describe the loop you >> imag
45:44
>> for going to a right you again need the target >> yeah you would stop at that point so what you yeah this is a good question I I'll show you how we fix certain things but you do only one step meaning you have your Q value at this point and it tells you go to the left and you just want to target Y. So what you do is you put left and you look at your next state. You forward propagate your next state. You look at the two options. You pick the best. You don't go further. You
46:12
just use that one step. You look one step ahead essentially. You don't look multiple steps ahead. You could, but it would be more computationally heavy to do one more step again and so on. So yeah. Yeah. >> Yeah. It seems like you're learning the function locally like most
46:37
people know like how fast that
46:44
>> it will typically be a function of the environment the state space um how long it will take to converge but you're perfectly right that um as the Q function gets better, the estimate Y also gets better. So the two things get better together, right? Because the Y is based on the Q function. And if the state space is massive, you might have a very difficult time training this model. There's better approaches that we'll see later. Yeah, correct. There was a question there.
47:23
>> Yeah. So here I'm just saying let's say when you send state S in Q the left happens to be higher than right. But the same happens on the other side. Let's say let's say the left is worse than right. Then what you will do is you will define your target Y as the reward that you observe on the right plus from the next state of having gone to the right what's the best action and what's the Q value for that pair and then it will give you the target for that scenario.
47:55
So one complication with this training is that when you want to differentiate L. So you want to perform a back propagation. You want to take the derivative of L with respect of the parameters of the network. You want Y to be a fixed thing, right? Because in supervised learning Y is not differentiable. It's just a fixed number zero or one or a certain number. So here we're going to simplify and we're going to say this term that is dependent on the Q network. So technically this term
48:21
has parameters. So if you actually differentiate it, it will give you a value. We'll just hold it um fixed. So we say we do use our Q network to perform an estimate of our Y but we will not differentiate it. We will say it's not it's fixed. Yeah. >> Can you explain why we discount this? >> Yeah. >> Because you know going back to the reason we discount is like the value of time. It's like you probably want to say if you can win the game in 10 moves, win it in 10 moves rather than 100 moves. Um
48:56
or if you can get $1 today, get $1 today rather than in 10 years. All of that is why we have a discount here. And the discount is a is a hyperparameter that you would define as well. That would influence the strategy of your agent. >> Once more pass. >> We're going to see it after. Actually, I'm going to do a concrete example because it's a little complicated. Yeah. Yeah. >> Q. >> No, no, that that was it's a good point. It's not that. It's just Q of it's it's
49:29
a 2 by two. It's a one by two. So you have left and right. I was just going down the first case. So I put the state left. Yeah. Yep.
49:44
>> What if the rewards are not fixed? I mean, in most games we're going to see right now, the rewards are going to be fixed by the designer of the game, the human that's designing the game. Um, in practice, you could have a separate function that um actually comes up with the reward. We're going to see an example later in the lecture where the reward might be different in different scenarios and there's a function or sometimes called a critic that determines what's the reward in a certain state.
50:12
Okay, this is yeah one last question and then we move because we we're going to see a concrete example is going to be clear. >> Um so when we like hold it fix for laptop is that what differentiates this from iterating through all of the like possible >> Yeah. Yeah. So instead of doing the backtracking down the tree and going over everything, we're saying we're going to limit oursel to just picking the best action based on our current understanding of the network.
50:42
You see, like my network is kind of intelligent, not great. We're in the middle of training. It says that I should go to the left and then if I look at the next state when I'm in the left, it says I should go to the right. I will trust it because it's the best I have, best estimate I have, but I will discount that. And then if you keep repeating that, it turns out that not only your estimate gets better, but your model gets trained and then ultimately both together get to an optimality equation.
51:10
So it's a it's a funky concept, right? But you get it. We're going to see examples. Um, okay. So uh then once you have been able to use the Belman equation to estimate your targets, you perform classic back propagation and you update the parameters of the network and you repeat that process. Okay. Uh here is concretely if you were to code it in pseudo code, here is what it would look like to train a NRL agent using Q-learning. We start by initializing our Q network parameters.
51:51
So initialization, it's random at first. Then we will loop over episode. As a reminder, episodes are one full game from start to terminal state. Um within an episode, we're going to start from the initial state s and we're going to loop over time steps until we reach a terminal state. So within one time step, here's what we will do. We forward propagate the state s in the Q network. We will execute the action A that has the maximum Q value. We will observe a reward and we will
52:28
also observe a next state S prime. We will use that S prime to compute our target Y by forward propagating S prime in the Q network and then computing our loss function. And based on that we will use gradient descent to update the parameters of the network should be simpler looked at like that right okay so this is the vanilla Q-learning so to summarize again the one the main difference is that we don't have a target and we use our own network to estimate the target and the rewards are
53:05
what's going to help us get better over
53:13
By the way, it's okay if you don't understand everything. This is an entire class at Stanford. Um, you know, an entire quarter of studying that type of stuff. So, we're trying to get the basics within an hour and a half, two hours. Okay, let's go a little further now together um and apply that to an actual game. So, here's the game. It's called Breakout. We want to destroy all the bricks. Who has played Breakout in the past? Buddy, a few. Okay, good. So, you have a a
53:43
paddle that you control and you're trying to destroy the bricks. If the ball gets past your paddle, you lost. And if the bricks are all destroyed, you won. That's it. Let's do it together. What um what is the input of our Q network? What would you use as input to remember? Yeah.
54:15
Yes. >> Entire screen. Okay. Let's do that. So I take I define that as the state S which is the input to my Q network. Uh what's the output of the Q network? >> Yes. >> Do we have to do that on screen? >> Good question. We'll get there. I'm I'm gonna ask you, but do we have to look at the full screen? Answer is no, but we'll see why. What's the output? >> Yeah. >> Game score. >> The game score. Uh, no. But we're going to talk about the game score in the back.
54:54
>> Yeah. Let's let's talk about the output first and then we'll talk about the stuff we can get rid of on the inputs. But what's the output? Yeah, >> it's the the actions. >> Yeah, the actions. So, yeah, it will be the Q values associated with the actions in state S. Remember, it's a Q function. So, the output is we need one value for left, one value for right, and one value for idle. You could make this game more complicated and say we have eight actions. We have a little bit to the
55:25
left, a lot to the left, a lot more to the left. You know, if you had multiple buttons, but let's simplify and say three actions. Either you don't move, you move to the left or you move to the right. So these are the outputs. So now let's get to the question of the screen. Do we need the entire screen? >> So you were saying something earlier?
55:52
>> Okay. So you say you need the tray and the bricks. I would argue uh you need more because there's the walls. And I guess that you could if you're an expert player, you could know where the walls are, but generally you need a little more than that. What what what would be obviously things we can get rid of? And why would we do that? >> The background. >> Okay. The score, the score at the top. >> Um, who would remove the score at the top? About half. Why would you not remove it?
56:33
>> Why would you remove it?
56:39
>> Okay, you want to always win. So the score doesn't matter. It's true. We would remove the score. So you you could actually crop the top. You could also crop the bottom. I mean, if it passed the paddle, you don't care about the few pixels at the bottom. You could get rid of them. Um this is not always true. There are games where the score matters and in fact you know I like football soccer the the in soccer if you're one zero up you can park the bus. So your
57:08
strategy is dependent of the score that you have like you wouldn't park the bus if you're losing one zero. Parking the bus meaning you ask every player to come back and defend. If you're losing you would actually do the opposite. You will go all out attack. So in certain games you want the scores, in others you don't want. And so it's part of the designer, the the the AI engineer that's working on that to determine what information we need and what we don't need. What else
57:33
could we do to reduce the dimensionality of the problem and make our computation faster? >> Yeah, remove the RGB channels. So do grayscale essentially. That's true. Here you actually don't need the colors. It's just nice as a user for user experience purposes. you don't need. I don't think there's different points based on the bricks that you destroy. It's all the same. Um there actually, funny enough, this algorithm was used by um Deepine to play a lot of Atari games and they did a
58:04
single pre-processing where they removed the channels because they said it doesn't matter. Turns out in one of the games, I think it was CQS, I forgot which one, the fish disappeared when you did that. And so that game didn't work. the the agent couldn't crack it uh because they thought that the same pre-processing could apply to every game, but actually they had to make a slight tweak.
58:37
also >> correct >> you. So just to recap, you could do it even better by using a a low dimensional representation of this game that describes the game. It's true, but because we want to use a single algorithm for 50 plus Atari games, we'll say the human sees the screen, we'll just give the screen and it will probably scale better essentially. But you're perfectly right if you were working on only that game. Okay, so let's do that. We'll we'll do pre-processing. There's one last thing
59:05
that nobody mentioned which is history because in fact if you get only one screen you don't know where the ball is going. So actually you can't solve the game and the way you fix that is by giving a history of multiple screens for example four screens so that you see the direction that the ball is going in. So our pre-processing function is you know called f ofs let's say and f ofs is a mix of um you know you might do convert to grayscale reduce the dimension the
59:34
height and width and also add the history of four frames and that should be enough. Turns out in most games you will need a history a little bit of history to know where the ball is going or >> in this example can just encode the uh like velocity vector of the ball. Yeah, you could you could replace exactly you could replace um the history so multiple screen by just adding the gradient or the velocity of where the ball is going. That's true. But would it scale to every game? You
1:00:02
know, turns out this because we know humans look at the Atari machine and they look at pixels. This would be more likely to scale to every game. Like think about a game where actually sequest is a good game or space invaders where you have multiple enemies coming at you then you would need to change your pre-processing to take into account the velocity of all these enemies. So it wouldn't work the same way. While if you actually give the pixels you actually
1:00:29
from the pixels get the velocity of all your enemies and the directions they're going. Okay. So this is our pre-processing. I'm going to refer to it as fs. And um our deep Q network architecture because we're working with pixels is going to be um a convolutional network. Don't worry if you haven't learned it yet in the class, but it's a bunch of con and relu activations. Um and then we end with a fully connected layer that gives us the three Q values for uh the different actions.
1:01:03
So nothing special here. Now, uh, we're going to go back to our vanilla training. So, this one that we saw together earlier, and we're going to look at tips to train reinforcement learning algorithms. Those tips are not specific to Q-learning. Some of them are applied to a lot more than Q-learning, and they're very important to know. Um, and they're part of the reason reinforcement learning has worked better in the last few years. Um, so one of the things that's pretty simple that we
1:01:30
forgot to do um is the pre-processing that we just did. So anywhere I had an S, I'm going to instead run S through the pre-processing step, I'm going to use PH of S. So I initialize instead of S with P of S. I start from the initial state of S and then I for propagate f of I um I get the Q of that pre-processed state in action A and etc. etc. And then when I get my next state, so let's say I look at my current pre-processed state, I forward propagate it once. I see the
1:02:08
three Q values, in our case, the two Q values. One of them was better than the other action, right? Then I get my next state S prime. I want to pre-process that state as well. Yeah, so that's pretty straightforward. You just replace all of that. The second thing we forgot to do is to keep track of the terminal state. In our pseudo code, there is no concept of terminal state. It's pretty easy to add. You would probably just do an if else statement. You would create a boolean to
1:02:38
detect terminal state. So let's say your boolean is terminal equals false. And then as you loop over the time step of a single episode, every time you're going to check, is the state that I'm going in based on the action I'm taking a terminal state? If it's a terminal state, then get out of the loop. You know, there's nothing else after. The one thing that you need to be careful of is if it's a terminal state, then your target is not the Bellman equation. It's
1:03:04
just the the immediate reward. Remember, you get to the terminal state, you get a reward of 10. There's no Bellman equation to apply. It's just 10. It's immediate reward. There's no discount, etc.
1:03:20
Okay, so these are fairly easy changes. Now, we're going to look at a new method that will enable more data efficiency. It's called experience replay. One of the a couple of issues with the way we've been training so far is one the correlation of successive screens. It's like imagine in the Atari game you have the ball that's in the top left corner and it's traveling to the bottom right of the screen. You have like many many time step that are essentially the same.
1:03:53
It's all the ball traveling in the same in the same place. So you're actually training repetitively on something that is not that meaningful. You don't need to just train on a batch. The equivalent in supervised learning is let's say you're trying to differentiate cats and dogs and you train on a mini batch of cats, then you train on a mini batch of dogs, then you train on a mini batch of cats, and it will never converge. It will just index too much on cats and
1:04:18
then index too much on dogs. So you want to add some sort of a experience replay concept that we'll see in order to create more mixes in the data and get more diversity. The other thing that is important is in our current training process, we are not reusing our data. Like you experience something, you immediately train on it. You never see it again unless you reexperience the same thing sometimes in the future, which might or might not happen. Experience replay is going to
1:04:50
help us to keep experiences in memory and maybe retrain on them on a regular basis so that one experience might be useful multiple times which intuitively makes sense. Like maybe you do an experience, you get an amazing reward and you don't want to forget it. You want to retrain the model on it on a regular basis. It's more data efficiency. So here's what it looks like. Um, the current way we were training was we're in a state I'm just going to say state instead of pre-processed state, but it's
1:05:18
pre-processed. We're in a state S. We perform action A, we get a reward R, and we get into the next state. From that next state, we perform another action A prime, we get a reward RP prime, and we get into S second and so on, you know, and so on. And each of these would be called one experience. It's one iteration of gradient descent. It's one experience. So right now we're training on these experiences. So the training looks like I train on E1, I update my
1:05:48
parameters. Then I train on E2, I update my parameters. Then I train on E3, update my parameters. Those are highly correlated because they're part of the same episode. And as I was saying with the ball traveling in one direction, that might actually not be that helpful to train on all of these, you know. So instead what we'll do is we'll use experience replay where we will collect our first experience but instead of training on it we will put it in a memory called the replay memory D. We'll
1:06:18
put it in there and then at every step we will sample from that memory to decide what to train on. So of course at the beginning if we just have one uh experience in the memory we will train on that experience. But over time you will see that we get more diversity and reuse out of our experiences. So for example, let's say I experience E2, I put it in the memory and then instead of training on E2, I'm going to randomly sample from the memory. I might get E1
1:06:47
or I might get E2. Then I experience E3 and I put it in the memory and I might get one of the three. You know, this is the vanilla experience replay. In practice, there is more methods like prioritize sweeping which might tell you which experience you want to weigh. Maybe some experiences had a higher gradient, so you want to prioritize them more often. You know, things like that. So, all in all, this is what our training looks like with experience replay. We experience um E1, we train on
1:07:19
E1. Then we the next training iteration is not on E2, it's on a sample from E1 and E2. Either or. The third experience is then put in the replay memory but we don't train on it. We train on a sample from whatever is in the replay memory and we repeat and that is more sample more efficient allows more reusability and less crossorrelation in our um training batch. Okay. So that's called replay memory and you can use it with mini batch gradient descent. Note that you still
1:07:57
experience in the direction that the game is played. Like we still go and take the action as expected. We just don't necessarily update our model parameter based on the action that we ended up taking. We put it in the replay memory. We may train on it later. Okay. Um so here is how it modifies our vanilla setup. We've added an experience from state S to state S prime to the replay memory. You know, like let me walk you through it again. Within one time step, we forward propagate our
1:08:32
state into the Q network. We execute the best action given the Q values. This gives us a reward and the next state. The next state is pre-processed. And then instead of training on that, instead of training, we just add that transition to the replay memory. And instead we sample randomly a mini batch of transition from the replay memory and we train on those and we redo the same thing again and again. >> Yes. replay bias towards the start of the game sample from everything. So, aren't
1:09:08
you more likely to trade start game just like you would sometimes want? >> Yeah. >> Yeah, you you you would uh you would within one episode, but you know, if you if you play multiple chess game, uh your replay memory would get already bigger. So, then you would see some end game, some middle of the game, some early games. Yeah, good. And in practice, it's actually useful because uh you might imagine that in a chess game, you know, all of us, let's say if you're a beginner, you you see a
1:09:45
lot of beginning of the games. You actually people that are beginners, they're good at openings, but they're bad at end games because they don't get to play a lot of end games. Uh well, that type of approach could be useful. You can retrain on end games more often. And you know the a more advanced version of the replay memory would also weigh the experience in the replay memory based on how much the gradient is going to be. So if you have an experience that actually was super
1:10:11
insightful, you can weigh it higher so that you you you prioritize grabbing it and retraining on it essentially. So let's say you blunder in chess, you might actually want to receive that blunder later so that you don't do it again. Um okay so these were all the different methods. Another one that's very um intuitive and very important is when during the training process our um agent gets stuck gets stuck in a local minima. Uh here is how it would work in practice. Uh you start in initial state
1:10:47
s1 and you have three states ahead of you. If you take action a1 you go to state two which is a terminal state. If you take and you get a reward of zero. If you take action A2, you get to S3 also a terminal state and you get a reward of one. And if you get um action A3, get to state four terminal state with a reward of a,000. So of course to us it's obvious that we would want to explore the state number four. It's pretty obvious in practice. Let's say you update you you initialize your
1:11:20
network and in the first forward path that's what you get first forward path the network is random you get Q value for action one.5 for action 2.4 four for action 3.3. What does that mean? It means the agent is saying I'm going to go to action one. So I take action one and I see an immediate reward of zero. Right? Because it's a terminal state. The Bman equation thing doesn't happen. I just have the immediate reward which becomes my target Y. And so I perform a gradient descent
1:11:56
update to say this Q value should have been zero. So I convert this Q value to zero. Now second try. This time the Q value is saying take action two. It's the highest Q value. I take action two. I have an immediate reward ahead of me. That's one because it's a terminal state. There's no second discounted future reward term. Um so I just take Y equals 1. I perform my gradient descent updates and this converts to one. And then third time the agent is still saying go to A2. Go to
1:12:36
the take action A2 reward of one. Good. That's what you predicted. Nothing to do. Just keep going. We're done with training. We're stuck. We never visit the state we actually wanted to visit. Okay. So that that that wouldn't work for us. We will never visit that state using our current algorithm. Does that make sense why we wouldn't ever visit that state? In practice, this is a big issue. The analogy of this uh concept of exploration versus exploitation is when
1:13:10
every day you take your bike and you cross um campus, you have a favorite route. And turns out that the more you take that route, the better you get every time. Like you get a little faster. Maybe your turn is faster or something or you can predict how many people are going to be at that roundabout and you know how to take it in the wide way so you go faster. We've all done that. Um that's exploitation. You exploit what you already know and you get better at it. But maybe there's
1:13:36
another route that you're not thinking of that's pretty instead of going north from campus, you go south and maybe it might be better. You will never see because you don't have the courage or the patience to do it. That's the difference between exploration and exploitation. In practice, a good model would be able to handle both to exploit when 22 to exploit to explore when it needs to explore. The way we do it in practice in our pseudo code is to inject some
1:14:04
randomness. So for example, when we are looping over time step with probability epsilon let's say 5% take a random action. So from time to time on average one time every 20 times you take a random action it will allow you to visit maybe a new path. The analogy in chess is you know you might use a creative move from time to time that might be worse today but might allow you to learn something and to get better over time. >> Yeah. Um in that uh the example we just
1:14:37
covered, couldn't we resolve that by just setting the initial um Q values to infinity? >> Setting the the Couldn't we resolve this problem by setting the initial values from into infinity? Well, the problem if you set the initial values to infinity. So you would say instead of randomly initializing your network, you initialize it in a way that the outputs are equal to infinity. >> Yeah. so that we wouldn't get the issue of where like the Q value of action three state one is
1:15:09
>> well in practice if the three Q values are infinity then you can't make a decision on the spot so you're saying just pick one randomly because if the three are infinity you you can't decide which one to take right and also if in if it's infinity and the reward is one I mean if it's a really large number and the reward is one your gradient is going to be massive right so it's going uh I guess the loss function is going to be massive and um I don't know I imagine it would be really hard
1:15:37
to train it but in practice you start with the random initialization because in this might be one example but you know if in the game of chess um actually the the reward is one at the end and zero all the time or maybe the reward is a thousand at the end and when you lose your rook it's uh it's a negative reward. You can't predict what the reward structure is going to be. We want an agent that is able to adapt to it and um it's better to find a method that can scale to different environments
1:16:07
essentially. Um okay so this was um epsilon greedy action which is adding some randomness with probability epsilon take a random action. Okay, so adding all our techniques because we get good at training reinforcement learning algorithms. This is what we have. We initialize our Q network parameters. We have a random network. We initialize our replay memory D. And then we loop over episodes. We start from an initial state. We create a boolean that allows us to detect terminal states with
1:16:42
probability epsilon. We're going to take a random action. Otherwise, we're going to follow what we know, which is forward propagate the state in the Q network. take the action that has the highest Q value that allows you to observe a reward and the next state take that next state forward propagate it again instead and then and then instead of um uh oh no sorry observe that next state add it to the replay memory sample from the replay memory and then train on that
1:17:14
sample and in the process you will need to do another forward path because you need to estimate your target by using the immediate reward plus the belman equation plus the discounted future reward. Okay, are you experts at Q-learning?
1:17:34
Okay, good. Sounds good. And here is where we get at the end. You can claim proudly you have trained an atari. It's not that complicated as you can see other than the Bellman equation piece. Turns out the agent has discovered that it can send the ball on the back and it's actually much easier to finish the game like that which is quite interesting. You know, a good player would know that you can dig a tunnel and you can finish the game without too much issues. Yeah. >> How do you actually
1:18:04
>> How do you quantify when uh when the game has ended? >> How would the model come after the train? >> Yeah. Well, uh, first you would you would you would start seeing um the model get to good rewards as it play like it manages to get really good rewards while earlier it might not, you know, and so that's probably your best guess for how good the model is. In practice, if you're AlphaGo, you can also test it against the best humans in the world and you can observe that
1:18:32
they're losing against the model. I'm saying you have like a bunch of different chest engines and some of them are way way better than others. They have different maybe they're both based on reinforcement learning and at the end they maximize both of their rewards. >> Yeah. >> So how do you know which model is actually doing better? >> You can get them to play together. So you have no idea if you do that one. >> No, you you could you could actually monitor the loss function and look at is
1:19:02
the Bellman equation respected. If the Bellman equation is respected, then your model is really really good. And then we we're going to see an example of competitive selfplay where you get the model to play against other models and then over time as you watch them play for thousands and thousands of time, you can tell which model is ahead of another one. You can then sort of copy paste the best model into the other models and then make them play again for many
1:19:28
times. And because you have the epsilon greedy approach, one of the model is naturally going to get better than the others because of the randomness that you add.
1:19:40
Um, okay, let's look at a few examples and then we'll spend 20 minutes on the RLHF. Um, here are other examples. This is Pong uh which is one v one sequest which is an underwater game. And then the one that maybe more of you know Space Invaders very popular game as well. So the impressive thing that they showed is that you can um actually solve many games with the exact same algorithm, no tweaks, which is quite impressive.
1:20:18
Let's go a little further and talk about um advanced topics. Um here is a game called Montezuma Revenge. Um this game is particular because you're controlling a little character right here. And this character is trying to go and grab, let's say, this key right here, and it has some obstacles or some enemies that it needs to take care of. What what do you think is going to be an issue if we apply what we just learned to this game? What makes this game especially hard in
1:20:54
comparison to let's say chess or go? >> Yes. >> Yeah, the reward is very delayed. Like if you start with a random network, what are the chances that the network is going to figure out that to get to the key, it actually should go in the opposite direction. It should go in the opposite direction. It could jump down here. It should catch the rope. The rope will probably allow the character to go to the ladder. It goes down the ladder. It has to go jump up this enemy. My
1:21:26
guess is it's in an enemy. I'm not sure, but I think it's an enemy because of the color. And I know that in gaming if it was green it might not have been an enemy but if it's gray or red it might be an enemy. And then go up the ladder and grab the key. The chance is very low that the agent is going to make that successive good decisions to get there. You're right. Why is it use why is it easier for a human to actually solve that game? >> Intuition. >> Intuition. Prior knowledge. So, for
1:21:59
example, when you look at this game, even if you have never played it, my guess is you would know you can go down the ladder because you know what a ladder is. Or you can see this little rope and you're like, I'm going to catch the rope. I'm going to jump and go to the other side. And you look at this little monster and you're like, I better not touch this monster. Or if anything, I will jump on top of it. Cuz you've played Mario, let's say. So, all of this is human intuition. uh sometimes you
1:22:25
would call as a baby survival instinct like you throw the baby in the water and suddenly it flips and it can um it can uh swim. Those are things that are to a certain extent encoded in our DNA but at the very least encoded in our experience of doing other things that have nothing to do with this game. And so the the problem here is called imitation learning. Is is there a better way to start our network than a random initialization that allows the network to for example guess that this is a
1:22:51
ladder and turns out that if the network knows that it will be more likely to get to the reward first and then learn from that reward and then get better over time. The other part that can also use human knowledge which is what we're going to see together is reinforcement learning from human feedback where you have an analogy here which is you can train a language model and it might be completely misaligned with what actually humans care about. How does reinforcement learning help in those
1:23:18
situations? That's going to be the next topic in the last part of the lecture. Okay, let me show you a few other results um quickly. Today we talked about DQ and deep Q learning. In practice there's a lot more reinforcement learning algorithm but you got the gist of it. You got the concept of making good sequences of decision epsilon greedy exploration exploitation um terminal state starting state all of that you you got the one the one algorithm that is very popular right now
1:23:47
is called PO proximal policy optimization. There is one that is even more popular right now that's actually from a year ago at Stanford called DPO that we won't study in the class. One of the things to know about PO just just to go over it really quickly and and I I pasted two important papers from Schulman a few years back trust TRPO and PO um is that it is not a value based algorithm. So in Q-learning you learn the Q values and then you define your policy as the arg max of the Q values.
1:24:20
In PO, you learn the policy directly, which is a more probabilistic method. Um, it also works well with continuous spaces. If you look at the Q-learning, we learned one output for one action. If you actually have um a game that has continuous action like autonomous driving where it's not like just turn the wheel to the right or to the left, it's like what degree you turn it, it's continuous. then Q the QN would not work well or you would have to granularize
1:24:50
the number of action a little bit to the right a little bit more a little more which would not be really useful instead you would use PO
1:25:06
>> yeah so question is how do you define a reward in DQN um different reward structure will lead to different uh types of you know agent strategies. Uh but you're right for the game of go you could actually define the reward as one if you win and zero if you don't win. That's it. You know every move will be zero until the last move is a win. In chess you might actually do intermediate reward because you want to tell the you want to tell the agent that it's good to
1:25:33
kill the opponent's pieces to get rid of them. You could also do end to end and say I don't give any intermediate reward. I just give a final reward which might be more complicated to train on but it might actually lead to a more optimal strategy because in fact you could actually win without taking any piece from your opponent. So other things about PO is um you know it's more probabilistic. It has a concept of an expected advantage which at every steps instead of telling you
1:26:02
how good that action is, it would tell you how much better it is than random than than the current state like how much better would it be to do certain thing versus what you would have done otherwise. I'm not going to go into the details. It's all in the paper. But those are things that are important. Here's a few examples of PO. So this example on the left is from open AI a few years back where you can see it's a continuous space where uh the agent is being um bullied a little bit but um
1:26:32
it's trying to grab the rewards but it's also subject to external forces that are sort of throwing balls at it. It's a little bit mean, but um you can imagine that this is a continuous space, meaning you're controlling the nodes, you're controlling the joints of the agent, and you're controlling the forces, the angles, and so it's a that's why PO would be better in that case. Super. Here's a competitive selfplay, which I really like [Music] where you have agent play with each
1:27:07
other. And this is the sumo game. Push the opponent outside the ring and you get a reward. So actually it's interesting because you're seeing some emergent behavior which is they attack each other's feet or they lower their center of gravity to be more stable for example. Yeah. >> Yeah. Yeah. It's versions sometimes different initializations for example. >> So no but good question. So often time what open would do back you know back in that time is they would create copies of
1:27:42
the same model they would initialize them differently and they would let them learn and turns out one of the model will get better than the others and then they will copy again that model to the rest and do the same thing again and again pretty much. Oh yeah it's kind of funny isn't it? That's a good catch. Yeah, that's a good goal. Could watch that for hours. Okay, [Music] they're a little awkward, you have to say, but but it it works. Okay, so this, you know, I let you watch the video,
1:28:20
it's going to be shared, but um here's another set of games that are even more complicated that I mentioned early on. Open AAI 5 which you can think of an equivalent of League of Legend Dota where you have um 5v5 game so you have to collaborate etc which makes it adds like literally one additional um degree of complexity. Uh and Starcraft uh Alpha Star from Deep Mind is an example of where the observation is not the entire state you have fog and so that adds
1:28:53
another layer of complexity. not going to see that together today. Um, I would encourage you to look at the AlphaGo documentary on Netflix if you haven't. Who has seen it already? Nobody. Okay. Well, um, you can now watch it with a different eye, understanding reinforcement learning. And at some point in the in the documentary, you will see that um Alph Go makes a very odd move, a very creative move. And people are like, I don't understand that move. Even the top
1:29:30
researchers or the best players would say in the video, they don't understand that move. It turns out that that move is very unintuitive for humans because as humans, we are trained to maximize our chances of winning. Like literally, if I can eat all your pieces in chess, I will eat all your pieces. And if I can surround your stones in go as much as I can, I will do it. The agent is just programmed to win. So that move actually look counterintuitive because the agent
1:29:57
doesn't care about winning by one or winning by a, you know, 20 stones. It just cares about winning. And that move specifically put the agent in a good place to win by a small margin. Yeah. So that's an example of an insight that you will learn. you you understand from this class and you will see in the in the documentary. Okay, I think we have 10 minutes. I'm I'm just going to introduce uh reinforcement learning from human feedback because it's a more um modern
1:30:27
topic that um is very trendy right now. It's important to know and so let's look at it together. We're going to start by recapping how language models are trained in a nutshell and then we'll see what self what supervised fine-tuning looks like. We'll talk about how do we train a critique model, a reward model and then finally what RLHF looks like and why is it so trending in the news. So um our training objective for language models is next token prediction, right? We've already talked
1:30:59
about it in a former lecture. The idea is that I will get some inputs. I'm reading Wikipedia, let's say, or some sort of a text online and I read a sentence and I predict the last token and I do that again and again. So for example, deep learning and then deep learning is deep learning is so deep learning is so cool and that's it. Um, so you get the idea, right? you always predict the next token and then over time it forces the model to um explicit u um emerging behaviors
1:31:36
and it understands the connections between those concepts and it's really good at generating text. We compute a loss function. You're actually going to study this loss function in uh C 5. So I'm not going to talk about it right now, but you perform, you know, a gradient descent loop. And this is how you get your first pre-trained language model. Get a pre-trained language model. You can call it on a text or a prompt and it will continually generate and you
1:32:04
call it again and again and again and it generate generate generates. Everybody's comfortable with that, right? Okay. So, uh that's how we trained a language model. But there is a couple of problems. The first problem is that online data does not reflect helpfulness. So to give you a concrete example um what you might find in the training set is something like deep learning is so cool when actually what you might find in practice is people asking what is deep learning.
1:32:39
So the data is not really reflective of you want an agent to be helpful and that's a problem because the model was trained to continue text rather than answer questions and in practice you would see it's a big problem. Another problem is the model has no concept of good, polite, or helpful yet. And to give you a concrete example, you might actually ask a pre-trained language model, my laptop won't turn on. What should I do? And then the model responds because it has
1:33:09
Reddit on Reddit or on Wikipedia is laptops sometimes don't turn on because of power issues. Um, which is not what you ask. You ask what should I do? And in fact, a better answer would have been check your charger if is properly connected or the outlet works. If that's fine, try holding the power button for 10 seconds. If it still doesn't start, the battery or motorboard may blah blah blah blah. That's a better answer. That's what you want an a language model
1:33:34
to do nowadays. Um, and the model um can give you factual text because that's what it's been trained on, but it's it doesn't understand being helpful or um having an answer that looks like a humanlike answer. So our solution to it will start with using supervised fine-tuning um which is going to be learning from human written demonstrations of helpful behavior and then we get to even further and use RHF which will optimize not only for human written sentences or paragraphs but for
1:34:07
preferences and the word preference is the keyword. Let's talk about how we can improve our pre-trained model with supervised finetuning. I'll take um that we want to align models with human written responses and the step one that we're going to lose is to build a data set. Let's build a data set of human prompt response pairs. So what actually open is going to do I'll explain it in a second is it might collect some of the prompts that we all use and then ask humans to
1:34:39
respond to those prompts and put that in a data set. It might al also ask separately experts to write really good prompts and then answer those prompts. It's a fully human-made data set. And then we use that data set to fine-tune our pre-trained model. And by now you've learned fine-tuning in the online video. So you know what I'm talking about using supervised learning. So what it looks like is I take my pre-trained model that I just told you how we train and then I
1:35:07
give it a prompt explain deep learning to a beginner and I also will concatenate to it a response a good response written by a human. Deep learning is a type of machine learning that uses neural and then I expect the model to come up with the word networks. So it's literally do whatever we did to train the pre-trained model but we do it on human written front response pairs and if you do that many times and you use the you know the same loss function how far the model's response is from a
1:35:44
human response um you do that many times and you will get SFT supervised fine-tuning um but it has some shortcomings One of the shortcomings is it is data that is extremely costly to collect. In fact, I believe in the first version of that instruct GPT there was only 13,000 prompt response pairs and turns out it did really well despite that. Um the second aspect is it's unlikely to generalize well because you're again you're not doing reinforcement learning here. You're doing supervised learning
1:36:28
and so you're just showing a set of examples 13,000 examples that you want to learn but it's what tells you that it will generalize to an unseen prompt that will come up from your user base. And so this approach SFT really teaches the model to imitate good behavior from humans. And that's the key. It's it's imitation. It is not preference optimization. To do preference optimization, that's where we're going to train a reward model and we're going to do proper RHF. So let me talk to you about
1:37:04
the RM reward model and then I'll tell you about RHF in a nutshell. The problem of um RHF is to align not with human responses but with human preferences. So what what's going to happen is we're going to train a separate model to predict which responses human prefer and we're going to call that model the reward model. It's a separate model from whatever we've trained before. The model um is going to use data from labelers. So you're going to show labelers two or more responses to the same prompt
1:37:44
and those responses will be sampled from the SFT. So your best model right now is the SFT. You will sample three or four responses and you know how we sample right you you can tweak the temperature. You can select not only the top priority word, the top the softmax layers number one word, but you can sometimes sample differently and you will get a variety of answers. And then you will ask a human labeler to say answer B is better than answer C and answer C is better
1:38:14
than answer A and answer A is sort of equal to answer D. Let's say um they will be asked which response they prefer and it can get more complicated. It doesn't have to be just a simple ranking. You you have multiple liker scale methods and so on. But the the point is that you will collect those pair-wise comparison that we call preference data and you will use it to train a reward model which is initialized from your SFT. So your SFT is here. It's your best model to date
1:38:46
and you're going to modify the last layer. So the softmax layer at the end of a language model that will tell you this is the token we should output or this is the word we should write. Um instead of that you'll get rid of that layer. You'll put a scalar value as output. You'll put a linear layer with a scalar value that will represent the reward head. It will predict the the reward you know uh which is a proxy for the preference of the human. The way you'll train that reward model is you'll
1:39:15
give it um a batch of two um you know you give it a prompt X with a response A and the preference of the user and you'll give it the same prompt with a response B from the SFT with the preference of the user. So here the user is saying response A is better than response B. And so if you actually were sending that in this model, you will get a predicted reward for the preferred answer and a predicted reward for the this preferred answer that allows you to uh train using a loss
1:39:52
function that I'm not going to cover given our our time sensitivity. The loss function will encourage the model to assign higher rewards to preferred responses. So you're trying to dissociate the higher reward better preference from the lower reward for lower preference. And it turns out that if you do that many times, you will have a reward model that given a prompt and a response will be approximating human preference. So you've just trained a critique that represents your humans.
1:40:23
It's a proxy for what humans prefer. It's been trained on a lot of human preferences. The reason it's better to use a model than actual humans is because we can use it widely on all sorts of inputs and it can scale from a data standpoint. Also note that this method is better than SFT because it's way easier to ask humans what's your preference between those two things and to ask them to come up with answers to prompts. Takes way less time. And if you've used SH GPT,
1:40:51
you've probably been asked before to to to tell them which response you prefer. Yeah. So once trained the reward model represses the human as the evaluator during reinforcement learning with from human feedback and reinforcement learning from human feedback is very comfortable for you. Now I will I will show you what it looks like given the Q-learning algorithm we learned. But essentially we we have first talked the model what good behavior looks like with SFT and then we built a reward model
1:41:21
that can tell us how good an answer is according to human preferences and the RHF approach is where we will let this model practice get scored by the reward model or the critic and update itself to produce higher scoring answers. So more preferred answers and it's the same as the games we've seen together but some things differ. So I just pasted here the exact setup that we've learned together um for reinforcement learning. The differences are the following. You know
1:41:55
our objective is still to maximize expected reward that is produced um by the reward model aligned with human preferences. The agent is the language model being fine-tuned. The environment is the space of possible prompts and continuations. It's any any text that you can encounter. The state is the specific prompt plus the tokens that were generated so far. The next state is one more token added and the action is the next token that is chosen by the agent or the model.
1:42:34
which is of course determined by the policy and then the reward is estimated by the reward model that we trained to represent human preferences. Okay, in this case one episode is one full prompt. So imagine that you get a prompt and you start generating and you go through this reinforcement learning loop and you observe the rewards and then you try to maximize the future rewards and then at the end of training you end up with having your pre-trained model turn
1:43:08
into an SFT and your SFT turn into a way better model using RHF.
1:43:18
Okay, so a few things to note to end on this. The model does not get a reward at every single token. It gets a reward at the end of a sequence when the completion is finished because reward model was uh was asked to rate prompts and responses together. So you need to finish the generation in order to see what's the reward. And so again going back to making good sequences of decision that's exactly it. You want the model to make enough good sequences of decision so that the response is
1:43:50
preferred by the critique which represents a proxy to the human preferences. So all intermediary rewards are typically zero and that makes it a very sparse reward episodic tasks just like a game of chess where you only get a reward when you finish assuming you're not defining intermediary reward. So you only know if you did well at the end and you have to then use that information to update your network and get a better proxy for it. Super. There's a very nice
1:44:22
video. We're not going to play it for the sake of time, but I will send it online. Uh it's from 4 days ago. It's uh you know former Stanford students Andre Karpati who is very thoughtful and articulate and was explaining 4 days ago why reinforcement learning can be terrible at times and that human minds work way more efficiently. And so I would encourage you to watch this 4-minute video because he's very clearly outlining why reinforcement learning is still not
1:44:53
great even if it's the best thing we can use in many ways.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat