Hello and welcome back to the course on Machine Learning.
Today we're talking about the multi-armed bandit problem.
Don't you just love these names when they come up?
Such cool names for machine learning algorithms and problems.
Well, today we're indeed talking about this problem.
And it is the example
that we're going to be using in this whole section on reinforcement learning.
We're going to be looking at different ways that we can solve
the multi-armed bandit problem and comparing the results.
But before we continue, I just wanted to mention that
the multi-armed bandit problem is not the only problem
that can be solved with reinforcement learning.
Reinforcement learning is actually really, really cool.
Reinforcement learning, for instance, is used to train robot dogs to walk.
And I'll give you a quick example.
For instance, you can once you've created a robot dog, you can implement
an algorithm inside the robot dog, which will tell it how to walk.
You can tell it,
all right, move your front right foot and then move your left back foot
and then front left foot, right back foot and so on.
You can actually give the sequence of actions
that it needs to take in order to accomplish a task which is walking.
Or you can implement a reinforcement learning algorithm
which will train the dog to walk, in a very, very interesting way.
So basically
what it will do is will say, hey dog, here all the actions you can take,
you can, move your legs like this, you can move your legs like that.
And, your goal is to make a step forward.
Every time you make a step forward, you are, given a reward.
Every time you fall over, you're, given a punishment.
And a reward is basically a one in the algorithm.
You don't actually have to give it a carrot or, you know, something, to eat.
You just give it a one.
An algorithm and a punishment is a zero.
And basically every time it takes a step forward, it knows it's got a reward.
And it will, yes, that's good for it.
So it basically will try all these random sets of actions
and see what they lead to.
Every time it takes a step forward, you'll remember that those were good actions,
and you'll try to repeat them more and more.
And actually, dogs like that can learn to walk.
so you don't have to program an actual walking algorithm into it.
It'll figure out the steps it needs to take on its own.
The I think that's really mind blowing and really cool.
but unfortunately, that is a more, a topic, more of
on the side of artificial intelligence rather than just machine learning.
And that is, you know, that can be a whole course on its own.
We're not going to delve into, training robot dogs to walk inside this section.
Inside this section,
we are going to talk about the multi-armed bandit problem,
which is a bit of a different application of, this machine
learning branch of reinforcement learning.
And plus, of course, there's other,
lots of other applications of reinforcement learning as well.
So moving on to our multi-armed bandit, problem.
So first of all, what on earth is a multi-armed bandit?
Right.
So the first thing that comes to mind, a is like a robber going into a bank
and so on, and, or somebody with a gun, but actually a,
a bandit or a one armed bandits.
So let's simplify things.
A one armed bandit is a slot machine, right?
It's one of these.
And, why is it called a worm on one armed bandit?
Well, it's got a bit of a history there.
back in the day, they used to have this, handle
on the right, and you can still see that in movies.
And maybe some places you can still find these slot machines
where you actually have to pull the handle,
because now they're all electronic, and you just press a button
right there, push with your push slot machines.
Whereas in the back in the day you had to pull the lever,
to make it work to like initiate,
the, the game and so hence the arm.
Yeah. But why is it called the bandit?
Well, because, these machines, they would actually,
you know, these
this is the one of the quickest way to lose your money in, in a casino,
they would take, I think it was like,
a 50% chance that they would take away your money back in the day.
So they would.
Of course, you would earn less than your,
you're actually winning.
And it was about a, you know, a 5050 chance whether or not you actually make a,
or you get a win or you, you lose money, but then they put a bug into them.
I think I read up a little bit online.
They put a bug into them that people who were playing
them were losing even faster than, or even more frequently and 50%.
So hence the name bandit, because it was basically robbing you of your money.
And, you know, one of the quickest way to ways to lose your money,
hence the multiple.
Oh, that's why it's called the One arm bandit.
and what is the multi-armed bandit?
Well, the market multi-armed bandit problem is kind of the challenge
that a person is faced when he comes up to a whole set of these machines.
When he doesn't have just one, he has, like, 5 or 10,
you know, programing examples.
We'll have, example of ten, but we won't be talking specifically
about these machines.
Of course. This is this is the historic problem.
you'll just now we'll see that there are many, many other applications, that,
even though it's called the multi-armed bandit problem, it's actually,
used to solve many other problems as well.
So, basically here you're faced with a challenge.
You've got five of these machines, right?
And, how do you actually play them to maximize your return?
from the the number of games that you can, actually play.
So you've, you know, you decided you're going to play,
you know, 100 times or a thousand times.
and you want to maximize return.
How do you figure out which ones of them to play?
in order to maximize your returns?
Well, the problem, you know, to describe the problem in more detail,
we've got to mention that, the, assumption here
is that each one of these machines has a distribution behind it.
So there's a distribution, of numbers
out of which or outcomes out of which the machine, picks results.
Right?
So, it has, it has sort of like each one of these machines
has its own distribution, and it picks out a result.
You pull the trigger and it just picks out randomly out of its distribution,
a result, an outcome, you know, whether you win or whether you lose
and how much you win and how much you lose.
or basically you lose the same mode you just put in the coin.
but basically it tells you whether you win lose
based on the, and distribution that's built into the machine.
But the problem here is that you don't know these distributions, right?
You don't know in advance what the distributions are.
And they are assumed to be different for these machines.
Sometimes it can be similar to the same, in some of the machines.
But by by default they are different.
And your goal is to figure out
which of these distributions is the best one for you.
So, let's have a look.
So there are these distributions. Right.
So for example, we've got these five machines, the five distributions.
And as you can see right away
just by looking at this which is the best machine right away,
obviously the one on the right, the orange one is the best machine
because it's got the best, you know, it's the most left skewed.
left skewed because the tails on the left.
So it's, it's got the most
favorable outcomes, got the highest mean median and mode.
And you, if you knew these distributions and what you would obviously
just go to the fifth machine and you would bet on the fifth machine
just on the fifth machine all the time because,
it's got the best distribution right.
So on average you would get the best results.
But you don't know that. You don't know that in advance.
And your goal is to figure out,
you know, it's it's like a it's like a mind game.
You know, how there's all these movies about, machine learning and really cool
or cool mathematics on how they're, using
their cool, really good movie was,
imitation game, right, about Alan Turing and,
and, and how he was solving the Enigma and so on.
But similar kind of concept.
You don't know which one of these is the best.
You got to figure it out.
But at the same time, you are already spending your money doing this right.
You can't just, you know, the longer you take to figure it out,
there's a trade off, right?
The longer you take to figure it out.
The, more money you will probably spend on the wrong ones.
and therefore, you have to figure out very quickly.
So there are these two factors that are in play, exploration
and exploitation.
So you need to explore the machines to find out
which one of them is the best one.
And at the same time, you need to as soon as you can already start exploiting,
exploiting these machines, exploiting your findings to make the maximum return.
So basically, and there's another mathematical concept behind
behind all this, which is called regret.
And a regret is is mathematically defined.
And if you want to read more about this as a goal,
there's a really good white paper on it.
It's called using confidence bounds for exploitation
and exploration or trade offs.
And it is by, Peter,
Euler or a
AQR from the University of Technology in Austria.
really like the white paper.
it goes into a lot of detail.
like I didn't even read the whole thing,
but the first couple of, chapters are pretty good if you want to go into detail.
But basically, regret is, is when it's suffered
when you're using non non alternative and not optimal method.
Right.
So the one on the right is the optimal
or the one on the right the optimal machine.
Whenever you're using the non optimal machine you have a regret which,
which can be quantified as like as the difference
between the best outcome and the known best outcome and the,
you know, all of those sums of the money that you put,
like your, opportunity cost of actually exploring the other machines.
And, so the longer you explore the non-optimal machines, that higher regret.
But at the same time, if you don't explore for long enough, right,
if you explore, if you don't explore for longer, long enough, then you're.
And a suboptimal machine might might appear as an optimal machine.
So for instance, this machine over here. Right.
So if we explore, explore, explore, but we don't spend enough time exploring,
we might think that this is the best machine
because it's got quite a good return right close to this one.
And we might start exploiting this one for the rest of the time.
But in reality, this one was the best one.
So the the, goal is to find the best one and exploit the best one,
but spend the least amount of time exploring all of them.
Right?
And while you're exploring is still earning money,
but not from the optimal machine. Right.
So that's the goal.
That's the point, of this whole exercise.
And it's important to understand here that, there is the best one so that where
even though these machines, you know, they,
have like jackpots sometimes.
And so on, but we are assuming that there's just that
these distributions are, finite there.
And out of them, there's a best one that you are looking for that's kind of the,
pre emphasis or the whole assumption on this problem if, there are
there are more complex options and versions of this problem and,
again, check out some additional reading on that topic.
That's, that's more or even more advanced.
But what are we going to be using this for is that's going to be sufficient.
And why is it going to be sufficient for us?
Because the most common modern application of this that we can, think of
and the one that we are going to be exploring is advertising.
But, so let's have a look at some ads.
This is going to be fun.
So just a disclaimer this there's no affiliation with Coca Cola.
Examples I used just for educational purposes.
All right. So let's have a look.
we have let's say Coca Cola or
some company wants to run a campaign.
and it's going to be called welcome to the Coke Side of Life campaign.
And if you search for this
campaign online, you'll see that they had, you know, hundreds of different ads
that so they came up with, for this campaign.
And here's here's one example of them where these are just some images
I pulled from Google.
So maybe these are even drawn by, people, but we're going to assume
that these are legitimate ads that, we're going to go into the campaign.
And so we want to find out which is the best ad,
which is the ad that works best.
So we've got options number one.
Number two, number three, number four, and number five.
And so now our goal is to find out which ad works the best.
Maximize our returns.
But right now we don't know which has worked the best. Right.
So there's no there is a distribution behind it, but that distribution
will only become known after thousands and thousands and thousands of people.
Look at these ads and click or not click on these ads.
And this is actually going to be very similar
to the example that we're going to be looking at.
The example that had land is going to be walking you through
in the programing tutorials.
And in that example we're going to have ten ads.
So even more.
And so the what can you do here.
Well one way to approach a problem is just run an AB test.
Right.
So take your five or 50 or 500 ads
and run a huge AB test, with or multiple AB test and,
wait until you have enough, of a, a large enough sample.
and then, conclude which ad is the best, right, with, with certain confidence.
But the problem with that is that you would spend
a lot of time and money doing that. Right.
So an AB test is pure exploration, right?
You're not exploiting the best option.
You are exploring the best option.
But, to the same extent as you're exploiting the non-optimal options.
Right.
So if, if we go by our previous distribution, if this is the best one,
if you just run an AB test and you're uniformly distributing
or uniformly using these, five options and therefore,
as much as you're using this one, you might using all for all four of them.
So basically all five of them.
So basically you are exploiting it a bit, but
unconsciously, right, in a random way.
and therefore AB tests are just for exploration.
So the challenge is to find out which is the best one.
But, do it while you're explore.
while, you know, to exploit the best one while you're exploring for it.
Right.
So find out which of them is the best one in the process of,
hold on to find out
which is the best one in the process of the actual launched campaign.
So not don't have two phases. Yeah.
And do the AB test and then use the most, the best one.
but actually find out the best one in the quickest way
possible and start exploiting it along the way.
So that's the challenge here.
And that's what we're going to be solving.
and that's the modern application of the multi-armed bandit problem.
So hopefully you're excited about this.
We've got two great algorithms coming up.
can't wait to get started.
I look forward to seeing you in the next tutorial.
And until then, enjoy machine learning.