-: Hello, and welcome back
to the course on artificial intelligence.
Today we are finally talking about Q-learning.
All right, so we've already got this equation,
the Bellman Equation,
which we've added lots of components to.
We've got the reward here,
which can be not just at the very end,
but it can be at any given step.
We've got the discount factor, we've got the probability,
because now we're looking at mark of decision processes,
and here we've got the probability
of ending up in a different state,
regardless of what action we take,
or actually given the action we take,
there can be multiple states that we can end up in,
and then we've got the value of the next states,
so you can see this kind of like a recursive function
and so on.
But you probably still have one question.
The question is, where in all of this is the letter Q?
Why is it all called Q-learning?
So where's the Q?
And that's the question
that we're going to be answering today.
So far we've been dealing with values,
the value of being in a certain state,
and now we're going to look
at how Q fits into all of that as well.
So here we've got two examples.
On the left is what we've been doing so far.
Our agent has been analyzing,
okay, I'm over here.
This is a mark of decision process,
so it doesn't matter how I got here.
The rest of the environment doesn't care of the steps
that it took me to get here.
From now on, I have to make the optimal decision
where to go.
Here, here, or here, based on the current state
and all the future states that come from here,
but not from the past.
And so he can see that there's three options.
There's state one, state two, state three,
and based on his experience,
he has calculated the values in these states.
And now he's going to using the Bellman Equation
so even though this is a stochastic process,
so he knows that he'll go here,
but there's a chance that he'll go left to right and so on.
So based on these values, going to make a decision.
That's what we've been doing so far,
and that is totally the legitimate approach here.
But now we're going to modify it a little bit.
We're going to take the same exact concept,
same exact problem,
but here, instead of looking at the values of each state
that he can end up in,
we're going to look at the values
or the value of each action.
So we're not gonna use the letter V anymore
because V is for the value of the state,
we're gonna use Q.
And you might have a question, why the letter Q?
Well, Q, some people speculate that Q,
well, I read this I think on Quora,
somebody mentioned that Q is because of quality,
but at the same time,
I couldn't find any other references to that,
so it might not be because of that,
might be just because that's the letter
that was used at the time
and now it became super popular
because it's all called Q-learning because of that.
So no exact reason why it's called Q,
but nevertheless, at least it helps us distinguish
between V and Q.
So Q here represents, rather than the value of the state,
it represents, let's go with quality.
It represents the quality of the action.
Okay, so I've got four actions.
What are the different qualities of these actions?
What is the value of the action
or the quality of the action?
Which action is more lucrative?
So I need a metric telling me,
all right, how do I quantify this action?
And then I can compare them.
And that is exactly what Q is.
And so here he's got four possible actions.
As always, go up, right, left, or down.
And based on the action, this is gonna be a formula
which tells us the quantifiable value of that action
which we're calling the Q, the Q-value of that action.
So let's have a look
at how we're going to derive this formula for Q.
How does it actually relate to these?
Because as you can imagine,
because actions lead to states,
there has to be some sort of link between the two, right?
We've already determined how to calculate this
and we're pretty good at it.
We know how to use the Bellman Equation
and very different environments
with lots of different complications.
Well, let's leverage that knowledge
to understand how we can now calculate Q
in order to make the same predictions.
Because as you can imagine, the environment doesn't change
depending on what approach we use.
The environment's gonna be the same regardless.
So therefore this approach,
and this approach should always give the same result,
and therefore that's another reason
why these two should be linked.
So let's have a look.
So here's our V approach
where we're just going to look at the value
of any given state, this state or any other state.
And here we're going to,
we're just using the letter S here
because that's the current state,
and so therefore the terminology
will be the same in both equations.
And here we're using QSA.
Q is of the state S and the action A,
because action is up,
but in which state did we perform that action?
We performed that action in state S.
Okay, so now we're going to write out the Bellman Equation
for the first approach.
As you can see here, we've got V of S.
So the value of any given state S
is the maximum of the reward that you get,
so maximum based on the actions.
So you have three,
in this case you actually have four actions.
So maximum out of all the possible actions,
and then of this part,
which we've already discussed many times
So this is our reward that we get
from performing that action in that state,
plus a discounted factor multiplied
by the expected value of the new state
that we're going to be in.
And expected value because it is a stochastic process.
We don't know exactly for sure
that we are going to end up over here.
We might end up on the left or the right
with certain probability.
That's why these probabilities are in here.
All right, so that's our value,
and now let's look at Q.
So Q is going to be defined,
we're going to use this to define Q.
So let's say the agent from this location, from this state,
performed the action up.
What is the Q-value going to be equal to?
Well, first of all, let's see what he'll get in in return.
For performing this action up,
first thing that you'll get is a reward, right?
No doubt about it.
There's going to be some sort of reward,
might be zero, but we know
that the way the reinforcement learning process works
is that sometimes
for performing certain actions from a given state,
there's a reward.
So we're gonna add that in here.
And then we're going to add, what are we going to add?
Well, let's think about it.
What is the next thing that happens
after he is gotten the reward?
Well, next thing that happens
is that now the agent is in a certain state.
He could end up here with a 80% probability,
or some probability,
but actually he can end up here or here.
But wherever he ends up,
now we already have a quantified metric
for that state he's in,
and that is actually the V-value of that state.
But because he came up in many different states,
in three of the possible different states,
we have to look at the expected value
of the state that he'll be in.
And so we're going to add that in.
We're going to add, of course the discounted factor
as we previously had,
because that is somewhere in the future.
And then we're going to add the sum
of across all possible states,
across all possible states that it could end up in
by taking this action, times a probability.
So what we're saying here is that,
okay, so by performing an action,
you're going to get a reward,
plus, which is a quantified metric,
plus you're gonna get, you end up in a state,
we don't know which one.
It could be here, it could be here, it could be here.
But here is the expected value of the state
that you're going to end up in.
And now we're going to multiply it by discounting factor
because that is one move away.
So that is our Q-value for this performance section.
And what you will notice here right away is that the Q-value
is actually exactly identical
to what's inside these brackets over here.
And why is that?
Well, if you think about it,
here we're taking the maximum of the result we will get,
the maximum across all possible actions,
so we've got four actions,
and we're taking the maximum across all possible actions
of the result that we'll get
by taking each of those actions.
And in Q, we're defining,
interesting, what will we get by taking a certain action?
So if you think about it, it makes sense
that the value of a state, so for instance, this state,
is the maximum of all of the possible Q-values, right?
So here in this state, by being in the state,
the agent has one Q-value, two Q-value,
three Q-value, four Q-value.
So he has four possible Q-values.
Well, the value of this state,
it makes sense that the value of the state
is the maximum of all of those four Q-values,
and that is exactly what we can see here.
That's a good confirmation
of this new formula that we derived.
If that wasn't the case, if that didn't match up,
then we would have questions.
We'd be like, so why doesn't it match up
if Q-value is a quantified metric of performing an action
and V depends on the four,
is the maximum of the possible results of the four actions
that it can perform.
Hopefully that makes sense,
and that confirms the formula that we've just derived.
And now we are going to make it even more interesting.
We're going to get rid of the V entirely.
Because you can see here you got V
is a recursive function of V.
And then you got V, and then V, and then V,
and then V, and so on.
So you can express this V through all of the following V's,
the most optimal V's that will come up.
Here, we're expressing Q as a recursive function of V
or as a function of the next V.
And then we'd have to plug in this V
and then we'd get back to the V.
So what we are going to do
is we're actually going to take this V
and we're going to replace it with a Q, right?
So let's have a look at that.
We're going to take this V of the next state
and we're going to plug this into that formula over here.
And as you can see now, so this part doesn't change,
this probability doesn't change,
but as we just discussed, V of S is the maximum
by all actions of Q of S and A, right, over here.
So that's what we're going to replace in here.
So we're going to say a maximum of,
of course it's the new action,
the action that we're going to take,
because here we've got V of S prime.
So here now we've got the maximum across all A prime,
so the actions that we're going to take from this state,
or from whichever other state we end up in.
But the action that we're going to take from there,
and maximum across all those,
and the maximum is of all of the Q-values
that are available to us
in that new state as prime, A prime, and that's the action.
So there's gonna be another four Q-values there.
So now as you can see, let's go through that again.
So as from what we derived, from what we discussed,
just through logic and intuition,
so that we can see that V and S are actually V of S
and Q of S and A are linked.
V of S is the maximum across all actions of Q of S and A.
You can see it right here,
so this part is identical to this part.
And then we're going to leverage that
and we're going to replace this bit with V of S from here,
but not this exact formula.
We're gonna take this internal part
and we're going to replace it with Q of S and A.
So we're gonna plug that in here.
And this part is gonna be Q of S prime, A prime.
So maximum of Q across all A primes of Q S prime, A prime,
and now we have our formula.
So now we have a recursive formula for the Q-value.
So now the agent can think, what's the value of this action?
What's the quality of this action?
What's the Q-value of this action?
Well, it depends on the reward I get
in the immediate step after that,
plus it depends on the discounted factor times the maximum
of all the possible Q actions in that state.
But I don't know if I'm gonna get there,
so I need to also look at that state and that state,
and that's why we have this expected value over here.
So we have this sum, probability times a maximum,
and that's our expected value.
So very similar formula as you can see,
but this time we're expressing things through the Q-values.
And that's why this whole algorithm is called Q-learning,
because this is what is looked at,
this is what the agents actually use.
They don't look at the states,
so look at their possible actions,
and then based on the actions,
on the Q-values of the actions,
they will decide which action to take.
So they'll just look at the maximum Q-value
in this given state.
It has four actions.
What is the best action to take?
So it can compare.
Instead of comparing the different states it can end up in,
it's going to compare the possible actions
that it currently has.
Then by finding the optimal one,
it's going to take that action
and then it's going to repeat that process,
repeat that process, and so on.
So now you can see how all of this comes together,
how the reward, the discounting factor,
the stochastic mark of decision processes,
and the V-values and the Q-values all come together
in order to give us this one super powerful Bellman Equation
for Q-values, which we can now apply
and let our agents learn how to beat the environment.
And so that is a intuitive explanation of what's going on.
I know we went through the formulas, but it is necessary,
because this is our formula
that we've been going through this whole chapter,
and I think it's a good transition from V to Q,
and it illustrates how they're linked between each other.
And if you'd like to get a bit more
of a rigorous approach, mathematical approach,
and you see the mathematics behind it,
and learn a bit more about Q-values and how they work,
then we've got some additional reading for you.
This paper's called "Mark of Decision Processes,
Concepts, and Algorithms" by Martin Von Otterlo, 2009.
So you've got the link here as always,
and here you can read in a bit more detail
to understand all the nitty gritty
behind Q-values and so on.
And now that we've discussed all of these things
relating to the Bellman Equation,
now we are ready to look at something more complex
such as this paper,
if we want to get some additional information on this
in order to get a deeper understanding.
But even if you don't read through this paper,
already you should have a good working knowledge
of what key learning is all about
and how agents come up with the actions
that they need to take in a certain environment.
So I hope you enjoyed today's tutorial
and I look forward to seeing you next time.
Until then, enjoy AI.