Hello and welcome back to the course on Machine Learning.
Today we're talking about the upper confidence bound.
And the intuition behind this algorithm of the.
Reinforcement branch of machine learning.
So let's get started.
As we discussed previously, the problem we are solving.
Is a multi-armed bandit problem where you've got
five or more or any number of slot machines, and
you can bet your money in any one of them, and you need to find out.
How to bet to maximize.
Your returns.
And basically, we agreed that behind every machine
there is a certain distribution.
And that's because you don't know which of these distributions is optimal.
You need.
To combine exploration of these machines with their.
Exploitation in order to find out which.
One of these machines is the best, and then you can start exploiting that one.
adds the more implication of this problem is, of course, advertising.
So if you have 5 or 10 or 50 or 500 different ads,
how do you find out which one is the best one?
Of course, you can run just an AB test and then use the results of that.
But that means you're doing the exploration
and then you're doing the exploitation separately.
You're going to incur lots of costs.
You're going to incur, you're going to waste a lot of time.
we want to combine exploration, exploitation and get. To.
The optimal result as soon as we can and maximize the output of our efforts.
All right.
So, this is a quick summary of the multi-armed bandit problem.
So let's go through this very quickly so we can get to.
The fun stuff.
So we have the arms.
For example, arms are ads that we display, each time a user comes to a web page,
each time an ad is displayed or a user visits this page,
that's around, for each round. And.
we choose. Which ads to display.
So you can only display one ads, like with, one, armed bandits.
You can only pull one of those arms.
You can only choose one machine to bet on, at each round.
And, ads AI gives a reward whether it's a 0 or 1.
and basically I of n t of n is equal to one
if the user clicks on the ad and zero if you didn't.
These are didn't. And our goal is to Maxwell total reward.
We get over the many rounds.
So that's basically what we're doing.
And this is how the upper, confidence bound algorithm works.
And I.
Won't go into too much detail on this because.
Actually, how the land is going to, run you through this and.
You're going to code.
This, from scratch, in R, and you can code this also in Python
in the fully lectures, of course.
So we're not going to waste.
spend time on this. We're actually going to get.
To the essence of the algorithm. Right.
So, let's get to the intuition part, which is, how does it work?
What what's actually happening in the background when this algorithm is running?
All right, so let's have a look.
these are our slot machines, or one armed bandits.
And, they each
one of them has a distribution behind, it we want to find the best one.
Right. Look at them.
We can't tell which one it. Is, but let's see.
We do know. Let's see.
We know the end result.
just for argument's sake, what would it look like?
Well, this is.
For instance, in this case, the. Distribution.
These are the distributions. Behind those machines.
You've got, you know, the machine.
This is how they're spitting out the results with these distributions.
And just by looking at this you can
you can tell right away which one is the best machine.
Which one would you bet your money on?
constantly if you were playing around with this one.
Right.
So right away here you can see that this one has the best, return.
And you would want to just,
well, all the time, just bet on this one, and your outcome would be the best.
But we don't know that, right?
We don't know that.
And we want to find that out in the process of playing
these machines of or using those ads that we're running,
and find out, you know, which one is getting the most clicks?
we don't want to we don't have the time, and money
to do that exploration before or the actual campaign is running.
We want to do that in the process.
We want to maximize our return already from the very start.
So how do we do that?
Well, let's transfer these distributions or the actual expected return
from these distributions onto. A vertical axis.
So we're going to take these values
and we're going to put them onto a vertical axis over here.
So there's our vertical axis.
So for distribution one let's say that what value is there for distribution.
Two there was a value we could. Remember.
It was lower distribution three even lower to sure.
For higher and have five the best right.
So those are the expected
values or returns for each of those distribution.
For each of those machine. That's why our y axis.
But again we don't know that.
So, what how does this algorithm work.
Well, it assumes.
Some starting point. For every distribution.
It just assumes that.
There is a certain starting, value that.
Okay, let's just assume that because we can't distinguish, we can't.
Discriminate. Against these machines in any way.
They all look the same.
Let's assume that they all have the same return.
And let's put it on that level.
Now then what the algorithm does is,
those formulas that, are behind the algorithm, they.
create a.
confidence band. And it's,
it is
designed in such a way that with a very high level.
Of certainty, that.
Confidence band will include the actual,
will include the actual return or the actual expected return.
So basically, the first couple of.
rounds are going to be trial runs.
So we're going to intentionally just. Try out.
The machines at least one time each in order for us to be able to place this.
Value here and come up with a confidence band.
Who's going to be very. Large.
So at the very start, it's very large, but it is designed specifically in a way
that, the expected value, which is this one over here
will have very high level of confidence, falls inside this confidence
with a little high,
with a very high degree of certainty, falls inside this confidence bound,
which is built around this,
red empirical value which we have derived.
And the very solid, it's all the same. Right.
So and then how does this algorithm work?
Well, out of all of them, we pick the,
the machine with the highest confidence bound.
Right now, it can be any of these machines, right?
They all have the same confidence bound that we're talking about.
The upper confidence bound.
That's why the algorithm is called upper confidence bound.
and so we just going to pick any one of them
because it doesn't matter which one we pick.
Again we don't. Know these blue these color. Lines.
We don't know about them all. We see.
as as the
agent or as the person analyzing this.
We only see these boxes and all. They're all identical to us.
So we just pick any one of them. Let's say we pick this one.
So what happens.
Next is we actually.
Pull that lever of that machine and something happens,
or we place that ad, right.
So we display that ad next and we want to see
did the person click on it or did the person not click on it.
And in this case, the person didn't click on it.
Right.
So it went this red value goes down because it's
when now we have another observation just for this machine that is added
to the whole, sample of observations for this machine.
And the value goes down because, well.
All always this red.
Value is like the observed average.
The observed average. Is going to according.
To the law of large numbers, is always.
Going to, In the long run is.
Going to converge to the.
Expected, expected return or expected average
or expected value for this distribution.
So, therefore
it is very likely that this value is going to go down.
And now because we.
Have an extra observation, the second thing happens is the confidence
bounds confidence interval.
You see that confidence interval becomes smaller.
Simply because we have.
An additional duration of course doesn't become that much smaller.
But this is to just to illustrate a point, because
we have an additional observation, we are more confident in our predictions.
We are more confident in everything that's going on.
So the confidence interval interval, slowly starts to shrink.
All right.
So the next step is now we find the next one with the highest confidence bound.
So this is not this one.
It's one of these for just picking a random one.
There we go. This one do the same thing.
So again the, ad is displayed, a person either clicks or doesn't click.
And that affects the average that we've measured so far, the empirical average or,
if you've pulled the lever, you've got a certain,
you know, you either one or you lost.
And that affects your, empirical average, this red line.
And as expected, it's, slowly starts to converge over like, lots of iterations.
It will start to converge to the to the, expected value.
so it comes closer and right.
Away, you can see now this machine is all of.
A sudden above all of the other machines. Right.
So if this was the end of this.
Iteration, that's it.
We, we would assume from here that this is the best machine.
And we'd start exploiting it.
And, therefore, this algorithm would be completely useless.
But the we we shouldn't forget about the second thing that happens.
The second thing that happens is that.
Because we.
Got an additional, observation in our sample now,
we are more confident in this interval.
And these confidence bounds, they're designed, they're they're.
Only purpose is to include.
The, actual expected value, wherever it is.
We don't know where it is, but they are, they are telling us that this value,
this green value is somewhere inside this box.
But because we've got an additional observation, we're.
More confident our sample size is larger.
So we're more confident in the overall picture, for this machine.
So the confidence bounds decrease.
And now as you can see it's no longer the top machine
because even though it went up the confidence bounds went down.
So now we're going to look for the next highest confidence bound.
It can be any one of these three machines.
And just look at any any one randomly for now this one.
And here even though the red line is above the blue line. So,
according to the law of large numbers, you'd expect this to converge to that.
But sometimes it can randomly occur that, it can go the other way.
Right? Things can happen like this.
It's it's all probabilities. so. Basically.
It might even go up.
So there we go.
It went up even though the blue line was below the red line.
it can happen as a, you know, like as a,
just as per chance.
Right.
In the long run, it will converge, but on a random occasion it can go up.
It can go in anyway, and again, we got another,
another element in the sample.
So the, confidence bounds converges. Okay.
So can we kind of get the picture of what's going on here.
So now we're going to pick the next one with the highest upper bound.
let's say this one.
then we do the trial.
We do the, the rounds.
What happens is the person click on add, do we win money from the slot machine?
and it goes down?
Probably not.
we didn't didn't click on the add.
Didn't win from the money from the slot machine.
So the average of our observation goes down, comes closer to the,
expected value.
And the confidence bounds also decrease. Okay.
Now we kind of when our in business, we can
all of them are kind of starting to play, next one is this one okay.
This is the now.
Because we know. The end result.
We know that this is the best one. Right.
We know that this is the best ad or this is the best slot machine.
We should be using. But like.
Because just we.
We were kind of like, given this insight, just for argument's sake
or for the purpose of this exercise, but the person that's,
reforming this algorithm or the algorithm itself doesn't know that.
So unknowingly, it's actually starting to exploit the best, option right now.
so again, okay, it goes up good.
kind of this band goes down and as you can see, it's still the best one.
All right. So now we're going to do it again.
we're going to use this one again.
And it comes closer and but the confidence bound goes down again.
This is all just, for illustration purposes.
Of course, it's not going to go down by that much just because one observation.
But we don't want to be sitting here through a thousand iterations.
This is just to demonstrate the overall picture.
So even though we exploited the best option
by exploiting the best option, we're decreasing the confidence bound.
Which gives an opportunity or breaks learning.
Any option.
If it goes, if it keeps going up, kind of keeps being good.
because we're building.
Up the sample size, this gives an option to the other, it gives opportunity
to the other options too, or machines or adds to have a chance in the play.
So that we are not just, you know, we're not biased towards
which one we think is the best or optimal outcome, optimal machine.
So now that we move on to this one same thing
and comes closer to decrease, we want to this one,
but decrease and we move on to this one and the decrease.
And then again this one bounds decrease.
And again this one might jump closer bounds decrease.
And even though we were very close to, you.
Know, finding the solution that as that one bounds the.
Bounds decrease so much. And you'll actually see this.
In the practical application.
The practical areas that are following that sometimes
we will after using the optimal option for some time, we'll switch.
The algorithm will still switch
to a suboptimal option just because the bounds are decreasing all the time.
And then we'll use this one. Bounds will decrease.
And now we're back to the best one on the crease.
And then we're just going to be exploiting this one and exploiting this one
and exploiting this one because we found out that it's the best one.
So that is in essence
the whole concept behind this upper confidence bound algorithm.
And that's how it solves the, multi-armed bandit problem.
it's a it's a very interesting solution, much more sophisticated
than just selecting randomly or running an AB test and then,
selecting the option, you know, that that one.
So, you know, if you're in advertising or if you've got, campaigns
or if you come across problems that are similar to this, always
just remember about the upper confidence bound algorithm.
And you can apply this in your work as well.
Very powerful algorithm.
And on that note.
I hope you enjoyed today's tutorial.
In the next couple of videos, Helena will take you through the.
Programing of this algorithm both in R and in Python, and you'll.
Get your takeaway templates.
And I can't wait to see you.
Next time when we'll be talking about the Thompson sampling algorithm.
And until then, enjoy machine learning.