Skip to main content
Loading Explore guides…
Reinforcement Learning · Acedra
Home
Explore
Computer Science
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
94 segments
Copy
Hide video
0:00
Good morning, good afternoon, good evening. Today I want to introduce you to the third paradigm of machine learning: reinforcement learning. The first paradigm is supervised learning, which we saw here in the form of classification and regression, using KNN, Naive Bayes, and neural networks. The second paradigm is unsupervised learning, which we saw through the K-MINS algorithm, to find natural groupings in data, which is called clustering. In reinforcement learning, which is inspired by
0:37
operant conditioning in psychology, the goal is to learn through sparse reward signals, that is, signals that can occur sporadically. You know the little mouse that presses the button and gets food? That's it. It's quite different from supervised learning, where we have labels or correct reference values for each piece of data and learn by error. In reinforcement learning, sequences of actions that lead to good results will be reinforced to occur
1:08
more frequently, while sequences of actions that lead to bad results will be discouraged. So here we can, for example, apply a value plus one or any other value when the agent achieves a goal. For example, in this diagram, if it picked up food, it could gain a value plus one. And it could gain a value minus one or any other value when it fails, which would be a punishment. And the agent needs to learn the best
1:37
sequence of actions that leads to the greatest amount of rewards. In many cases, there are no rewards or punishments during the course. They are only at the end. This makes the problem much more difficult. Let's look at an example here. So we have a 4x4 grid, a kind of board, right? And our agent starts here in the lower left corner. This will be our Wally here. It needs to reach the upper right corner to receive a reinforcement
2:06
of plus 100 and end the episode. However, if it steps on the square below, it receives minus 100 and ends the episode. You can imagine that this plus 100 is an exit, for example, and this minus 100 could be a trap, a hole where it falls and breaks. Okay, an episode is what we call a round of execution in the environment when we're working with episodic problems, which is the case here. It has a beginning and an end. Then
2:34
it resets and starts again from the initial point. So the robot walks, and when it reaches one of these states here, it returns to the beginning and starts a new episode. Note also that the problem is discrete, since the agent will always be in one of these 16 possible states. Each square here is a state. So they are finite and countable states. Therefore, the problem is discrete. And here we will work with the discrete environment because it is
2:57
easier to understand reinforcement learning initially. So, in addition to being episodic and discrete, this environment is also fully observable. The agent knows exactly where it is and has no hidden information. Finally, this environment is deterministic. Whenever the agent moves upwards, it goes to the square above. Or if it is already in a square here at the top and moves upwards, it stays in the same place. It's as
3:22
if there's a wall. Whenever it moves to the right, it lands on the rightmost square , and so on. There are no probabilities involved here. I don't roll a die to see where it will land, like in Monopoly. Okay, now that I've presented the problem to you, I'm going to present one of the existing solutions for this type of environment, which is the Q-Learning algorithm. First, we're going to put four zero values in each state. In this environment, remember, each
3:49
square is a state, and the agent has four possible actions: up, down, left, and right. So, that's why there are four zeros in each state. These numbers are called Q-values, or quality values, for each action in each state. And we're going to try to learn them now. We expect the best values to lead us along the path to the reward. This number represents the Q-value, how much reward the algorithm expects to accumulate from then on if it chooses that action and continues to
4:19
always choose the best action. So, for example, this zero down here, at the top, represents how much I expect to earn from that point on, after I move upwards, how much I expect to earn from that point until the end of the episode. In this case, it's all zero. So, be careful! These numbers here are not the same as the numbers up here. These two here, the green and the red ones, are immediate rewards, plus
4:45
one hundred and minus one hundred. It's not an expectation. These Q values, however, are expectations of accumulated rewards until the end of the episode. They are different things. And how are we going to learn this? The agent will always choose the action with the highest value in its current state. In this case, since all the values are zero, it will initially go in a random direction. So, it's important here in terms of implementation
5:08
that when we have tied values, we randomly select one of them. Otherwise, the agent might get stuck. Let's say that in the order I programmed it, the left here is the first value, the first action. And the agent always chooses, since everything is tied, it chooses to the left. What will happen? It will be eternally stuck here and won't learn anything. It will keep hitting a wall to the left and won't move forward. So, whenever we have tied values, ideally you
5:35
should draw lots between them. Initially, the agent will be completely random. It will experiment until it discovers what is good or not, more or less like a baby. Let's say that at a given moment the agent entered the state with the punishment. Here it is exploring, like a baby, randomly. Then it entered the state that has the punishment here. What will happen? It came from below, right? If it was here, it went up. So, I'm going to take this punishment value and put it in the
6:05
Q value of the upward action of the state it came from. That is, this zero here will become minus one hundred. Okay? I copied the value there. This means that now it knows that if it is in this square and goes up, it will receive a minus one hundred punishment and the episode ends. It goes back to the beginning. And that's all. But what happens now? Note that when it falls into this square again and has to choose the action with the highest Q value, it
6:31
will not choose upwards. He's going to choose one of the zeros that are greater than negative one hundred. So, he's already learned something relevant here. He already knows that he shouldn't go up when he's here. Then, let's say he experimented for a while longer and fell into the trap again, but coming from the left. So, same thing. Put the negative one hundred there in the action to the right of where he came from. He already knows that when he's here, he can't go
6:52
to the right because he gets negative one hundred. So, notice that the way it is, he can no longer fall into the trap. He's already learned how to avoid the trap. Then, he continues experimenting, let's say, and he gets up there. Then, he finally falls into the reward and we update. We pulled one hundred there to the value Q on the right, from the previous square. It became one hundred. So, he already knows that when he's in this square, the best thing he can
7:15
do is go to the right because he'll gain one hundred points. But, what about the rest of the values? What happens now? Will everything be zero? No. Look what's going to happen now. Let's say he's in that square, the second-to-last one before reaching the reward. Now, we can update this square here. So, let's say he moves to the right. I pulled the one hundred from there to the previous one. So, the same thing happens in all the squares. But
7:40
the difference is that here, instead of taking an immediate reward, as was the case with the green one, I'm taking the largest of the four values and pulling it back. So, there was zero, zero, zero, and one hundred. So, I took the one hundred and pulled it back . Put one hundred there. So, now he knows that from here he has to go to the right, then right again. So, notice that implicitly he's forming a path there from back to front. He's learning how to reach the goal from back to front.
8:08
If we continue repeating this algorithm, eventually we complete the values up to the initial state. Something like that. And then he'll know exactly where he has to go from the beginning. And the exploration ends. We call this path here "policy" because it's a function that, given a state, returns to the action that should be taken. So, for example, if I move this state here to this political function, it returns me upwards. If I move this square here, it returns me to the right. So, politics
8:39
It's a function that we give a state to, and it tells us what action we have to take in that state. And this here is the graphical representation of our political function. Well, this is the simplified learning algorithm. But there are more things that I'm going to show you now that can happen, and the algorithm has to have a mechanism prepared to deal with these situations. So, first situation. Imagine there's a second reward here in the lower right corner, also worth 100. But if the agent
9:10
found the reward above first and learned the path, it will never again have the chance to discover this reward that is closer. It always chooses the action with the higher value. So, it can no longer discover that this guy here exists because it always goes up here. Think about the following real-world problem. You buy food on a delivery app, after a while, you already have your favorites and
9:35
always order from the same ones. In a way, you learned the best options through positive and negative reinforcement of everything you've tried on that app. But what if there's a much better restaurant that you've never tried? How do we solve this? The simplest solution is what we call epsilon-greedy exploration. It's written that way, and it consists of simply not always choosing the best action in each state. With an epsilon probability that we'll define—hence the name—
10:10
we can choose a random action. So, whenever we're in a state, until now we always chose the best possible action. With epsilon-greedy, what we'll do is, from time to time, we'll choose a random action instead of the best one. That's all. In the case of the restaurant, we would occasionally choose a random restaurant instead of going by experience. Could it go wrong? It could, but at least we learn more restaurants to avoid. Our knowledge increases. But
10:40
it could also go very well, and we discover a much better restaurant. This is the so-called exploration versus exploitation dilemma. Exploration would be the act of trying to extract the maximum from your agent, which would be choosing the best action. And exploitation is when we use random action. How do we balance these two things? Because we can't just keep exploiting, because then what I showed happens. You can't discover new things. But we also can't just keep exploring, because then we'll
11:09
be suffering eternally trying to learn something. There are other more advanced and intelligent forms of exploration, but here we'll stick with epsilon greedy. In terms of implementation, we'll just add an epsilon parameter here, defined by the programmer. In the example, I put 0.1, which means 10%. So that means that, at each state when choosing an action, the agent has a 10% chance of going to a random side instead of choosing the best action. And
11:40
the problem of finding better paths is solved, albeit in a simplistic way . Because then it won't always go up here; at some point, it will end up going to the right and discover this reward down here. So notice that I've already updated the values here as if he'd spent several episodes exploring and updated all the path values. I even included that, let's say, he explored from above and discovered that going from above also allows him to get 100 here. Now
12:09
let's move on to the second problematic situation. Let's say we explored the entire map. It looks like this. You can manually implement the algorithm I taught you, and you'll see that it will end up filling everything with 100, except where you go to the trap. Because we're always copying the highest value to the previous one. So what he learns here, in a way, what he's saying here is that it doesn't matter where I go, because
12:32
I'll always know where to go next until I reach the objective. Since he learned all the possible paths here, he knows that it doesn't matter where he goes, he can get there in the end. So basically, he thinks that all paths lead to Rome, that all paths are good. He can go in the most inefficient way possible to reach the objective. And it can't even differentiate between the reward that's closer and the reward that's
12:52
further away. For it, it's all the same. Solution? Consider the following example. Would you rather earn 100 reais today or next month? I believe most, if not all, would answer today. Even though it's the same amount, we have a preference. It's as if the 100 reais next month are worth less. And in fact they are, because of inflation, the lost opportunity cost of investment, and so on. And we can incorporate this reasoning
13:19
into the algorithm. We're going to make rewards further away worth less than rewards closer to the point. It's quite simple to implement. We're going to add a new parameter here, called gamma, which is the discount factor. I put 0.9 in the example here. When copying a value from one state to the previous one, I'll multiply it by this discount beforehand. So, for example, let's say I stepped on the square before the reward up there.
13:46
I was in this square here and I'm going to step on this last one now. What happens? I didn't copy 100 here. I copied 90, because it's 100 times 0.9. So there's already a decrease there. It's already understanding that if I go to the right I won't immediately gain 100. There will be a discount on the quality of this action. Here, yes, it's 100, 100 immediately. The moment I move from here to the right I gain 100 immediately, but not here. So it's already considering a discount here.
14:17
Now let's say I ran another episode. The little robot walked here, reached this upper left corner and moved to the right. What will happen? 81. Because I took this 90 here, which was the highest value, copied it here multiplied by 0.9. It became 81. If I repeat several episodes it will end up learning this whole path in this way. Here I'm already doing some rounding. It's approximate until the 81 here is exact. 72
14:45
here is already an approximate value I'm assigning. 72, 66, 59. He knows here that going upwards is good. But if he continues exploring and learns about this reward from below, what will happen? Let's say he's coming down here. He'll put 90 there, 81 here. So look how great, now he knows that going to the right is better than going upwards. Because going to the right is worth 81 here. It means he'll earn that 100 faster. Going upwards here is worth 59, because it takes him longer to earn
15:18
that 100. So the preference he has for the time factor is already embedded in the value . For the depreciation of the reward, let's say. And more than that, if I continue learning here, he'll also learn, for example, that he can't keep wandering around in a zigzag until he reaches the goal. He knows exactly that he'll be wasting time if he doesn't take the most direct path to the reward. So, another problem solved in a very simple way. Now let's move on to the last problematic situation.
15:49
Let's say that now, whenever the agent moves, there's a chance it will trip and fall into a square next to it. In other words, the environment is now non-deterministic, a bit more realistic. What happens if it's here between the trap and the lower reward and walks down, but then it trips and falls into the trap that was behind it? It will copy the value from the trap, which was -100, to the action down here, from this state, and it also became -100. Now it thinks it can't go down here because it
16:23
dies. And even though it had already learned, as was the case here, that going down there was good, it unlearned it. Now it thinks it's better not to go down there because it might fall into the trap. So the most correct thing here would be for it to learn an intermediate value, because most of the time if it's here and goes down, it will fall to plus 100. Occasionally it will fall to minus 100. So perhaps this value
16:47
that is here, minus 100, should be something intermediate, a positive value, but not 100. To reflect that it's sometimes 100 and sometimes minus 100. Solution: We're going to add one more parameter, which is the last one for today, I promise, which is alpha. Here I put 0.2 in the example. Then what we're going to do when we transfer a value to the previous state is simply move the old value towards it. Regarding the new value. Like, we're not going to change 100 to -100. We're going to move 100
17:22
towards -100. It won't be all at once, it will be little by little. So that value that was 100 and suddenly became -100, now it will only be adjusted a little bit here in the proportion of 0.2 towards -100, according to this formula here on the side. So let me explain what's in the formula. First, we have the previous value here. Before all this happened, there was a 100 here. This value that I'm putting there. The current value of that action. 0.2 is my alpha, which I defined.
17:59
In parentheses, I'm multiplying. -100 is the target value, the reward I received when I took that action, because I stumbled and fell to -100. Plus 0.9, which is the gamma, times the expected value in that state I fell into. Here's an important detail I haven't mentioned yet. Remember I said that these values are an estimate of the future? Therefore, these final states here, the plus 100, the minus 100, and the other
18:27
plus 100, they end the episode; they have no expectation of the future. So their Q value for any action, implicitly, is 0. Because the moment I fall into them, there is no more future. So that's what's here. I'm saying that the future value, the expected value, is 0, times the discount, which is 0.9, minus the current value again, which is that 100. Doing this calculation, it gives 60. So the new value I'm going to put
18:55
on that stock, instead of being minus 100, will be 60. So notice that he still thinks it 's a good DC. He just doesn't think it's perfect, wonderful, because he knows that sometimes he gets hurt. But it reflects reality much better. Here's the general formula. Don't even try to say it's complicated, because it's just simple addition, subtraction, and multiplication. The worst that happens is that sometimes these Greek letters appear, which scares us. But
19:19
there's nothing more to it, it's just a variable. In fact, it's even simpler, because they are constants. They are values that the programmer will define as fixed. So I'm saying here, the new value, which is T plus 1, at time T plus 1. We are at time T, T plus 1 is the next one. So the value at time T plus 1, for that value Q, that state in that action, will be equal to the current value, plus the learning rate alpha, times the reward
19:48
I received for performing that action, plus gamma times the highest expected value in the state I fell into, minus the current value. And that gives you the formula I showed you in the previous slide. 100 plus 0.2 times minus 100, plus 0.9 times 0, minus 100, equals 60. Another example, let's say our agent is now in the previous square, and it moves to 60, to the one we just updated to 60. How much do I have to
20:16
put there? Again, it's just applying the formula. Let's see here. The current value was 0, everything was zeroed there. So the current value is 0, plus my alpha times the reward I earned falling there. Zero, this square here has no reward, so it's zero. Plus 0.9 times the highest value of that square. If you look here, we have minus 100, zero, zero and 60. So the highest is 60. I put 60 here. Minus the current value again, which is 0, gives
20:49
10.8. I'll round it here and put 11. One last example. Now let's say he moved down here to get 100. How do we update that value that was 60? Let's look at the formula. The current value was 60, alpha times the reward I earned is 100, plus 0.9 times zero, because from there on there's no expectation of earning anything, minus 60, which was the current value, gives 68. So I updated that from 60 to 68. You'll notice that he's gradually moving towards 100, he doesn't go
21:22
all at once. It will happen that from time to time he'll fall here at minus 100 and lower that value. And he'll stay in this struggle, in this tug-of-war until he reaches an equilibrium value that best represents his expectation of going down here. And with that we solved the last potentially problematic situation. For now, as I told you, there are more advanced ways of exploration. Who imagines advancing on a giant map until he accidentally falls into a reward and learns a tiny little thing
21:52
? Here I made a 4x4 map, but imagine a 100% map? It's impossible. Also There are ways to update all the values on the map more quickly instead of one at a time. And then there's the biggest problem, which is transferring all of this to a continuous environment, which is how we work in the real world. It's as if we had infinite states in this case. So for that, there's the combination of Deep Learning with Reinforcement Learning, which is Deep Reinforcement Learning, or
22:23
deep reinforcement learning, which is still a hot research area today. Also, it's good to highlight that we only saw one Reinforcement Learning algorithm here, which is Q-Learning, but there are others. I focused on this one because I think it's the simplest and best illustrates the problem and the solution in general. Anyone interested can also take a look at the SARSA and Monte Carlo algorithms. And now let's get our hands dirty
22:47
and implement this, make it run. The algorithm you used from the code is this one here. So everything I talked about in class is summarized here. So, we 'll predefine the learning rate alpha, discount factor gamma, exploration rate epsilon, all between 0 and 1. I'll initialize all the Q values arbitrarily. In the examples, I initialized everything with 0, but we'll see that it's possible to do it with other values as well, which is quite interesting. Then I'll repeat this for each episode,
23:18
I'll put the agent in the initial state, and I'll repeat it for each step of the episode, each step the little robot takes on the map. I'll choose a random action A with probability epsilon, which will be exploration. Otherwise, if it doesn't fall within the probability epsilon, I'll choose action A with the highest Q value in state S, which is exploration. I execute action A, observe state S', which will be the resulting state where it falls,
23:46
and the reward it gains in this new state where it ended up. I apply that formula to update what? From the square where I came from, I update the current state to the new state. I do this until S is the final state. Or we could also set a limit on the number of steps to ensure that the agent doesn't get stuck in an infinite loop . So let's look at the code now. I 've already implemented it here, using two classes. It's in Python, and I'm using
24:16
Google Collab. For those who don't know, I'll leave the link in the description. It's basically an online Python interpreter that already has a lot of libraries installed, mainly for machine learning. Although I'm not using practically anything here, I'm only using the active random number library in Python, so I'm importing them here. Here I'm creating the `mapinha` class, which will be my environment. So I separated the environment and the agent, which could be used in other
24:44
environments if I wanted, or I could use other agents in this environment as well. So, I defined here that we can choose the width and height of the map, it already comes to the default 4x4, and we can set a probability of it tripping, which I set to the default 0. Then I call the reset, what does this reset do? It puts the agent back in the initial state, I'm telling it to put it here on the line that is height minus 1, that is, down there, in column 0, so it's the bottom left corner, no matter
25:11
the size of the map, it will always stay in the bottom left corner. And I'm returning a copy of the state here. Here's an interesting anecdote: when I was implementing this, I forgot to pass a copy of the state, and it ended up changing in other parts of the code and causing some strange bugs, but it only changed a few small values in the middle of the map, and the agent continued working, learning the best path. So this is a big problem for debugging machine learning, because by definition
25:39
in machine learning we are looking for approximate solutions, we tolerate errors. So it's difficult to know when your code is working or not, because sometimes there's a small error and you think, "Oh, it's normal for the algorithm," but sometimes it's a bug, and in this case there was a bug, I fixed it and it's working perfectly. With the `act` function, you pass an action to it and it will apply that action to the environment. So in this case I...
26:05
I'm saying that when the action is 0, it goes up, so I decrement the row. When the action is 1, it goes to the right. I've done it clockwise here; to the right, it will increment the column; down, it will increment the row; to the left, it will decrement the column. Here, the stumble probability randomly selects a number between 0 and 1. If it's less than the stumble probability I set here (which is 0 by default), then by default it won't
26:32
stumble. But I can put a value there, and it will start stumbling. So, if this random number is less than the probability of stumbling, it will add -1, 0, or 1 to each coordinate here. So we can go up, down, or diagonally. Walls, so here we don't go off the map, so I'm making it so that its line goes at most to a height minus 1 and at least 0, the column goes at most to a width minus 1 and at least 0. Finally, I'll define the reward and whether
27:06
the state is final, so I'm seeing here, for this environment I defined it like this: if the agent is in the last column of the map, which is W-1 here, in the first row, which is row 0, he will gain 100, it's the upper right corner, so it doesn't matter the size of the map, this will also work for any size, he will gain 100 reward and it's a final state. If he is in the last column in the second row, he gains minus 100 and the state is final. Note that I didn't put that extra reward in the lower
27:37
right corner, I only did our initial example that had a reward and a punishment. Then I return here again to the copy of the current state, how it is, the reward and this boolean here that says whether it's final or not. And this is our environment, it's ready. Now let's move on to Q-learning itself. So its constructor here has several parameters, we can define them, I've already put in standardized values here, but we can choose
28:04
epsilon, alpha, gamma, the initial value, the default is 0, the one where I'll fill in all the little numbers will be 0, map size, here's a detail, normally when we implement an algorithm like this, we don't think in terms of a map, we only think in terms of the number of states, it would be 16 here in this case, but to simplify the explanation I thought it best to put it in Q-learning itself, also separated by rows and columns. And the number of actions is 4, so I do a reset, what does it do on
28:38
reset? It initializes all the values in the Q table, which is my Qtable here. So I took the self-init function, created a list—in this case, since I have 4 actions, it will create a list with 4 values, 0 here for example—so I'll create a small list of 4 zeros for each column and then for each row. So I actually have a three-dimensional matrix here, rows by columns by action. This is just a little function to nicely color the table; we'll see how that works down below.
29:11
Here's another one to nicely color the policy; it will show the little map with the arrows. Here, `max kill`, `get max kill`, I pass it a position, a state—some places I called states, others I called positions, sorry. Here I called it a position. So I'm saying pass the row, pass the column to the table, this will give me a list with 4 values, 1 for each action, and I want it to return the largest of the 4 values, that's it. To get the best action, given a position, what will it do?
29:43
He's going to take the Qs from that position, there are 4 values, he's going to see which one is the largest of those 4, he's going to put it here in M, then I'm going to create a list with the best ones. So remember I said at the beginning that it's not enough to simply choose the best stock, if we have stocks with the same value we have to randomly select one of them, so that's why I'm doing this. I'm taking all the ones that have the same value,
30:07
which is the best, so let's say I have 100, 100, 0, 0, it will return the two stocks that have the value 100 here. And then I'm telling it to randomly choose one of these, it randomly chooses one of the stocks that has the highest value, if there is more than one tied it randomly chooses one of them. Get Random Action simply returns a random stock, so I put here for it to generate a random number between 0 and 1, multiply it by the number of stocks, which is 4, and convert it to an integer.
30:36
So, it will give a number between 0 and 3 here. Remember that this random number is between 0 and 1, with an open interval at 1, so it never gives 1. That's why I can convert it to an integer here; it stays between 0 and 3, it will never give 4. And the Get Action, which would be, let's say, its true policy, is the Epsilon Greedy here. So, I promise here, I will draw a number between 0 and 1. If it is less than the Epsilon,
31:02
which is the exploration rate, I return a random action; otherwise, I return the best action in that position. Finally, the Update here. The Update needs to know the previous state, the action, the new state, and the reward. And here is basically our formula. I 'm saying here that our Q value in that position, in that action, receives itself plus the learning rate alpha times the reward plus gamma times the highest Q value of the resulting state
31:36
minus the current value in that state, in that action. It's exactly the implementation of that formula. And lastly, here I have where I instantiate these classes and run my experiment. So I've defined here that I'll have 4 lines, Rows, Columns here, R and C. I'll run it for 100 episodes. My map here will be the little map, where the width will be C and the height will be R. My QLearn, I'm instantiating it here as well with width C and height R. I'm setting
32:07
alpha to 1, since we're going to start here as deterministic, we can leave the learning rate equal to 1, so it learns faster. And I'm putting a high exploration rate here, 0.5. So that means that half the time it will randomly select an action instead of choosing the best one. Then there's our loop that was in the pseudocode , for each episode it starts the agent at the initial position. For each step in the episode I've defined a limit of R times C steps. So in this case, in this 4x4 map, it
32:40
can move a maximum of 16 steps and then the episode ends. If he's trapped or something like that, it ends. The action receives the QLearn, Get Action, so it's the Epsilon Greedy, in the state I'm in. It returns the action I have to take. Then I'll apply that action to the map. And the map returns the new state where the little figure ended up, the reward, and whether it's a final state or not. Then I'll update my Q table,
33:10
update method, pass the state, pass the action, pass the new state, and pass the reward I received. I update my state now to the new state, check if it's final, break the loop if it's final. If I ended up in the final state, I can end the episode right here. And finally, I paint the Q table and the policy. Let's see what all this resulted in. Let's run it here. So first, here it's painting the Q table. You can see that I put the positions and the four actions here
33:38
. So we can see the values it learned here. Note that here 00 is the upper left corner. He's saying that upwards is 72, to the right 81, which we did in the example, it was indeed 81. Downwards 65, to the left 72. Why do upwards and to the left have the same value? Well, it's the upper left field on the map. So if it goes upwards or to the left, it hits the wall and stays in the same place. That's why they have the same value, they give the same
34:09
result. Then going down, we're seeing here that 03 is the reward. The first line, last column. It's all zeroed out. It's what I told you. It has no expectation of future. Second line, first column. He's saying that upwards or to the right gives the same result, which is also correct. On our little map, if we go up or to the right, it gives the same distance to the objective. Another interesting one to see is 23, which is the third line, last column. It's that little square below the trap.
34:42
So notice that it's saying that if I go up I get minus 100. It hasn't fully learned how I can tell here. It's telling me that if I go to the right it's zero. This here, to me, is a sign that it hasn't explored this action here. If I put more episodes up there, it will probably fill in this value. We can test it later. I can test it now too. I'll put 1000 here. Run it again. Look, it filled in. Sometimes when there are these missing zeros it's because they are actions
35:08
that it hasn't explored yet. So I have to give it more time to explore. But notice Well, I don't know, now it's capable of exploring even further. Yes, now I put 100 and it explored. Since it's random, there's no way to be sure. But notice that there are other places here with zero. But the interesting thing is that even if it doesn't learn all the correct values on the map, it learns enough to reach the objective. We can
35:29
see this here with the policy. Look here, up, up, up, right, right, right. It's here, it learned the best path. The rest is random, because this is an interesting thing that I didn't mention. In our problem, we always start the agent here in the lower left corner. But I could choose to place it anywhere on the map and it would work. Notice here, if I set it to start here, in this place, it goes to the left, up, up, right. If it starts here, left, up, up, up, right,
35:59
it also works. You can ignore these two, okay? Because they are the final states. So, since everything is at zero, it's showing a random arrow here. Because it doesn't matter, when you reach the final state you won't choose an action, the episode is over. So we ignore these two. But you can see that the rest of the policy is correct. It always reaches the reward. Let's see what we can test differently here. If I removed the exploration, what would happen?
36:23
Look, a lot of things are zeroed out. You'll see the policy here is all strange. Although it works. You can see here that if you start here , right, right, up, up, up, right. It even works. But the values are almost all zeroed out. It hasn't explored much. It hasn't learned much. In fact, if I leave the little character here, it will get stuck because it will keep going to the right here, hitting the wall. Here too, okay. So here we see that
36:50
exploration is essential for it to really learn all the values. Another thing I mentioned, right? We can start with a value instead of zero, we can put in a different value. What happens if I put 100 here? Everything is filled with high values. Notice that it learned the right path here, but in other places it's traveling, look, it's going to the left. Although it works too, okay. It's just not the best path, but it works here, look. It goes left, left, up, up,
37:17
up, right, right, right. It arrives, but it's a very bad path. What I wanted to show you about this initialization here? Because this is what we call optimistic initialization. It's when we put a higher value in the states, the initial value. What is the effect of this, right? The effect is that the agent will naturally be optimistic. It will think that the states it hasn't visited are good, the actions it hasn't taken are good, by nature.
37:42
So it's curious. It will start choosing actions it has never chosen because it thinks they are wonderful. So, it will update the values, and soon the value will decrease, and it will naturally lose interest in those actions. Therefore, performing an optimistic initialization is the same as implicitly performing an exploration, right? It works like exploration, as I managed to do here with Epsilon zero. But there's a catch in the implementation, right? You can see that there are values greater
38:06
than 100 here, which doesn't make sense. There's no way to earn more than 100 in this problem. The problem lies precisely in the final states, okay? Because since I initialized them with 100, the agent thinks that when it reaches the final state it still has the expectation of earning 100 in the future, but there is no future, the episode ends there. It's almost as if the agent believes in an afterlife. So, this can be corrected, okay? I had
38:28
already corrected it, but I removed it precisely to show you. So let's do it here. I'll put it in my update; it needs to know if the state is final, okay? I added an extra argument and put an if statement there . What did I do in this if statement? If the state is final, I'll simply remove this term here. This term is the one that's taking the expected future and multiplying it by gamma. I removed it and created the formula without it. So when the state
38:51
is final, I put the formula without the expected future; it's just the immediate reward. If If it's not the final state, it's the normal formula, okay? And then down here I need to pass the final state here, okay? Update. Let's run everything again. Look, now the numbers are correct, a maximum of 100, look. It maintained, right, the expectation of 100 in the final state, but it 's not using that now. My if statement was precisely to ignore this 100 here.
39:19
So you can see here that it learned, look. It learned correctly, look. It even learned the optimal policy here, look. It's always the shortest path. Except, except here in these two. Here it messed up. Here it hits the right wall, here it hits the bottom wall. So the exploration wasn't enough. I could put a 0.1 here in epsilon to compensate. Yes, then it learned this one, but not this one below yet, okay? What can I do? Ah, I only have 100 episodes, that's very little too.
39:46
Let's set it to 1000. Oh, it learned perfectly. I can even remove this epsilon here now. Oh, it learned perfectly here. So, with just the optimistic initialization, it can already explore enough to learn the correct values here. What else can I test here? Let's add a stumbling block here. I'll set a 10% chance of stumbling. Let's see what happens. I'll put my exploration back at 0.1 and remove the optimistic initialization, okay? So as not to mix things up. It looks quite strange. Notice the
40:18
whole policy is wrong here. There are arrows going to the left, down. It's completely lost, okay? So it's because of that. Sometimes it's stumbling and learning the wrong things. We need, then, as I showed in the slides, to decrease the alpha. Let's set it to 0.2 like in the slides. Let's see. It's almost solved. Actually, here it knows how to reach the end, but you can see that there are some underexplored regions. Here's where he goes
40:45
down and to the left, okay? But the rest here is correct. Here he's supposed to go to the left. Since I decreased the learning rate, to 0.2, it means he's learning five times slower, right? I'm going to increase the number of episodes here to compensate for that. Look, it's already improved. Now he's learned the correct policy here. Except for this part, which is suboptimal. Here he was supposed to go up, but at least
41:10
he's not getting stuck. Let's increase his exploration here too. Let's put it at 0.5. It's already improved. Actually, it's just this guy here. You can't even say it's wrong, because look how interesting. The normal policy in this position would be to go to the left, right? He goes around the trap, goes up and comes to the objective. But he understood that going to the left here is dangerous because he could fall into the trap.
41:37
He could trip and fall backward here. So, as a precaution, the policy has already incorporated that. It learned that it's better to go down and go around here from above. Although he passes by this side, right? Still dangerous. He could have learned to go a little more to the left. Look, I rotated it again and this is what I got. Now it makes more sense. When he's here, he's telling you to go left. Here, it could be down, right? Here he's not telling you to go up. He's telling you to go left
42:01
again because he's afraid of going up and tripping and falling here. So this strategy he learned here makes sense, considering he's tripping. Now let's enlarge this map. I'll make it 10x10. Quickly. You can see what he learned from above. Let's follow the path here. Right, up, right, right, up, right, up, right up right up up right up right up right up right up right up, right. He reached the end. He learned the path. For all of these here, I think
42:31
it's okay, because everything is up to the left. Here he's saying to go down because he's afraid of falling into the trap. Here he's going to the left, that's right. Here everything goes up, left, okay. Yes, here he could go up, but he preferred to go to the left. It's suboptimal here, but it's fine. It's reasonable. He learned reasonably well for a 10x10 map. I can still improve the exploration, put the optimistic analysis here.
42:56
Let's see. Again, the politics seem to be well learned, but I have the impression that this corner is better now. Everything is up. Only here, closer to the trap, It sends it to the left. But the rest is all sending it up or to the left. It used to work much better. Well, I think I've shown everything I wanted to here. I'll leave the code for this collaboration in the description as well, for anyone who wants to access the
43:20
code. Some interesting things that could still be implemented here would be perhaps a performance graph, to see over time how it learns. It would be possible to change what it learns so as not to use width and height, but only the number of states. Anyway, it's possible to implement other little maps, make a more generic map where I can place rewards and traps wherever I want. It would also be interesting for testing. There's a lot
43:43
to play around with here. So, that's it for today's lesson. Thank you very much!
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