-: Hello and welcome back to the course
on artificial intelligence.
Today, we're going to talk about the Bellman equation.
It's quite a complex topic
and we're going to introduce it in a step-by-step manner
throughout this whole section of the course.
So we're not going to just jump straight
into the most complex version
of the Bellman equation right away,
but instead, we're going to introduce it slowly
in order to gradually understand how it works.
And I hope you're cool with that approach,
if you are, let's get straight into it.
So, we're going to have a couple of key concepts
that we're going to be operating with.
And these concepts are, S stands for state.
So the state in which our agent is,
or any other possible state in which it can be.
A, represents an action that an agent can take.
So an agent can have access to a certain list of actions,
and actions are very important
when they're looked at in a state combination.
So when you're in a certain state
and then you look at actions,
then it starts to make sense
what's going to be the result of those actions.
Because if you look at an action by itself without a state,
doesn't really make sense
because you don't know where you are,
and where you can possibly end up in.
Then we have, we'll have R, which stands for reward.
And that's the reward the agent gets
for entering into a certain state.
And gamma is the discount factor.
And we'll talk about the discount factor in a second,
it all makes sense just now.
But just take a note, make a mental note,
that we are going to have this letter gamma,
that we'll be operating with later on.
So the person behind the Bellman equation
is Richard Earnest Bellman.
He was a applied mathematician,
and came up with the concept of dynamic programming,
which we now call reinforcement learning
or which we call the Bellman equation now in...
Well, that's what we call now.
And in 1953 he came up with that concept
and that's when the Bellman equation came to be.
So let's have a look at how this all works.
There's our lovely agent in the bottom left corner
and he is in a maze.
And this is quite a classical maze
where you've got some blocks,
the white blocks are blocks
in which the agent can step into,
the gray block is the one that is just not accessible
so that's like a wall in this maze.
The green is where the agent
should be aiming to end up in.
That's where we want the agent to go, that's the finish.
And the red is a fire pit.
So if the agent falls into a fire pit,
he will lose the game.
So in the fire pit, the reward, which is R, is minus one.
So that's our way of telling the agent,
"That's not something we want you to do."
Like remember an example of when we're training dogs,
we want to tell him like, "Bad dog,"
if it's not doing the right thing that we wanted to do.
Same thing here,
we want to tell the agent
that this is not something that you should be doing.
You shouldn't be ending up in the square.
So every time it doesn't end up in the square,
it'll get a minus one reward,
so it'll be punished with a minus one reward.
On the other hand, if it ends up in the green square,
it'll get a plus one reward,
meaning that that is what we wanted to do.
So those are the two rewards
that the agent can possibly get.
And how does it learn how to operate in this maze?
Just like in that example of the robot dogs
that learn to walk,
we just gonna let it know...
We'll just tell it that, "Here are the actions you can do,
you can go up, right, left or down.
Those are the four possible actions that you can take,
and that's it.
Have a play around with that,
see what you can come up with."
So the agent might go to the right,
then they might go to more to the right,
they might go back to the left,
they're just randomly pressing these buttons
and they're trying to see what happens.
Then they go back here,
they go up, go up, go down, go up, go right.
So for now, they haven't learned anything,
they just...
So far nothing's happened.
They go right and then bam, they end up in the green square.
So they realize, "Wow, I just got a plus one reward."
So as soon as they stepped into the green square,
they got a plus one reward.
And that triggers the algorithm to say,
"Okay, that's really cool.
I am rewarded for ending up in this square.
So I want to end up in the square."
So what does that mean for the agent?
That means it starts asking question,
"How did I get to the square?
What was the preceding state I was in,
and what action did I take to get into the square?"
And then it looks back and it says,
"Okay, so the preceding state was this one.
It turns out to be valuable in that state,
that one that's part of the red arrow
because from that state,
I'm just one step away from getting the maximum reward
I can possibly dream of, of plus one.
Like a biscuit for a dog.
As soon as I know, if I ever am in that state,
that square mark with the red arrow,
all I'll have to do is press right."
So how do I tell myself,
how do I remember that, that state is valuable?
Well, to me there's no difference, actually.
As the agent, there's no difference
in whether I am in the green square
or in the white square, right?
In the green square I get the reward of one,
so I'm going to mark for myself
that the white square for me, it has the value of one
because it leads exactly to reward one.
So as soon as I'm in the white square,
I know I'll just take one more action,
I'll be in the green square and I'll get a reward of one.
So that's why I'm going to say,
that the value of this square is equal to one
because it leads directly without any sort of subtractions.
As soon as I'm in here, I know my reward will be one,
so I'm gonna mark this square as V equal to one.
That's the value,
that's the perceived value of being in this state.
Next, the agent's going to be like,
"Okay, so how do I get into this square?"
And you know, he might walk around again, and so on,
end up in this square again and be like,
"Okay, how did I get into this square before that?
And the way I got into this square was from this square.
Interesting.
Okay, so as soon as I get into this square,
I know that all I have to do is go right.
And then from here I already know that I'm going to win.
I know exactly how everything's gonna unravel from here.
And I know the value of being in this state is equal to one.
And since there's no,
nothing is stopping me from going here, from here to here,
the value in this is going to perceived value.
I'm going to value being in here, as V equal to one as well,
because as soon as I'm in here,
and I'll be here pretty quickly, so I'm going to win."
And then how do I get into this square before that?
"Well, I got into this square from this square."
So the value, a similar approach,
the value of being here is also equal to one and so on.
So the value of being here is equal to one,
and the value of being here is equal to one
because each one of them leads to the next one
and leads to the finish line.
So that's all like pretty logical at this stage.
This is as pretty much designing
the Bellman equation right now.
So this is, we could possibly think about designing
an equation that helps an agent go through the maze.
So look at the reward, then the preceding state,
give it a value of equal to reward
the preceding state and so on.
So it kinda like creates this pathway.
It's all great and well, but the problem here is,
"Okay, what happens if our agent for some reason
starts in this state,
Instead of starting here and taking these actions,
but it actually starts in the state?"
How does it know?
How does it remember which action to take?
Should it go right or should it go down,
or should it maybe go left, or should it go up?
How does it remember
which is the next continuation from here,
if the only values it has is these values of equal to one?
So it cannot see what's further away.
It can only see, "All right, what I have here,
and what I have here."
How does it know which way to go?
Well at this stage, it doesn't.
It's pretty identical for the agent which way to go.
And so that's why this approach doesn't really work.
It's a very simplistic explanation.
Of course, there's much more to it,
but in an intuitive way that's why we cannot just assign,
just carry on this value backwards like that,
because one of the reasons is once the agent
is in between these two values, which way is it gonna go?
It can get confused like that.
And so how do we solve this problem?
What are we going to do here?
And this is where we're going to start introducing,
the Bellman equation in its actual form,
slowly, step by step.
So the Bellman equation looks something like this.
So we've already talked about V,
the value of being in a certain state,
S is your current state or any given state.
And there is S as well,
and S prime is the state, the following state,
the state that you will end up in after this state,
and by taking a certain in action.
But we know that there's many actions that a agent can take.
And that's why we've got this max over here.
So by taking an action, what will happen to an agent?
So let's say we are in state S,
by taking an action in state S, and we take action A,
what will happen is we'll instantly get a reward
by getting into a new state.
And remember that reward can be one or plus one or minus one
if it's at the end of the game,
or it can be a zero if it's throughout the game.
In this case, our reward throughout the game is zero.
So that's the reward.
Plus, we will get into a new state
which has value of S prime.
So that's the value of the new state and gamma.
We'll talk about gamma in a second,
but the point I'm trying to raise here
or the point I'm raising here is that,
we've got many different actions that we can take,
and that's why we've got the maximum.
So by taking action, we get reward,
plus, we end up in a new state.
And so for every out of the...
in our case, we have four possible actions,
for every one of the possible four actions,
we're going to have a equation like this.
So this is going to have a value for...
They will have a different value
for every one of the four actions.
And we're going to look at only the maximum
because, of course, the agent wants to take
the optimal state.
So if he's in state S, he's going to look at these values,
he's gonna look, find the maximum
based on the action and going to take that action
that leads to the maximum of these values.
So hopefully that makes sense,
why we're taking the maximum here.
Then once we've got the reward and the value of the state,
why do we have this gamma parameter here?
Well, it's there exactly to solve that problem of,
where the agent doesn't know which way to go
because it's comparing the values of two states
on both sides and they're the same.
That's why the gamma is called the discounting factor.
So we're going to have a look at that
in practice now to better understand it.
So let's take our formula,
we'll put it here on the top right
and now we will analyze what the values
of these different states are.
And every state here is a square nomate.
So any one of these white squares
is a state and we will going to calculate
the value of being in that state.
So let's start with this square,
what is the value of being in this state?
Well, we need to take the maximum
of this value across all actions.
And we know that this value is maximized
as we get closer to the finish line.
That's how it's constructed, and just by looking at,
you can see because, here's got the reward,
and here's got a discounting factor
multiplied by the value of the next state.
And it just makes sense,
that that's how we would construct that equation.
So it makes sense that from here,
the maximum of this value will be if we move to the right.
So, that's how we calculate the value of the state.
This value of this state is equals the maximum
or equals to this value if we move to the right.
If we take an action of moving to the right,
so what will this value be?
Well, the reward of moving to the right is equal to one,
and regardless of what gamma is,
we don't have a value in this state
because we are already in the best state possible.
So this is the final state,
it won't have a value, we just get a reward here
and that's the end of the game.
So the value will be of this maximum will be equal to one
and that's why value of state S here, is equal to one.
Now things get interesting when we move to the left,
when we move backwards a bit.
So now let's calculate the value of being in this state.
And for that, we're going to need gamma,
so let's say our discounting factor is a 0.9,
and it'll make sense what a discounting factor is,
once we calculate this.
So from here, just based on our intuition
and because we know how this maze is working,
how this maze works,
we know that the best possible action is go to the right
because from here we go here.
So that means a maximum will be be achieved
when in this state, you go to the right.
And so let's see what happens if we plug it in here,
so if you go from here to here,
you don't get any reward, it'll still be a zero,
but then you'll get gamma, so you get 0.9
times the value of the new state, which is one.
So in this case the value,
the whole result of this is 0.9 times one equals 0.9.
So that's our value, 0.9.
So if we calculate this now, you'll see that from here,
we know just by looking at the maze,
we know because we as humans,
because we're understanding how this equation works,
of course, and an AI,
the agent would have to experiment with these things,
but because we have like a crystal ball,
we can see this whole maze,
we have like the bird's eye view right now,
we know that the best action's to go to the right.
So if we plug it all in here, it'll be zero, no reward,
plus 0.9 times the value in this state 0.9, is 0.81,
and so on.
So here it'll be 0.73 and here it'll be 0.66.
So you can see that the way the discounted factor works
is it discounts the value of the state
as you are further away.
So if you are familiar with finance theory,
then it's something similar to time value of money.
Like what would you...
Think about it this way.
What would you prefer to have $5 today
or $5 in 10 days from now?
Just if somebody was to give you a choice
I will give you $5 today
or I'll give you $5 10 days from now.
Well of course you would choose $5 today.
Why is that?
Well, because you can take those $5
and you can invest them at a certain interest rate,
which is very similar to gamma
and your $5 in 10 days will actually grow into maybe $5.73,
or something like that.
And that's how time value of money works.
And very similar concept here.
And the important thing to understand here,
this is just a theory,
a way that reinforcement learning works.
So Richard Bellman came up with this equation
and from then, now that's how we use it.
So you could go ahead and come up with a different equation.
It doesn't have to have gamma,
it might have some other factor,
it might not even have a factor
but this approach works and that's why we're using it.
And this is what it visually looks like.
So the further away you are,
the less value of this being in this state.
And in terms of time value of money,
if I could say to you, "Where would you rather be?
Would you rather be here, would you rather be here?"
You'd say, "I would rather be here."
So we're creating that same phenomenon
as in time value of money.
We're artificially creating it through gamma
so that in order to incentivize agents
or inspire agents to be closer to the finish line.
So if an agent were to be asked,
"Would you rather be here or here?"
Because of the way this equation works,
it would choose to be here.
There's nothing more to that, nothing less.
It's not something that the world works this way, no.
It's just something that we're artificially creating
in order for our agents to understand
that this is good, this is good, this is good.
They're all good, but this one is better than this one,
and this one is better than this one,
and this one is better than this one.
And that way, you can see the old agent can see
in which direction needs to go.
So you can see that if I'm standing here,
remember that problem that we had
or was he standing here?
Yeah, so if he's standing here, do I go down
or like, if I'm standing here, do I go up or do I go down?
Well, now it's not a problem anymore
because you can see that it's actually better to go up
because the value is bigger here.
And then from here is better to go right,
because the value is bigger here than here.
And then from here is better to go right,
because the value here is bigger than here, than here.
And then from here he already knows
that he needs to go right
because he'll get a reward here of one.
So that's how this whole approach works.
Now let's have a quick look at the rest of the square.
So how do we calculate the value in this square?
Well, here is where things get a bit tricky.
So from here, you might not actually go left, right?
You might actually go right.
So we can't just keep going like that
because it might actually be shorter to go this way.
So what we're going to do,
is we're going to calculate the value in this square first.
And because obviously from here the best way is to go is up.
Again, that's because we see the crew,
we have the crystal ball, we can see things.
And you'll see further down in this section,
you'll see how the agent actually explores this,
understands this like through experimentation.
But for us we know that it's better to go this way
so we're going to calculate the value here
and that's why we're going to calculate
the value in this square first.
So, here we have three possible actions,
in reality, we actually have four.
We can also go left,
the agent could hypothetically press left
and bump into the wall and stay here.
But for simplicity's sake we're just going to show
the actions that we knowing what we know
and having the crystal ball we know
which actions are the ones actually to lead to something
other than the same state again.
And so from here, we know that the...
Again, just because we have a crystal ball
we know that the best way to go is this way.
An agent, of course, would have to experiment
and find the best way.
And you'll see how that happens,
further down in this section,
you'll see actually how an agent walks around
and how you would experiment trying to find these values.
But for us, we know it's that way.
So here if we plug everything in one,
so the maximum, the best output is when you go up,
here is a one 0.90, so you plug that in, you get 0.9.
Okay, so we calculate that one.
Let's calculate this one, same approach.
You have three ways you can go,
actually four for the agent,
but for us we can see it's only three.
So 0.81, from here you have 0.73,
and it actually ties in nicely with this value
because if you discount again, you get 0.66.
And here you have 0.73 because this is the optimal route.
So there you go.
That is the values all of these states.
And now you can see that
because we've created this equation,
we've created synthetically this whole concept
of the closer you are to the finish line,
the more valuable that state is.
Now, because we've created that, now it's pretty obvious
for the agent which way it should go.
And we'll talk more about that in the coming tutorials.
I hope you enjoyed today's session.
And I know it's a bit...
it might sound a bit very basic at this stage,
but as we go through this section
we will add a bit more complexity to it.
At the same time, if you cannot wait,
if you wanna jump into it,
then there's a paper which you can look at
and it is the original paper by Richard Bellman,
it's called "The Theory of Dynamic Programming" from 1954.
And you can find it at this link.
And there you go.
So you can jump straight into it
and read from the author of the Bellman equation.
But just bear in mind that
this is quite a mathematically heavy paper.
And on that note, I look forward to seeing you next time.
And until then, enjoy AI.