Speaker: Hello, welcome back to the course
on artificial intelligence.
In today's tutorial,
we're going to cover off quite a complex tutorial
called Eligibility Trace
or N-step Q-learning.
And, this is something that we're going to implement
in the practical side of things.
So, that's why we need to cover it off.
And, at the same time, it is quite a complex topic.
So, I've got a very interesting approach
to getting us up to speed with the intuition behind this.
So, I have like
a different approach in mind than we're used to.
So, let's, let's have a look at that and see how that goes.
So, I'm going to give you an example to start off with,
like, I'm going to give you an example in this tutorial,
and, that will demonstrate the power of eligibility trace.
And, it'll give us the intuition behind things.
And, then, if you like to delve further
into eligibility trace,
I'll give you the best place where you can read about it.
I'll give you a reference to a book.
But, otherwise,
so, why this is gonna be different?
is because we're going to first,
rather than delving into the intuition,
we're going to look at an example,
and, the intuition will become obvious
after we talk about it.
And, that's my hope for this tutorial.
So, let's have a look.
Let's see, let's see if we can do this.
So, here we've got two agents.
And, they're navigating the same environment.
And, we are going to see how these two agents work.
The first one's gonna work without eligibility trace.
Second one is going to work with eligibility trace.
And, hopefully we'll see why the second one
is going to be so much more powerful than the first one.
So, let's have a look.
We're going to look at this agent first,
and, the way he operates is
the exact way that we've discussed deep Q-learning, so far.
So, the agent is going to take a a step,
or is going to move,
take an action, move into a new state.
It's going to get a certain reward,
it's going to put that reward through its algorithm,
update the neural network that's running this agent,
or that's running in the mind of this agent.
So, that's basically how it's learning from the environment.
That is going to take a new step,
So, from this new state, its gonna take a new action
based on what its neural network is telling it to do.
It's going to get rewards,
it's gonna update, and, so on.
And, it's going to keep doing that.
So, obviously this agent's going to do quite a good job.
And, as we've seen previously
from the previous practical tutorials,
we're gonna get some quite good results here.
But, now we're going to add a new feature.
Now, this agent number two,
this guy over here,
he's going to navigate the same environment,
but, he's going to use eligibility trace.
And, this is what it means.
What he is going to do is he's going to take N-steps.
He's gonna take, in this case, five, four steps.
He's gonna take four steps.
And, then only after taking these steps
will he get,
calculate the total reward that he got from those steps,
and, he will put it through his network.
He will put it through his neural network
that's governing the decision making process.
And, then, the neural network will learn from that.
So, which one, right away,
like, which one do you think is more powerful?
The guy that is just taking one step at a time
and, kind of like, poking in the blind or in the dark,
and, he's like, okay,
so, I'm gonna take a step, see what happens.
We're gonna take a step, see what happens.
The guy at the top.
Or, the guy that takes just,
very courageously marches through four steps in a row,
and, then,
he decides whether those were good steps or not
all together.
And, why you can see here,
or, why you're probably getting a sense for why
the second guy is better or is more powerful
is because the second guy actually knows what's at the end.
The first guy, when he's,
when he's assessing whether this step is good or not,
he's only looking at the reward that he's getting.
And, so he's only guided by the reward
the environment is giving him.
Same thing here, he's only guided
by the reward that this environment is giving him here.
So, every time, that's his only kind of compass that he has.
The reward, the reward, the reward.
Whereas here, the,
he actually can assess, after taking all these steps,
he can assess, oh, okay,
so, I did get to the finish line.
So, this combination of steps was good.
All of them were good.
Or, oh no, I ended up in the fire pit.
Or, oh no, I didn't win the,
my car didn't get to the finish line,
or, I crossed the sand wall,
or, I lost the game of doom,
or, something like that,
and, then, he decides or something like that,
this whole combination of steps is bad.
And, therefore,
for these steps that are earlier on,
he has more information,
he has more insights.
Like, in in a very intuitive approach.
Again, this is a much more complex topic
than we're portraying here.
But, in an intuitive way, for example, if we take this step
this step only has information,
to update it,
you only have information coming back from this reward here.
And, for this step, in this case,
the same exact step,
it has more information.
It has information coming all the way from,
okay, so what was the outcome after four steps
or five steps or whatever.
Yeah. So, that is,
that is how it works.
And, why it's called eligibility trace
is because during this process,
not only does he look at the cumulative reward of this,
of what's going on,
and, then, the cumulative loss,
and, then, all that is
(indistinct) propagated through a network.
But, actually there's a trace of eligibility.
That's why it's called, eligibility trace.
There's a trace that is kept in,
in the algorithm which says,
okay, so if we do get a,
let's say we get a punishment,
we get a negative reward,
then which of these steps
is most likely to be eligible for that punishment?
So, not only do we know what, overall, this whole pattern,
or, these this combination of steps is,
but, we also keep a trace of eligibility.
Which steps are we going to update if we get a reward?
So, for instance, if it's a negative reward,
we might have an eligibility trace that indicates to us
that this is the step that is most responsible
for what we got in the end.
Or, if it's a positive reward,
again, we might know,
the algorithm helps us keep track.
This eligibility trace algorithm
helps us keep track of what's,
what step or what action needs to be,
is eligible to be updated
based on that reward that we get?
And, that's why it's called eligibility trace.
And, so, that's the basic intuition
behind eligibility trace.
And, hopefully these two examples
of these two agents make it quite obvious
or quite intuitive
in why eligibility trace can be so powerful.
And, if, as promised, if you'd like to delve further
into topic of eligibility traces or N-step Q-learning,
then a wonderful amazing book is, which is,
which you can find is called
Reinforcement Learning: An Introduction.
It's by Richard Sutton and Andrew Barto, 1998.
I think they're in the process of creating a second edition
or, they're creating a second edition,
but, this is the most common, or the most popular,
or the most referenced book on reinforcement learning.
It's got a ridiculous number of citations,
I think like tens of thousands, if I'm not mistaken.
And, also the chapter you need for this is chapter seven.
So, in order to look at eligibility traces,
there's whole chapter about it.
Chapter seven.
You can read about it and
it goes into lots of detail,
forward, backward eligibility traces,
and, also, how, you know,
you've got temporal difference on one hand,
and, on the other end of the spectrum
you have Monte Carlo Methods,
in between, you have eligibility traces.
So, eligibility traces are your link
to go from temporal differences,
to Monte Carlo Methods.
Very interesting read.
Lots of pictures, which I really, really appreciated.
Very intuitive explanations.
So, there's lots of things that you can learn from this book
about artificial intelligence and reinforcement learning.
But, specifically eligibility traces are,
like, a very good place to go to
is this book for eligibility traces.
And, the second reference for today
is something that (indistinct) going to show you
in the practical tutorials,
the deep learning,
or, the Google DeepMind research paper
on asynchronous methods for a deep reinforcement learning.
Yes, that's the paper.
That's the one paper that,
the A3C paper that we're going to be discussing
further down in this course.
We're getting closer and closer to it.
And,
as you can tell, we're pretty excited about this.
So, this is going to be looking a little bit at about,
at how they implemented eligibility traces in this paper.
So, we're going to be using this more
for the practical side of things.
So, hopefully you enjoyed today's tutorial,
and, now you're a bit more comfortable
with eligibility traces.
And, I can't wait to see you next time.
Until then, enjoy AI.