Hello and welcome to this art tutorial.
So in the previous tutorial we imported the.
Data set. And today in this. Tutorial.
We're going to implement the.
UCB Upper. Confidence Bound algorithm.
So I'm not sure if it's bad news or good. News, but there is.
Actually no. Package that we can use easily to.
Implement this. UCB algorithm.
So that's the bad news.
But the good news is.
That we. Are going to implement the.
UCB from. Scratch.
And that's good news because that.
Will give you the opportunity to really improve your skills in AR.
So be ready.
It's not going to take 3 or 4 lines like we used to have before.
We are.
Going to implement the whole algorithm from.
Scratch without. Using any package.
And we are going to do. It step by step.
And speaking of steps, let's.
Now actually jump to.
The slide of the.
Upper confidence bound algorithm.
So this algorithm takes three steps.
The first step is at each round end.
We consider two numbers.
For each ad ai.
That is, for each version of the ad.
These two numbers are an AI.
The number of times.
The ad I was selected up.
To round N, and the sum of. Rewards of the ad.
Version AI.
Up to. Round n. Okay, so the.
First thing that we need to do.
Here is to declare these two variables, because we will need them afterwards.
Okay.
So the first.
One, the number of times the ad.
I was selected up. To round n.
Let's actually call this variable. Numbers.
Of selections.
All right.
So we need. To consider this number for.
Each ad AI.
So what we're. Going to do.
Is create a vector that. Will contain each.
Of those.
Numbers of selections. Of each ad I.
So we will set this variable equal to a vector of size d.
And we will.
Initialize all the. D components of.
This vector to zero.
And so how can we do that in R.
Well we simply need to type integer.
And in. Parentheses d.
And this will create a vector of sized.
Containing only. Zeros.
And we are doing. This because of course at the.
First round each version of the ad hasn't been selected. Yet.
So the number of times each version of the.
Ad was selected is of course, zero.
Okay, so done. For the first number.
All right.
And the second number.
Is the sum of rewards of the ad ai up to.
Round n. Okay. So let's call this variable.
Sums.
Of rewards this way.
And same.
You know we need to take the sums of rewards of each.
Version of the.
Ad at each. Round. And so.
We're going to set it as a vector.
Of D components as. Well, exactly.
Like we did for numbers of selections.
And same. We.
Will initialize. It to zero because of course at the.
First round the sum.
Of rewards of each version of the ad is of course zero.
So we will just copy this copy.
And. Paste it here.
All right.
So basically step one done.
Now let's move on to step two.
Step two is.
From these two numbers we compute.
First the average reward of ad ai up.
To round n.
And second the confidence interval at round n.
So basically we need to compute these.
Two numbers one.
At each. Round n.
So let's implement this. Step two.
Since we need to compute these two numbers at each round n.
Of course what we need to do is to make a for loop.
All right. So that's what we're going to do.
We're going to go through all the rounds from.
Zero to the. 10,000 round.
So for each.
Round n so we're calling the rounds n n.
So now we need to input.
The lower bound which. Is one.
So that's the first round.
And then the upper bound which is n.
So n is the total number of rounds that is 10,000 rounds.
So in case you have a problem with more rounds
or more users we will, you know, declare this variable here.
N. Equals well here for our.
Problem it's 10,000.
All right. 10,000. So right now in the loop.
And so what. Do we need to do.
We need to compute for each version of the add.
The average. Reward and the confidence interval.
So that's exactly. What we're going to do.
And since we're doing.
It for each version of the add AI, well.
What we need to do now.
Is. Again another. For loop.
And this time we're going to loop.
Over all. The ten different versions of.
The ad.
So the. Ads are indexed. By AI.
So for I here.
In one and then again we're going to input.
Here D in case you have more versions of your Add
or more arms for your specific problem.
So we are going to declare a new variable here which is D.
And since it's the number of.
Ads we will set it equal to ten.
All right.
And now we're entering into.
The second loop.
So right now this.
Level we are at a specific.
Round and dealing.
With a specific version of the ad.
And now we can.
Compute our. Two numbers.
The average reward of the ad AI.
And the confidence interval.
So let's start. With the first number.
The first number is the average reward.
So let's call it average
reward and equals.
All right. So what does it say.
It says that it's the sum of rewards of the.
Ad version AI up to round n divided by the number of times this ad version I.
Was selected up to round n.
So simply let's write this formula.
We already have these two variables.
Well, we have the vectors, but of course we will take the i'th.
Element.
Of these two vectors because they correspond to our AD version ie of the ad.
So let's do it.
Sums of rewards.
And we take the i'th.
Element of this vector.
Divided.
By numbers. Of.
Selections and same.
We're taking the i'th. Element of.
This vector.
Great.
So we have our first. Number computed.
The average reward.
Now let's take care of the.
Second number the confidence interval.
Well we. Will not. Build.
The whole confidence interval.
What we will compute right now is the upper.
Bound of the confidence interval.
Because that's what we need for step three.
As you can see.
Step three is we select the ad that.
Has the maximum upper confidence. Bounds.
So we just need the upper.
Confidence bounds. Of this. Confidence interval.
And so what is this upper confidence bound.
Well it's the average reward plus delta
I of n and delta I of n is given by this formula.
It's the square root of.
1.5. Log.
N divided by nine n, which is the number of times.
The AD. Version I. Was selected up to. Round n.
So let's compute. This delta first.
And then we'll compute the upper confidence. Bound.
So delta will call it's actually delta underscore AI.
And so it's equal to square root
which I call sqrt parenthesis here okay.
So what do we have.
First we have this three divided by two.
Then times.
And then we take the log.
So log here of. N.
That we divide by.
The numbers. Of.
Selections of the ad version ie.
That is the number of times the ad version I.
Was selected up to.
Round n.
Okay. So great for Delta. Delta is. Ready.
And therefore now we are.
Ready to compute the upper.
Confidence bound.
Which is all the essence of this UCB algorithm.
So let's do it.
Let's compute the UCB and let's call it upper bound.
This way.
Upper bound equals. Average reward.
Plus delta
I exactly like in this slide okay.
So great.
We just computed the average reward.
And the. Upper bound.
And therefore we are done with step two.
So now let's move on to step three.
Step three is to select the ad the.
Ad version I that has the maximum upper.
Bound.
So now.
Things get a little more complicated because we need to actually
create a vector, a huge vector, like a huge list.
That will contain the different.
Versions of the ad that were selected at each round.
So let's do this.
We're going to declare here a new.
Variable that we're going to call ad.
Underscore. Select id.
And this variable is going to be the huge vector that will give us the list of all.
The different versions.
Of the ad that are selected at each round.
That is, you know, at the end of the.
Algorithm when we run it.
The ad selected will be a vector.
Of 10,000 elements.
And each of these elements will be the ad that was selected at each round.
So we will clearly see the results of the strategy used by the algorithm.
Okay.
So as usual we. Need to. Initialize this.
And we are simply going to initialize.
It as.
An. Empty vector.
Because what we'll do next is to.
Append the different ads one by one.
Up to the. Last round. Round 10,000. Okay.
So now the question is how are we going to append the different.
Versions of the ad.
In. This ad selected vector.
Well let's go back to the slide.
Step three is we select the ad I.
That has the maximum upper confidence bounds.
So we already computed.
The. Upper confidence bound and now we need.
To create.
Another. Variable that will be the highest.
Upper confidence bounds.
Because right now.
This upper bound variable here is just the upper.
Bound for.
Each of the diverse versions of the ad at.
Round N.
And so that's why we need to create another.
Variable that will take. The maximum.
Of these upper bounds.
Here of the ten ads at round N.
So let's create this new variable.
And we're going to call it max upper bound.
So since this max upper bound variable is going to be different at each round.
Well we need to initialize it at each new round.
So therefore this variable.
Max upper bound will be.
Initialized right here.
So we will initialize this. Max upper bound.
Variable here to zero.
And then what happens is.
That we will compute the.
Different upper bounds of each of the ten ads.
And then we will compare. These.
Upper bounds to this max upper bound.
And each time the upper bound of the.
I here will be.
Higher than max upper bound, then we will set max upper.
Bound equals to upper bound.
So that's the idea.
So let's do that right now.
So basically what we have to do here is.
In this.
For loop we need to add. A new if condition.
And this condition. Will be if.
Upper bound larger than max upper bound.
And then what happens if upper bound is larger than the max upper bound.
Then we need to set max upper bound.
Equal to. Upper bound.
This way you know, what will happen is. That.
We will compute the different upper bounds of each of the ten ads at round n.
At first, this max upper bound is.
Equal to zero.
Then we compute the first upper bound.
And of. Course it will be larger.
Than max upper bound because it's. Equal to zero.
So then max upper bound.
Will be equal to upper. Bound. So that's for the first add.
And then we will compute.
The other upper bounds of the other ads.
And each time we find an upper bound that. Is larger.
The max upper bound then max upper bound will be.
Equal to this new upper bound. All right.
So this way we will.
Get the maximum of the different upper bounds of the ten ads at the
specific round n.
All right.
And now we need to do one more thing.
You know, we.
Need to select the ad that has the highest upper.
Bound.
And therefore each time we find this upper
bound to be larger than the max upper bound, not only.
We need to do this to. Keep the max upper bound.
But also we need to keep track.
Of the index that has the max upper bound.
And to. Keep track of. This index, what we need.
To do here is to create a new variable here, which we'll call ad.
And we will make.
It equal to I, because right.
Now we are dealing with a specific.
Ad because we are at a specific I of this for I loop here.
And so I here has a specific value that corresponds to a specific ad.
And so we need.
To keep track of this specific ad.
Each time we find an upper bound that.
Is larger.
Than the max upper bound to become this new max upper bound.
All right. So that's great.
But you know, when.
We use a new variable here, it's always.
Important to. Initialize it.
So that's what we'll do.
Right now we will initialize.
This ad variable.
We will initialize it.
To zero okay.
So we are getting close.
Now what we need to do is deal with the.
Initial conditions.
Because this is what happens. At round N.
You know this is the strategy.
That happens at round N.
But this is actually not what happens at the beginning.
Because at the beginning,
you know, during the ten first rounds, we don't have much information of the ads.
We don't have much informations. About their reward.
Whether they earned reward equals one or reward equals.
Zero when we selected them. Because simply we.
Haven't selected them yet.
So that's why we need to deal with.
The initial conditions, that.
Is, choose which ads we will select.
During the ten first rounds.
And so according to you, what will be the strategy to select the ads during the.
Ten first rounds?
Given the fact that we don't have any information?
Well, there's. Actually no. Strategy.
We will simply select the ten first.
Ads without using the strategy here.
We will use this strategy as soon.
As we have some informations of the.
Reward of each of the. Ten ads.
So basically what we'll do.
During the first ten rounds.
Is to simply select the ten first ads.
That is round. One. We'll select add. One.
Round two we'll select ad to round three we'll select
at three, up to round ten we'll select at ten.
And then
that will give us some information about, you know, the number of selections.
Of each. Of the ten. Ads.
Well at around 11 the number of selections will.
Be one. For each of the ten ads.
And we'll also get some information about the sums of.
Rewards.
The sums of rewards will contain either.
Zeros corresponding to the ads that go to zero reward.
When they were selected during the first ten rounds, or once corresponding.
To the ads that go to.
One reward when they were selected during the first ten rounds.
So let's do it now. Let's simply select add.
One at. Two at three, up to.
At ten during the first ten rounds, and then let's.
Use this strategy.
So to do this we will add.
A if condition. Here which will be.
If numbers.
Of. Selections.
I is.
Larger than. Zero.
So that means.
If. The ad version.
I was selected at least. Once, then we.
Will use this. Strategy.
And actually we need to align this.
And so now thanks to this condition.
Here, this strategy will be applied.
After the ten first rounds. Okay.
And now we. Just need to add a little.
Something to make. Sure that the. Algorithm.
Selects at one at two, at three of.
Two, at ten during the ten first rounds.
And to.
Do this the trick is to add.
An else. Here else.
And then. We will set the upper. Bounds.
To a very large value, like ten at the power of 400.
So to get this we can use one 400.
And that's ten to the power. Of 400.
So now I'd like to give you.
A little enigma.
I would like you to figure out why we're using this
very large value ten to the power of 400 for the upper.
Bound here in this else condition.
Try to figure out why.
Try to figure out how it will be useful for what we want.
And now I'll give you the answer in the explanation in the next tutorial.
Until then, enjoy machine learning.