Hello and welcome back to the course on artificial intelligence.
And today we're talking about Mark of decision processes or M.D..
Let's have a look what we've got today.
So last time we stopped on the concept of a map.
So because we've calculated the values based on the Belman equation we can derive this map for our agent
on this maze.
And basically what that means is wherever the ange a agent starts let's say it starts over there.
It knows exactly which steps to take in order to get to the finish line so it just goes up up right.
Right and done.
And so the question here is is that it.
Is it really that simple.
Is reinforcement learning really that you know for the lack of a better word boring.
It's it's yeah.
Once you have the math that's it all you have to do is you've done it just full of them.
Well the reality is that it's not actually that simple.
And that's a good thing because it makes this course more interesting for us and we can actually solve
much more complex problems.
So this is where a mark of a process is coming.
But first we're going to talk about two things.
We're into it deterministic search versus non-deterministic search.
So let's talk about the concept of deterministic search.
This is our agent in the maze and deterministic search means that if the agent decides to go up then
what will happen is 100 percent probability it will go up.
That's exactly what will happen.
There's no other options.
Once once it says go up or click the up arrow it'll go up.
There's no other options.
Now on the other hand nondeterministic search is when our agent says it wants to go up.
They are actually couple of options.
For example there could be three options and we're going to look an example where there are three options
but it doesn't have to be a limit to three before it could be different depending on depends on the
problem the randomness could be different but in our case it could be three options with an 80 percent
chance he does go up.
But then with a 10 percent chance when he wants to go up he'll actually go to the left just because.
Because that's how the environment works that's the world that he lives in.
And with another check in 10 percent chance he'll actually go right.
And in this case he'll fall into the firepit.
So that is how it all works.
That's an example of a nondeterministic sure search a stochastic process and what the point of this
is is to make a more realistic model of what could actually happen in a real world in a real world type
of problem because very rarely do you get situations like this when you do something and it happens
exactly that way.
And even if you think about it in terms of games let's say you've got an agent playing Pac-Man.
Well not always is it the case that if he's standing in the square he goes up.
He will get the same exact result every time.
Well he will indeed go up but it may be in one case you won't get eaten by a ghost in either case.
He will get eaten by a ghost.
So as you can see there's some randomness to it because it depends on how the ghosts are moving and
they don't always move the same way.
They don't always start in the same locations.
So it's very logical is very fair that there is some randomness there's something that is not under
the control of the agent and that is this is just a way for us to present that in order for us to learn
how we can deal with it and how that affects a Belman equation how it affects the whole reinforcement
learning process.
But at the same time the randomness is of course not limited to if you go up there's a 10 percent chance
you'll go right or temp's and just go left or if you go down to 10 percent chance you go right or left
or you're right there's a 10 percent chance an up or down subtle limited to where you're going to end
up sometimes you might have a problem that is exactly.
Sometimes the possibilities might be different.
Sometimes the randomness might boil down to something else it might be boiled down like that example.
Pacman ghosts eating you are not eating you or it might boil down to something different.
For instance like there's there's like if the agent is playing Doom and then there's something like
a monster which is going to shoot him in one case and other cases there's like there's a probability
if we should all get shot and we won't get shot.
And so and so something that is out of the control of the agents is something I cannot predict.
That's what we are modeling here in nondeterministic search and this is where we have directly approached
two new concepts a mark of processes and or a mark of process and a marker mark of decision process
so let's have a look at these.
And you know how much I don't like to put definitions and lots of text on the side.
But in this case it is necessary for us to go through that.
So let's have a look a stochastic process has a mark of property.
If the conditional probability distribution of future states of the process conditional and both past
and present state depends only upon the present state not on the sequence of events that preceded it.
A process with this property is called a marker.
Very complex definition and it kind of like you introduce a little bit not only contradicts itself but
feels like it contradicts itself so here it is conditional for positive presence that depends on your
point.
But at the same time it only depends upon the present state.
So don't get too bogged down in that.
I'll I'll break it down in simple terms so a mark of property is when your future states.
So not just your choice but the whole thing.
Your choice and the environment it will only like the results of all of the of the action you take in
that environment will only depend on where you are now.
It will not depend on how you got there.
And that's it.
So that's a matter of public and a process which has this property is called the market process.
So to put it into an example so if your agent is here and if he goes if he decides to go up he might
go.
He in our case in our nondeterministic search example he actually might go left and right.
All right.
That's because we have that stick a this city inside our environment we have that randomness inside
our environment.
So any one of these things might happen.
But the key here is that this is a mark of process because we don't care how you got here.
He could have come from the top ended up here he could have come from the left and that up here you
could come from the bottom and end up here.
He could have like play a moved around here like 100000 times and then got here.
It does not matter what happened before only what matters is which state is he in now.
And so the the probabilities of going left or right or up they will always be the same if he's in this
state now.
And so that's basically just saying it doesn't matter what happened before we're here now.
This is the state you're in.
And don't forget that state doesn't just mean where he's standing.
The state is the state of the whole of the whole of the agent in the environment so is there like monsters
on the right or the monsters on the left or you know is the ghost coming from a top or bottom whatever
state you're in now.
Doesn't matter how you got there doesn't matter how and how it all came to be that you're there in that
state.
Now what will happen in the future is only determined by the state you're in now.
Plus the actions you will take them plus of course the randomness that is overlaid on top of that.
So that's a mark of process and a marker decision process or an MVP or marker decision process.
Provide a mathematical framework for of modeling decision making in situations where outcomes are partly
random and partly under control over decision making.
So important to understand that mark of decision process processes are different and different whole
concept mark of process to mark of process.
There are like a mathematical framework so.
But at the same time I thought it was important for us to understand what a mark of process is because
I think it still helps in understanding of mark mark of decision process and so a mark of decision process
is there.
This is exactly what we've been discussing Up till now so that the agent lives in this environment where
he has control like him previously and had full control of what's going on but now it has a little bit
less control.
It can decide to go up but it actually knows.
OK so if I go up there's an apes chance I'll go up this attempts and chances go left and chance will
go right.
So not everything is fully under its control.
There is some randomness in this environment and that's exactly what a mark of decision process and
Markov decision process is the framework that the agent will use in order to understand what to do in
this environment.
So we've got an environment with some toxicity some randomness.
And now the agent has to choose for instance should go up down left or right.
He has to make that decision.
He doesn't know what to do.
And in order to make that decision is going to apply a framework is going to be using a mark of decision
process in order to make that decision what what's going to happen where it's going to go.
And so basically this environment that poses this problem it is referred to the mark of decision process
so it's the framework the agent using at the same time the environment is referred to that the agent
is operating in a market decision process environment.
And so basically here we have two concepts we've got the mark of process is the way this environment
is designed that the PA does the work.
What happens from where you are now doesn't depend on the past.
And that same time we've got the mark of decision process is the framework that the agent is going to
be using in order to solve this environment.
And the good news is that the mark of decision process or that framework that we're talking about is
actually just an add on to our Belman equation question is the Belman equation but just a bit more sophisticated.
So let's have a look at that.
This is our Belman equation so far.
It's the maximum of all possible actions.
So the value of being in a state is the maximum of all possible actions that you can take from that
state.
The maximum is taken from the reward that you would get by taking that action in that state plus a discount
factor times the value of the next state which is as prime.
So that's what we've had so far.
Now because we have some randomness in our whole process this this part will change because we don't
actually know which state will end up and we don't know what s prime will be will it be if we're going
up will it be up or will be left will be right so we actually have to place this with the expected value
of the next date.
So here we're going to replace this so there's three possible states we can end up in.
And so we're going to replace that with some value that state has a value of as one prime.
That it has a view of as prime to prime.
And this state has a value of the of us three Bryne.
So now we're going to multiply the state that we actually are intending to go into by 80 percent because
that's how probability of getting to that state plus the probability of getting to this state is 10
percent plus people getting in-state So this is just our expected value so if from statistics if we
take the expected value of getting into the state that we'll get into these are kind of like the average
What's the average of what we'll get and then we replace that over here.
Then we get this aggression and it jumps very quickly just because there's a big but if you look at
it carefully you'll see the same thing said about Max here Max here.
Then you've got r of S and A R of S and they you've got gamma you've got gamma.
And then finally here you've got v.
So you knew exactly it was a deterministic search you knew which states you'll get into.
Now you don't know which state you'll get into since that of taking V.
You're taking the expected value of the state you'll get into or of the future state or just in simpler
terms you're just taking the average of what you will getting into.
So you know like it was like for 30 plus 3 percent chance it will be like this Plus's divide by three
basically.
But in this case it's not it's not exactly like average average.
It's it's a weighted average because of the probabilities here.
So here you've got the probability of it when you're in this stage to take this action of getting into
state as prime time the value of s prime and some to cross all these primes that you could possibly
get into who we are.
So exactly what we had three here one two three.
Add them up multiply these add them up.
Same here.
One two three.
Multiply them by the probabilities and add them up.
And that is your new Belman equation.
Congratulations.
This is what we're going to be working with going forward.
And that is the framework that is used in of decision processes so that is the framework that solves
this.
That agents used to solve this whole stochastic nondeterministic search problem where there's random
events that are happening that they cannot control.
So it's it's much more complex.
But as you can see because we've built up slowly to it.
Now we already know about this we know about.
There's worry about this.
We know about this.
We know what they are.
So all we did is we just introduced this part over here because there are probabilities involved in
the action or the consequences of your action on nondeterministic they are based on probabilities.
And so there we go.
That's how a marker of decision process works and the underlying equation behind it.
Once again it is something that is more like more closely resembles real world problems real or Sinatras
or even game scenarios because not everything is straightforward.
There is some randomness of all involved and not always will taking an action in a certain state will
always Nawal not always will it lead to the same outcome.
And so this is what we're going to be dealing with going forward and that's going to make things way
more interesting.
So hopefully you're excited for that and excited to see what's going to come next.
And in the meantime I found a really cool paper for you to have a look at this time.
It's a very applied paper.
So this one is actually really interesting to read through.
It's called a survey of applications of Mark of decision processes proces and it was written by white
in 1993.
There's the link and Ill show you examples of where Markov decision processes actually are used to model
real life Sinatras I think I was very excited by this.
I was impressed by some examples of population harvesting for instance.
So let's say you have some fish and you know what the population of fish is you need to decide how many
fish can we fish out this year and what.
So that's your current state.
That's the action that you're taking How many can we've shot at this year.
So what are the up what are the possible outcomes of that.
How many fish will we have next year.
How many fish will we have the year after and the year after and so on.
And it's not deterministic because it's not like if you take it at an hour and 90 percent of the population
the next year you will have you know back to 100 percent is not not exactly sermonising.
There are certain random factors involved which are out of our control and therefore we have to understand
what's what's going to happen we have to model what's going to happen that's where a market decision
processes agriculture.
There's an example like something like harvesting crops how much crops do we harvest how much money
do we not harvest.
Another one which I looked at finance and investment like an insurance company needs to decide how much
of its funds it will invest in any I think day or year or some period of time and there are those certain
factors are of his control.
For instance you know the market movements it doesn't know what can happen so it needs to actually model
that somehow.
A mark of decision processes used for that.
So here you can see lots and lots of examples.
And this is the number of examples given I think for each one.
And so you know even sports examples for sports and epidemics and motor insurance claims inspections
and maintenance and repairs it's also very interesting.
Have a look at that.
Just to give you an understanding of hey this is not just all made up stuff hypothetical The Matrix
type of thing.
This is actually the real world scenario so Ill give you a better understanding and this is what we
talked about in the promotional video for the scores that or the description of the course that we're
going to inspire you and your intuition to give you ideas for how to use AI in real life.
This is your opportunity.
Look at this paper to understand.
OK so we're going to be dealing with mark of decision process going forward.
That's really cool what do they look like in real life and this possibly could trigger some ideas for
you how you could apply in the future to make the world a better place and we'd be super happy about
that.
We'd be happy if you could use what you learn in this course to make the world a better place.
How fantastic with that.
So on that note I hope you enjoyed today's tutorial.
I look forward See you next time.
And until then enjoy AI.