Hello and welcome back to the course on Machine Learning.
I hope you enjoyed the previous tutorials, and now you're quite confident
with the upper confidence bound
and the Thompson sampling algorithm, or at least the intuition behind them.
And today
we're going to quickly compare the two because they do solve the same problem.
They solve the problem of the multi armed bandit.
And let's have a look at some of the pros and cons of each of the algorithms.
So of course there's lots and lots of different
advantages and disadvantages and differences between the two.
But we'll just highlight the main ones.
So here we've got the two algorithms on the left.
We've got the UCB and the image from the intuition tutorial
that will help us to remember what it's what it's about.
And the Thompson sampling algorithm and same the image behind it.
So, the first characteristic is probably
that is different is that, that the UCB is a deterministic algorithm.
And actually there's lots of different,
there's lots of different, modifications to the UCB algorithm.
And you can find them online.
There's lots of different white papers
on how the YouTube algorithm can be modified to improve it and to,
make it better at, one thing or like ads, one advantage made.
It makes this, a bit better a result, but
it makes it more computationally intensive or the other way around and so on.
So, but all of that, all of those algorithms belong to a family, of UCB
algorithms or upper confidence bound algorithms, which are all deterministic.
And basically it what that means is, is that it is very straightforward.
Right? So, once,
you have
a certain round, it is very, it's very straightforward.
What's going to happen.
You just look at the upper confidence boundary, whichever one has the highest.
That's the one you pick.
you pull the algorithm. Yes.
you pull, you pull the lever. Yes.
Then you do get, like a random value from the machine, but that's,
that's that's the it's, that's on the side of the machine.
So that's randomness is on the side of machine.
On the machine.
And then, but then whatever value you get, it is very determined.
It's very deterministic what the UCB is going to do with that value.
and so all of the steps that the UCB actually takes,
they're very deterministic.
They there's no randomness in the algorithm itself.
Whereas on the other hand, the Thompson sampling algorithm is a probabilistic
algorithm because in the algorithm itself it has these distributions
which represent our perception of the world and where
we think the actual expected returns of each of those, machines might lie.
And therefore, every time we are,
implementing or, iterating in the Thompson sampling algorithm,
we actually generate random values from those distributions. So
if you rerun around in the UCB algorithm,
just one given round, after you've received the value from
the previous value from, the machine, and then you rerun
the round, it's always going to be the same result.
Whereas in the Thompson sampling algorithm, after you've received
the previous value from the machine and you rerun the current round,
it's all it's always going to be different because you're always,
sampling from your distributions,
which, characterize your perception of the world.
And, that is a whole different type of algorithm.
It's a probabilistic algorithm.
And those two things, they actually have, a few different,
implications. Right.
So, for instance, one important one is that
the UCB requires an update at every round.
Right?
So, basically the value that you get back from the you, from the machine.
So once you've pulled the lever and you get a value back
from that machine, that value, you have to incorporate it right away
in order to proceed to the next round.
You cannot proceed to the next round until you have, incorporated that value
until you have made an adjustment, to the algorithm based on that value.
because if you don't make the
adjustment, then nothing changes and you're going to be stuck.
Whereas in the Thompson sampling, it can accommodate delayed feedback.
And this is very important.
This basically means that if you pull the lever and you only will get,
the result, or you will only know the result
of pulling the lever, 500 rounds down the track, right?
Not right away.
You'll only get to know the result 500 rounds later.
The Thompson sampling algorithm will still work.
Why will it still work?
Because, if you now run,
the algorithm without even updating your perception of the world,
you still going to get a new,
set of hypothetical,
bandits, right?
You're going to generate a new a new expected return for every band
because you are generating them in a probabilistic manner.
And this is very important to understand because, this gives the Thompson sampling
that advantage,
that you don't have to update the algorithm with the result every time.
And in terms of, I mean, in terms of vendors, of course, it doesn't,
really matter that much because if you're playing in the casino and,
or if some hypothetical person is playing in the casino
and they're pulling these levers,
they get see the results right away so they could update the algorithm.
But in terms of websites and ads, that is a big deal, right?
So not even just, not even just,
displaying ads, on, on a website.
Or you could use this for like AB testing different instead of AB testing.
the different, layouts of your website.
Right.
You could, you could use, a Thompson sampling algorithm to,
have that power, balance between exploitation, exploration.
Right away.
So basically anything you're doing on the web with Thompson
sampling or like, solving a, multi-armed bandit problem
for your business or for a business on on the web.
you you're getting all these thousands and tens of thousands of clicks, right?
And to update the algorithm right away, that would be very
highly computationally, or computationally costly.
or it might require additional resources and, complex process.
Whereas if you,
what is what the Thompson sampling algorithm allows you to do is to
update your data set or your information algorithm in a batch manner.
So you you wait until you get 500 clicks, or you wait until you get 5000 clicks,
you update the algorithm, then you let it run
and then it runs, runs, runs, and then you get another 5000 clicks and then,
you update the algorithm again and it will still work.
And that's a very, important thing.
That's that flexibility that the Thompson sampling algorithm creates.
And, finally, again, we're not going to go into too much detail
on the pros and cons, but, the,
Thompson sampling algorithm is actually
it has better empirical evidence than they used to be.
And, they you will find this phrase better empirical evidence.
And that's because up until recently, the,
the theory behind the Thompson sampling algorithm or,
you know, the whole research wasn't it wasn't complete.
It's only been researched very detail in a lot of detail just a few years ago.
And, you know, now you can find, like, a lot of information on the Thompson
sampling algorithm, but previously people just see that,
from experimental evidence,
the Thompson sampling algorithm does work better than the UCB.
And that's exactly what we're going to see.
spoiler alert.
That's exactly what you're going to see
in the, practical tutorials for this section.
So we're going to be now
coding the Or Hudlin will walk you through coding the same,
exercise, the same problem that we had previously with the UCB.
Now we're going to be
or you're going to be solving it with, the Thompson sampling algorithm.
And you will see actually some very interesting results.
So we'll leave it at that.
And, I hope you enjoyed these intuition tutorials.
And off we go to the practical side of things.
Can't wait for you to get started.
Had lunch will show you all around and I'll see you back here next time.
And until then, enjoy machine learning.