Hello and welcome back to the course on artificial intelligence.
Today we're going to talk about the Belman 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 I'm not going to just jump straight into the most complex version of
the Belmont equation right away but instead we're going to introduce it slowly in order to gradually
understand how it works.
And I hope your goal with that approach if you're G.R. 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 states so the state in which our agent is or any other possible state in which it can be
a represents an action that a 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 swing state and then you look at actions and it starts to make sense what's going
to be the result of those actions because you'll look an action by itself or a state doesn't really
make sense because you don't know where you are and where you can possibly end up and then we have we'll
have our Which stands for reward and that's through ward that 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 all make sense just now but they're just taking
notes.
Make a mental note that we are going to have this letter Gamelin that will be operating with later on.
So the person behind the bellman equation is Richard Ernest bellman.
He was a flight mathematician and came up with the concepts of dynamic programming which we're now which
we now call reinforcement learning or which we call the Belman equation now.
Well that's what we're called now.
And in 1953 he came up with that concept and that's when the Belmont Belman equation came to me.
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 wide blocks are blocks in which the agent can step into the gray
block is the one one that is just not accessible says like a wall in this maze.
The green is where the agent is should be aiming to end up in that's where we want the agent to go that's
the finish.
And the red is firepits or the engine falls into the fire pit.
He will lose the game.
So in the fire pit the reward which is R is minus 1.
So that's our way of telling the agent that's not something we want you to do.
Like remember in the example of when we're training dogs we want to tell them like bad dog if it's not
doing the right thing that wanted to do same thing here we're one 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 happen the
squirrel get a minus one reward so you'll be punished with minus one reward.
On the other hand if it ends up in the Green Square it will get a plus one reward meaning that that
is what we wanted to do.
So those are the two rewards that the agent can't possibly get.
And how does it learn how to operate in this maze.
Just like in that example of the robot dogs that learned to walk which is going to let it know it will
just tell it that here the action you can do.
You can go up right left or down those are four possible actions that you can take and that's it.
Have 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 two more to the right they might go back to the
left just randomly pressing the button and they're trying to see what happens and they go back here.
They go up go up go down go up go right.
So for now they haven't learnt 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 awar So as soon as I stepped into the Green Square they got
a plus one reward.
And that triggers the algorithm to say OK that's really cool.
I am rewarded for ending up in the square so I want to end up in the square.
So what does that mean for the agent.
That means it starts to ask the question how did I get to this square.
What was the preceding state I was in and what action that I take to get to square and then looks back
and says OK so the preceding state was this one.
It turns out to be valuable in that state.
The one that spark of the Red Arrow.
Because from that state you're I'm 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 from as soon as I know if I ever am in that state.
That square marked with the Red Arrow.
All I have to do is press right.
So how do I tell myself to 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 Y Square is got for me it has a value of 1 because it leads
exactly to reward one 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 or one so that's why I'm going to say that the value
of this square is equal to one because it leads directly to if on any sort of subtractions as soon as
I mean here I know my reward will be one so I'm going to mark this square as the call to one that's
the value that's the perceived value of being in the state.
Next the agent's going to be OK.
So how do I get into this square.
And you know he might walk around again and so on.
And up in the square again and be like OK how did I get into this square before that.
And the way I got into this square was from this square.
Interesting.
OK 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 is going to 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 growing from here to here the value in this is going
to a perceived value I'm great value being in here as a vehicle to want as well because this is I mean
here I know.
Be here and I'll be here pretty quickly.
So I'm going to win.
And then how do you get into this square before that.
Well I got into this square from this square.
So the value is 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 value of being here is equal to one because each one of them leads to
the next one and these to the finish line.
So that's all like pretty logical at this stage.
This is us pretty much designing the Belman 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 proceedings and
so those are kind of like creates a pathway is all great and well but the problem here is OK what happens
if our agent for some reason starts in this state instead of starting here and taking these actions
and that 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 maybe go left or should go up.
How does it remember which is the next continuation from here.
If the only values it has is these values are equal to once it kind of 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 as pretty identical for the age and 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 Agent is in between these two values which where is it going to go.
It doesn't it can get confused like that.
And so how do we solve this problem what are we going to do.
And this is where we're going to start introducing the Belman equation in its actual form slowly step
by step.
So the Belman equation looks something like this.
So we've already talked about the value of being in a certain state as is your current state or any
given state and there is as well.
And as Prime is the state the following state the state that you will end up in after the state and
by taking concerted action.
But we know that there's many actions and 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're in state as by taking an action
in state assets and we take action.
What will happen is will 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 it in a second.
But the point I'm trying to raise here or the point I'm raising here is that you'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 move out of the in our case before our possible actions for every one of the possible
4 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 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 going to find the maximum based on the
action and going to take that action that needs the maximum of these values.
So hopefully that makes sense why we're taking the maximum here.
Then once we got the reward and the value that said why do we have this Gabaa parameter here.
Well it's there exactly to solve that problem of where the agent doesn't know which way to go because
it cannot.
It's comparing the values of two states on both sides and they're the same.
That's why the gamblers called the discounting factor so we're going to have a look at that and it better
understand.
So let's take a formula I'll put it here on the top right.
And now we will analyze what the values of the different states are.
And every state here is a square.
No.
So one of these any one of these white squares is a state I mean we're going to calculate the value
of being in that state.
So let's start with the 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 represents is maximized as we get closer to the finish line and that's how
it is constructed and by 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 values that this value of this state is he calls 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 1.
And regardless what color gamma is we don't have a value in the state because we are already in the
best state possible.
So this is the final stage.
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 1.
And that's why value of state as here is equal to 1.
Now things get interesting when we move to the left when we move backwards a bit.
So now is calculate the value of this of being in this state and for that we're going to need Gabaa.
So let's say our discounting factor is a zero point nine and it makes sense what a discounting factor
is once we calculate that.
So from here just based on our intuition and based because we know how this is working how this works.
We know that the best possible action is go to the right because from here we go here.
So that means the maximum will be achieved 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 in your reward will be zero.
But then you'll get camis who get zero point nine times the value of the new state which is one.
So in this case the value the whole result of this is 1 times a 0.9 times one equals 2.9.
So that's all values per.
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 an AI 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 go to go to the right.
So if we plug it all in here it'll be zero no reward Plus the report nine times the value in the state
0.9 is zero point eighty one and so on.
So here it'll be 0.23 and he'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 five dollars today all you $5 10 days from
all.
Of course you would choose $5 today.
Why is that.
Well because you can take that $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 dollars and 73 cents 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.
So Richard Belman 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 Gamla it might have some other factor might not you know have a factor.
But this approach works and that's why we're using and this is what it looks like so the further away
you are the less value of it being in the state and in terms of time and 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 that same phenomenon as 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 this is good this is good this is good old good but this one is better than this one and this one
is better than this one and this one has been in this one.
And that way you can see all the agent can see in which direction needs to go.
So it can see that if I'm standing here remember that problem that we had or was he standing here so
if you standing here do I go down or if I'm suddenly here to go up or do I go down.
Well now there's not a problem anymore because he can see that it's actually better to go up because
the values are here.
And then from here he's got to go right because the value is bigger here than here.
And then from here is Bertschi go right because the value here is bigger than you know.
And 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 tricky.
So from here you might not actually go left right you might actually go right so we can 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 the square first.
And because obviously from here the best ways 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 the section you'll see how the agent actually explores this understands this on their likes
through experimentation.
But for us we know that it's better to go this way so we're going to calculate 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 set which is going to show the actions that we knowing what we know and having the
crystal ball we know which actions are the ones actually lead to something other than the same state
again.
And so here from here we know that 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 the 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.
And here is a report 9:0 So you put that in.
You get zero point nine.
OK so it Kalika that one that calculate this one.
Same approach.
This is you have three ways you can go.
Actually four for the agent but for us we can see it's only three.
So zero point eighty one from here you have ZERO point seventy three.
And it actually ties in nicely with this value because in you if you discount again you put 66 and here
you have 0.23 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 or we've created synthetically this whole
concept of the closer you are to the finish line the more valuable that state is not because we're afraid
that now it's pretty obvious for the agent which way it should go.
And we'll talk more about that in the coming.
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 want to jump into it then there is a paper which you can
look at and it is the original paper by Richard Belman.
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 Belman equation.
But just bear in mind that this is quite a mathematically heavy paper.
And on that note I'll look for your next.
And until then enjoy AI.