-: Hello and welcome back to the course
on Artificial Intelligence.
And today we're talking about Markov decision processes
or MDPs.
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 Bellman equation,
we can derive this map for our agent on this maze,
and basically what that means is wherever the agent starts,
so 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...
Once you have the map, that's it.
All you have to do is, you're done, you just follow the map.
Well, the reality is that it's not actually that all 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 Markov process is coming.
But first we're going to talk about two things,
we're gonna talk about 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,
with a hundred percent probability, it will go up.
That's exactly what will happen. There's no other options.
Once it says go up or clicks the up arrow, it'll go up.
There's no other options.
Now, on the other hand, non-deterministic 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 be looking at an example
where there are three options,
but it doesn't have to be limited to three,
it could be four or it could be, you know,
it depends on the problem.
The randomness could be different
but, in our case, there could be three options.
With an 80% chance he does go up.
But then with a 10% 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 10% chance, he'll actually go right,
and, in this case, he'll fall into the fire pit.
So that is how it all works.
That's an example of a non-deterministic search
a stochastic process.
And what the point of this 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 this square, he goes up,
he will get the same exact result every time.
He will indeed go up,
but it may be, in one case, he won't get eaten by a ghost,
in another 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 is very logical, it's very...
It is fair that there is some randomness.
There's something that is not under the control
of the agent.
And this is just a way for us to represent that
in order for us to learn how we can deal with it
and how that affects the Bellman 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% chance you'll go right,
or 10% chance you go left,
or if you go down,
there's a 10% chance you go right or left,
or if you go right, there's a 10% chance you go up or down.
It's not limited to where you're going to end up.
Sometimes you might have a problem
that is exactly like...
Sometimes the probabilities might be different.
Sometimes the randomness might boil down to something else.
It might be boiled down, like in that example of Pac-Man
of the ghosts eating you or not eating you,
or it might boil down to something different,
for instance, like there's...
if the agent is playing Doom
and then there's something like a monster
which is going to shoot him in one case,
and another came, there's a probability
with which it will get shot
and with which it won't get shot, and so on.
So something that is out of the control of the agent,
something that it cannot predict,
that's what we are modeling here
in non-deterministic search.
And this is where we have directly approached
two new concepts, Markov processes, a Markov process,
and a Markov 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 texts on the slides,
but in this case, it is necessary for us to go through them.
So let's have a look.
A stochastic process has the Markov property
if the conditional probability distribution
of future states of the process,
conditional on both past and present states,
depends only upon the present state,
not on the sequence of events that preceded it.
A process with this property is called a Markov process.
Very complex definition and it kind of like... (stutters)
A little bit, not contradicts itself,
but feels like it contradicts itself.
So here it says, "Conditional both on the past
and the present states.
Depends only upon, but at the same time,
it only depends upon the present state."
So don't get too bogged down in that.
I'll break it down in simple terms.
So a Markov 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 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 Markov property.
And a process which has this property
is called a Markov process.
So in, 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, in our case,
in our non-deterministic search example,
he actually might go left and right, or the right,
that's because we have that stochasticity
inside our environment,
we have that randomness inside our environment.
So any one of these three might happen,
but the key here is that this is a Markov process
because we don't care how he got here.
He could have come from the top, ended up here,
he could have come from the left, ended up here,
he could have come from the bottom, ended up here,
he could have like play,
moved around here like 100 thousand 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 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
doesn't matter what happened before,
we are 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 agent
in the environment.
So is there like monsters on the right
or are there monsters on the left,
or, you know, is the ghost coming from the top
or from the bottom?
Whatever state you're in now,
doesn't matter how you got there,
doesn't matter how it all came to be
that you are 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,
then plus, of course, the randomness that is overlaid
on top of that.
So that's a Markov process.
And a Markov decision process or a MDP,
or Markov decision processes,
provide a mathematical framework
for modeling decision making
in situations where outcomes are partly random
and partly under control of a decision maker.
So, important to understand, that Markov decision processes
are different hold concept to a Markov process.
They're kind of like a mathematical framework, so...
But at the same time I thought it was important for us
to understand what a Markov process is
because I think it still helps in understanding
of a Markov decision process.
So a Markov decision process
is exactly what we've been discussing up 'til now.
So that the agent lives in this environment
where it has control,
like remember previously,
it had full control of the of what's going on,
but now it has a little bit less control.
It can decide to go up, but it actually knows,
"Okay, so if I go up, there's an 8% chance, I'll go up,
there's a 10% chance on the left,
10% chance I'll go right."
So not everything is fully under its control.
There is some randomness in this environment
and that's exactly what a Markov decision process is.
A 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 stochasticity,
some randomness, and now the agent has to choose,
for instance, should go up, down, left, or right.
It has to make that decision. It doesn't know what to do.
And in order to make that decision,
it's going to apply a framework,
it's going to be using a Markov decision process
in order to make that decision,
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 Markov decision process.
So it's the framework that agent using,
at the same time the environment is referred
to that the agent is operating
in a Markov decision process environment.
And so basically, here we've got two concepts.
We've got the Markov process,
is the way this environment is designed
that the part of the...
What happens from where you are now
doesn't depend on the past. And then at the same time,
we've got the Markov 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 Markov decision process
or that framework that we're talking about
is actually just an add-on to our Bellman equation,
is the Bellman equation but just a bit more sophisticated.
So let's have a look at that.
This is our Bellman 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 was 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 S prime.
So that's what we've had so far.
Now because we have some randomness in our whole process,
this part will change
because we don't actually know which state we'll end up in,
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, or will be right?
So we actually have to place this
with the expected value of the next state.
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 S one prime,
that state has a V of S prime two, S two prime,
and this state has a value of V of S three prime.
So now we're going to multiply the state
that we actually are intending to go into by 80%,
because that's our probability of getting into that state,
plus the probability of getting into this state,
10% plus probability of getting in this state.
So this is just our expected value.
So if, from statistics, we take the expected value
of the state that we'll get into,
so we're 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 equation.
Now it jumps very quickly
just because this equation is bigger,
but if you look at it carefully,
you'll see it's exactly the same thing.
So you've got max here, you've got max here,
then you've got R of SNA, you've got R of SNA.
Here, 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 state you'll get into,
now you don't know which state you'll get into,
since instead 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'll get into.
So, you know, if like it was a in a 33% chance,
and it'll be, like, this, plus this, plus this,
divided by three basically.
But in this case, it's not exactly, like, average, average.
It's a weighted average
because of your probabilities here.
So here you've got the probability
of, when you're in this state, you take this action,
of getting into state S prime
times the value of S prime and summed across all S primes
that you could possibly get into over here.
So exactly what we had, three,
here, one, two, three,
add them up, multiply by probabilities,
and add them up, same here.
One, two, three, multiply them by probabilities,
and add them up.
And that is your new Bellman equation.
Congratulations.
This is what we are going to be working with, going forward.
And that is the framework that is used
in Markov decision processes.
So that is the framework that solves this...
that agents use to solve this whole, stochastic,
non-deterministic search problem
where there's random events that are happening
that they cannot control.
So it's much more complex,
but, as you can see, because we built up slowly to it,
now we already know about this,
we already know about this, we already know about this,
we know about this, we know about this.
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.
And on deterministic,
they are based on certain probabilities.
And so, there we go.
That's how a Markov decision process works
and the underlying equation behind it.
Once again, it is something
that is more closely resembles real-world problems
real world scenarios, or even game scenarios,
because not everything is straightforward.
There is some randomness involved
and not always will take in an action in a certain state,
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 gonna 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's actually really interesting to read through.
It's called "A Survey of Applications
of Markov Decision Processes,"
and it was written by White in 1993.
There's link and it'll show you examples
of where Markov decision processes
actually are used to model real-life scenarios.
I was very excited by this,
I was impressed by some examples.
So population harvesting, for instance.
So, let's say, you have some fish
and you know what the population of the 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 fish out at this year
so 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 out,
I don't know, 90% of the population,
then next year, you will have, you know, back to a 100%.
It's not exactly deterministic.
They are certain random factors involved
which are out of our control,
and therefore we have to understand
what's going to happen,
we have to model what's going to happen.
That's where a Markov decision process is used.
Agriculture, there's an example,
like, same thing, harvesting crops.
How much crops do we harvest?
How much 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'll invest
in any given, I think, day or year or some period of time.
And there are certain factors are out of its control,
For instance, you know, the market movements,
it doesn't know what can happen,
so it needs to actually model that somehow,
and a Markov decision process is 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, yeah, even sports.
Two examples for sports and epidemics,
and modern insurance claims, inspections,
and maintenance and repair, and so, and so.
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 a real-world scenario."
So it'll give you a better understanding
and this is what we talked about
in the promotional video for this course 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,
"Okay, so we're gonna be dealing
with Markov decision processes 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 AI in the future
to make the world a better place.
And we'd be super happy about that.
We'd be super happy if you could use
what you learn in this course
to make the world a better place with AI.
How fantastic would that be?
So, on that note, I hope you enjoyed today's tutorial.
I look forward to seeing you next time.
And until then, enjoy AI.