Hello and welcome back to the course on Machine Learning.
Today we've got a very interesting topic.
Today we talk about Thompson sampling and the algorithm's intuition.
And again
we're going to be using this algorithm to solve the multi-armed bandit problem.
All right.
So let's get started.
A quick refresher on that multi-armed bandit problem.
We have several slot machines.
each one of them has a distribution behind it.
Do you want to do five?
We don't know what these distributions are.
And we need to start playing these machines.
And at the same time, figure out which one has the best distribution
so that we then exploit that best distribution.
and but, it'll take us some time to figure it out.
So we need to maximize our return during the process of figuring out.
So we have to, find that ideal balance
or trade off between exploration and exploitation.
we had a few tutorials previously on, these things.
So we talked about the multi-armed bandit problem in a lot of detail.
So if you haven't watched that tutorial, I highly recommend
jumping into the previous section and watching it there.
Also, understanding of the upper confidence bounds
algorithm will really help you grasp the concepts of, Thompson sampling.
So if you haven't seen the upper confidence bound, tutorial,
then I highly recommend checking that out before proceeding with today's lecture.
All right. So let's get started.
A quick summary of the multi-armed bandit problem, is as follows.
We have d'Armes.
For example,
arms are ads that we display to users each time they, connect to a webpage.
So, by the way, yes. indeed.
a modern application of the more modern
representation of the multi-armed bandit problem is advertising.
So when you display ads, that is very similar,
or the algorithms that we're going to be applying can learning,
can be applied to solving a problem where you're displaying ads.
So if you go back here instead of having,
these slot machines, each one of these is a different ad,
and you want to figure out which one of these
ads is the best performing ad, but you don't have time to do an AB,
so you don't have the funds or the resources to do an AB test.
You want to figure it out on the fly.
That's when you would apply,
one of these algorithms that we were talking about in this part of the course,
and of course, this of other lots of other modern problems
that are very similar to the multi-armed bandit problem.
Therefore, these algorithms, are valid for them too.
All right. So moving back here.
So we've got the arms, for example, arms are ads that we display.
She uses each time
they connect to a web page, each time a user connects to this page,
that is considered as a round at each round.
And we choose which to display to the user at each round.
And the ad gives us a reward, either 0 or 1
one if the ad is clicked, zero if the ad is not clicked.
In the case of the actual bandits, it'll be a monetary award, so it won't be
just 0 to 1. It'll be a some value.
our goal is to maximize maximize the total reward we get over many rounds.
All right.
So that's a quick, overview of the problem that we're solving.
then here we've got, some very complex
looking mathematics and Bayesian inference and all these, distributions
and posterior probability
and other, prior distributions and beta distributions and so on.
we're not going to delve deep into this right now.
So had lunch will, take some time to walk through this slide
with you in the practical tutorials because,
we're going to be coding this, from scratch.
well, at least in R and therefore
he will actually walk you through this slide.
Our goal for today is to understand the intuition behind all of these things.
So we're going to skip skip the slide and get to the intuition part.
And this is the actual steps
that, you're going to be using in the practical tutorial.
So again had lunch will walk you through this slide as well.
And today we're talking about intuition.
So this is going to be fun.
This is some interesting slides coming up.
And get ready for a fun ride.
So grab a cup of coffee a cup of tea
three rings of popcorn and, let's get started.
All right, so here we've got a scale.
the, a y or the horizontal axis is the return.
The return that we expect to get from a bandit.
So we're going to look at a simplified problem.
We're going to look at rather than five or even ten.
We're going to just look at three bandits
because there's going to be a lot of stuff going on on this, chart.
And I don't want to clutter it up,
and we want to keep it as simple as possible,
just so that we can understand the concept.
And then, the same thing applies for 5 or 10 or however
many, machines that, you'd be looking at.
So here we've got the return and these vertical lines, just like in the case,
of the, upper confidence bound, we had the horizontal lines.
These vertical lines,
represent the expected return for each of the machines.
So, each of the machines out of the three machines that we have,
each of the machines has a distribution behind it
so that the, result, the amount of money that you win per
game, is picked as a random value from that distribution.
and we're not going to draw distributions, but basically just imagine distribution
behind each one of these, expected values.
So this is, this is just the center of that distribution or
the actual expected return from that machine.
And we're just visualizing it here.
But this is also kind of like looking into,
into the actual machine itself or like pulling it apart
and knowing how it works or being the designer of the machine.
In reality, when you're playing these machines, of course, you don't know this.
So this is some additional information that will guide
us, that will help us understand how the algorithm actually works.
The algorithm itself doesn't know this information, right.
So this is hidden, but it's just there for us
so that we can better understand what's going on.
So these are the expected returns,
the actual expected returns of each of the machines.
And obviously if you knew this right away,
you would say that machine number three or the yellow machine is the best one.
because it has the highest return, right?
It has the highest expected return.
You'd always just bet on this one.
But again, you don't know this yet.
All right, so what happens, with this algorithm?
Well, at the start, just like with the upper confidence
bound algorithm, you don't know anything, right?
You have no prior knowledge of the, current,
situation or status of things, and therefore,
all the machines are identical to you, and you have to have at least one
or even a couple of trial rounds just to get some data to analyze.
And so let's see, let's say that has happened.
There are some, trial runs for the so for machine number one
or the Blue machine.
And, based on those trial runs,
the algorithm, the Thompson sampling algorithm, this is where it starts
getting different to the upper confidence bound will construct a distribution.
Right. So we'll get to this distribution in a second.
What means.
But for now let's just do the same thing for machine in the Green Machine.
And so yeah
we just are pulling the arm several times like four times for instance.
And we're getting some values and
that are going to be somewhere around obviously the actual expected return.
Right.
And based on that
and based on those values, of course, it's probably gonna be a bit more than four.
we're constructing some sort of distribution
or some sort of perception of the current state of things.
And this is the part where it gets interesting.
So the actual meaning of this,
these distributions is not which you might think at first.
So, these distributions
are actually showing us or they're representing
not the we're not trying to guess the distributions behind the machine.
So the first thing that might come to mind is that all right.
So we've constructed distribution.
And so the blue distribution is our attempt
at guessing the actual distribution behind the blue machine.
Right.
The distribution that this is the expected return for.
And the green is for the green machine.
The yellow set yellow machine will actually not.
That's not the case.
We are constructing something completely different,
something completely out of this world.
We're constructing distributions of where
we think the actual expected value might lie.
It's very important to understand that.
So, we are creating, kind of a,
if you, if you want to think of it that way,
we're creating an auxiliary mechanism for us to solve the problem.
So, we're not we're not trying to recreate these machines.
We're recreating the possible way these machines could have been created,
kind of in that sense.
So let's, let's, just solidify that this is where
we think that expected the actual expected values will be.
So let's look at the blue one. For instance.
We got four values.
And based on those four values we've constructed this distribution
which will show us which is showing us where is that value.
Mu star.
So this is mu star, the actual mu start, but we don't know it.
So the algorithm doesn't know it.
So it's constructed a distribution trying to guess where this value is.
And of course can't just say it's over here.
It's over there, it's over there.
It's saying, okay, there's a there's a very high likelihood it's over here.
But it also could be here, it could be here, could be here.
And as you move away, the likelihood drops.
But it still could be anywhere in this blue space.
Same thing for the green. distribution.
So based on the values that we've seen, the random values that have been selected
in the for four rounds,
the algorithm has created this distribution,
which is saying that this actual,
actual expected return from a sheet from the Green
Machine is somewhere in this area, and it's most likely to be here,
but it could be here, it could be here, it could be here, it could be way
it could be. So basically, at most it's most likely to be here.
Then it could be here, it could be here.
And as you move away, the likelihood of it actually being there drops off.
Same thing for the yellow.
So it's very important to understand.
So just to reiterate we are not trying to guess the distributions behind machines.
Right.
We are doing like kind of a little magic trick
or a little hat or a hat trick is I don't know if it's called a hat trick,
but we're trying to, do this, this create this perception of the world.
We're trying to, mathematically
explain what we think is actually going on or what could be going on.
And that is, that is important.
also important thing, because this demonstrates
that the Thompson sampling is a probabilistic algorithm.
The upper confidence bound was a deterministic algorithm
where everything was strict.
You know, everything was okay.
So whichever
one has a pious upper confidence bound, that's what we're going to choose
and so on.
But here we're creating a probabilistic, perception of the world.
We're saying, so it's likely to be here,
but it could be anywhere in this blue area,
and this one could be in this green and so on.
And you'll see exactly why we've done this.
In the next slide, we'll understand how this works.
And let's jump straight into that.
Let's understand now that this is probably the hardest part
to kind of, get your head around what we've created.
And now that we've created it, let's see how the algorithm is going to,
utilize this, auxiliary mechanism that we have created.
All right. So let's have a look.
So there are our distributions.
That's where we think.
So these are the actual expected returns for each of the machines.
But the algorithm doesn't know them.
The old algorithm has created these are these distributions where
which allow it to kind of guess where the
actual distribution might lie for each for each of these machines.
So what it's going to do is it's actually going to trigger
each of these distributions.
So like we're in the we're in a new round.
We have to choose a machine to use.
So what the algorithm will do is it will go and call
this distribution and it will pull out a value out of this distribution.
And let's say it pulled that value.
Then it'll pull a value out of the green distribution.
Let's say it pulled that value out of the green distribution.
And let's say and then pulls a value out of the yellow.
This is that distribution of that value.
And again it's pulling them.
So according to the distribution. Right.
So this is a distribution of values.
So basically it's most likely to pull a value
somewhere in this area then less likely in for the way you go, it's more
or less less and less likely, but still it can happen that you can see
that this yellow value is actually quite far from the center,
but it's still can happen that it pulled this value out of distribution.
And it can happen.
To pick this green, a value out of the green distribution
totally can happen in the long term, of course, is
going to be picking somewhere close to the center like over the long run.
but on a one off basis, this can totally happen.
And so now it's picked these values and guess what that means?
Well, what this actually means is that we have by doing that,
we have generated our own bandit configuration.
So we have created a
this hypothetical or imaginary
batch of machine or not batch
imaginary set of machines in our own
virtual world where we're saying, okay, so the expected,
the actual expected, return for the blue machine is this value.
The actual expected return for the green Machine is this value
and the actual expected return for the yellow machine is this value.
So we've created this, subzero upside of world
or hypothetical virtual reality in which we have all our own three bandits.
And how are we going to solve this problem?
and this whole problem is very easy to solve.
It's obvious how to solve this problem.
You just pick this machine, right?
Because this machine has the highest expected return out of the three.
And obviously just going to go with this machine in the virtual world
in the, sort of the reality.
And, what that means is that now we translate this result
into the actual world in the virtual, hypothetical world.
We've selected the Green Machine.
So in the actual world, the,
the algorithm will also select the Green Machine and what that will do.
So basically pull the lever for this machine right.
And what it will do is actually it will, give us a value.
So the machine will spit it out, spit out a value.
But that value is going to be based on the distribution behind this machine
where this is the actual expected value of that distribution.
So the value is going to be somewhere here, probably close to the actual
expected value doesn't have to be.
Again there's a distribution behind all of this.
It could be far away.
It could be close. But let's say in this case it's this one.
All right.
So now this information this is new information to the algorithm.
What it's going to do is it's going to say okay.
So the I pull the green lever or the lever for the green machine I got this value.
So now I have to adjust my perception of the world.
Right. So I have a, prior probability.
So these are my, well, for the green Machine, this is my prior, distribution.
This is where the Bayesian inference comes into play, or it's already been in play.
And this is where adding to the Bayesian inference.
So that's our prior probability prior distribution.
Now we've got some new information.
This is our new information.
We're going to add it in and see what see how that changes.
Our perception of the world or perception of the world has changed.
The distribution has shifted a bit and it's become,
narrower because we have more information.
We our sample sizes increase, of course.
Excuse me.
Of course.
It's not going to increase that that much.
Yeah.
This is just an example to,
demonstrate what we're talking about to get the point across.
But that's, that's the point that, every time we add new information,
our distribution becomes more and more refined.
All right, so now we have a new perception in the world.
Now what happens next is a new round, right.
Same thing.
We're going to do the same thing again for a new round again.
we generate or we pick some values out of a distributions.
There they are.
now we've constructed a or we've generated our own bounded configuration,
you know, virtual or virtual reality or in our hypothetical world,
out of these three, we have to pick the best bandit,
which is, of course, the one here, the Yellow Bandit.
And we're going to, now pull the actual pull in the real world pool.
That, lever of the yellow bandit algorithm is going to do that.
That's going to trigger the distribution behind the Yellow bandit,
and that will give us some sort of value.
So this is the actual value that we received in the real world.
Now we're going to incorporate that value into our perception of the world.
And our perception of the world is going to change, is going to adjust.
There we go. Now we're going to do that again.
All right.
So let's let's just do this one more time.
Just so we practice the logic behind all of this.
So a new round generates
the generates the bandit configuration.
Right.
So this is what we're going to think that our,
expected actual expected returns are going to be our conversion.
This is obviously the best one.
we're going to use a pool.
The yellow machines are a lever.
That's going to trigger the distribution behind.
The yellow machine is going to spit out a value.
In the real world, there's a value.
And then we're going to have to adjust our perception of the world again
to match that or to incorporate the new information and so on.
We're going to keep doing that until, we get to a point
where we've refined the distributions substantially.
And the picture looks like this.
So, they might be refined even more.
This one might be more refined, this one might be more refined.
But as you could see from there,
we slowly will start generating more and more rounds
based on the yellow machine will be triggering the yellow machine.
So these ones might not even get that refined in the long run,
which is totally fine, because our point is to get
to the best machine, to find it and exploit it as much as we can.
So there we go.
That is pretty much how the Thompson sampling algorithm works.
And as you can see, it is a, probabilistic algorithm.
And every time we're generating these values,
they are we kind of creating this hypothetical,
setup of the bandits.
And then we're solving that, and then we're applying the results
to the real world.
We're adjusting our perception of reality
based on the new information that that generates.
And then we're doing that again.
So hopefully this was a, interesting and tutorial.
I find this, algorithm very, very cool.
And in the next tutorial we're going to compare, a little bit,
and our confidence bound and the Thompson sampling algorithm.
And I can't wait to see you there.
Until next time, happy analyzing.