An Introduction to Online Learning - Reinforcement Learning (contd) Video Lecture | What is Data Analytics? - Data & Analytics

alright so in the previous module we
started looking at the multi-armed
bandit problems and we will continue
looking at some of the solution
approaches for multi armed bandits so as
you recall in this case we have n
possible outcomes and you have to select
one of the actions from this set of n
actions and each action results in the
the war arrived from the probability
distribution associated with the action
that our goal is to find the most
profitable action so the goal is could
have different shades to it right so we
are interested in finding the best half
but then or how are we interested in
finding the best arm so the simplest
notion of solving the bandit problem is
to identify the character eventually
right regardless of how many ever
attempts we take as long as you can give
me a guarantee that eventually I will be
playing the best arm that is sufficient
but then if you want to get more
practical algorithms we have to look at
other notions of solving the problem
that if we look at two here so once the
first one is you would like to maximize
the total rewards that you obtain not
just the rewards that we obtain
eventually but also the rewards that we
obtain during the course of learning so
this is called sometimes minimizing the
loss or regret while learning so the
regret is how much better you could have
done if you had known the true solution
from the beginning right so that
quantity is known as the regret and you
would like to minimize the regret and
the second solution concept that people
look at is called probably approximately
correct solutions so I am interested in
finding an epsilon optimal arm the
epsilon optimal arm is such that the
mean of
select Adamu is within epsilon of NuStar
which is the expected reward for the
best arm I'm going to find an epsilon
optimal ah that gives me the
approximately correct part and then I'm
going to say that my algorithm will
surely return the epsilon optimal arm in
1 minus Delta fraction of the problem
instances so with probability 1 minus
Delta my algorithm will give you an
epsilon optimal arm so for fixed values
of epsilon and Delta we try to figure
out how many samples do I need before I
can give such a guarantee so the
probably approximately correct framework
the probably comes from the fact that I
am interested in returning solutions
with probability 1 minus Delta and
approximately correct because I am
interested in returning solutions within
epsilon of the true solution so the work
that the most simple traditional
approach is to essentially pull the arms
multiple times keep track of the reward
that you get over time so I would
estimate mu hat I as the sum of the
rewards I get when I pulled the arm I
divided by the total number of times I
have pulled all my that gives me an
estimate for the average reward I expect
to get when I pull on I and we know that
this is an unbiased estimator of the the
world and hence with enough samples as
time goes to infinity these will
converge to the true expectations and I
can derive the best on by just looking
at the with the maximum expectation
right to ensure that we select the arms
infinitely often use an epsilon greedy
strategy so you select the arm that you
currently think is the best of the arm
star that gives you the
max over all new hat I you select data
with a probability of 1 minus epsilon
and epsilon is some small constant like
point one merchant and it can select any
arbitrary arm with a probability epsilon
so this guarantee is that that every arm
will get selected and therefore as the
number of place goes to infinity then
every arm gets selected infinitely often
and therefore asymptotic convergence is
guaranteed for these kinds of epsilon
greedy action selection one of the
state-of-the-art algorithms that we will
look at is called median elimination
algorithm alright so this is a PAC
algorithm so it gives you probably
approximately correct guarantees and it
tries to control the sample complexity
it's got one of the best-known sample
complexity for solving yeah Palkia and
the problem right so let's to get an
intuition into how these things work
let's start by looking at it's simple
algorithm we shall call the knave
algorithm so you start off by sampling
each arm yellow number of times where L
is given by the expression here so it's
4 by epsilon squared long to N by Delta
so n is the number of arms the epsilon
will Delta are the constants from your
back results right so you sample an arm
each arm actually L number of times and
let P hat be the average reward of arm a
so the output is essentially the arm
that has the maximum of all the arms and
the expected reward sense right so this
obviously has a sample complexity of n
by epsilon squared and long n by Delta
but the real difficulty is to show that
it actually achieves the desired
performance guarantee that is that it
will with a very high probability of 1
minus the Delta you look at rather than
epsilon october long until fail only
with the probability delta
so we're not going to we're not going to
get into the mechanics of the proofs
it's quite beyond the scope of this
course but this I'm pointing out that
you can come up with simple algorithms
and you can often show that they achieve
the guarantees that you want right so
one of the drawbacks of the naive
algorithm is the complexity depends on
login by Delta so you cannot avoid the
order end term because you have to pull
each arm at least once but you want the
additional factors to be dependent only
on the epsilon and Delta you don't want
to have an additional dependence on n
India algorithm so even though at all
the Western action elimination procedure
which allows you to be pretty efficient
India finding the optimal arm it also
serves as the basis for many other
algorithms and their forms I'll spend a
couple of minutes looking at the meeting
the elimination algorithm the key idea
here is that after some number of
samples you are going to eliminate some
arms and then you're going to continue
sampling with the rest of the arms right
so here is the algorithm it looks a
little complex but it's nothing really
it's fairly straightforward right so you
start off by having a set of all the
arms available to you and start off with
an epsilon and on the Delta and start
off with L equal to 1 that means that
you're sampling L equal to 1 this is
essentially the first round so here now
you sample every arm that is left right
so in the first stage it will be they
all the arm set just many number of
times 1 by epsilon L by 2 squared log 3
by Delta L and let P hat al-noor this
empirical value so now what I have done
I've taken the arms you have pulled each
of them some number of times and from
that you have formed an estimate of the
average at water farm now what you do
you arrange these averages in some
sorted order let's say you arrange the
averages in ascending order all right
and then you take the
first half the half that is below the
median right so the half of the data
that is below the median you take those
and you eliminate them okay and now what
you're left with is half the arms which
had the highest possible expected mean
from the previous round so now you
repeat the whole thing again except that
you make your epsilon and your Delta
even smaller so with a little bit of
algebra you can actually show that this
gives you nice performance guarantees it
gives you a PAC result so it gives you
the epsilon Delta guarantees in addition
to that you can also show that it has a
sample complexity of N by epsilon square
log 1 by Delta we go off and we have
salams quite long 1 by Delta so we've
gotten rid off the end in the logarithm
that's a big step and it turns out that
I it's very hard to improve on we need
additional cover at least using these
kinds of processes that we were looking
at but in practice these kinds of PAC
guarantees are weak all right and
typically you can get acceptable
performance with far fewer samples and
the fact algorithms also do not care
about how your performance varies while
you are learning and hence increasingly
regret analysis of data is becoming more
and more popular so here is a very
simple algorithm that can be shown to
give very good regret performance all
right so you not only maintain the the
the the best estimates or the estimates
of the rewards that you have so far but
you also maintain some kind of an
uncertainty interval around the 1 right
so look at this orange curve here so
this is the means reward that I have but
then I also have an uncertainty or some
kind of a confidence interval here that
says that a
and my true reward with a very high
confidence would be within this interval
so you can see that for some arms even
though the the estimated mean rewards
are lower the uncertainty is much higher
and so what we really are looking for
this so if you have the best estimate
are and the other arms are played with
leave the upper bound of a suitable
confidence interval is at least R all
right but all of the simplest approach
this could be just be greedy with
respect upper confidence bounds you
estimate the upper confidence bond and
then you take actions that have the
highest upper confidence bow that's
obviously going to bear something higher
than R star and essentially in this case
you would play the arm red as opposed to
orange and blue even though RH has the
higher expected beam right so you can
show that the suboptimal arms or play it
fewer than eight by delta j times where
delta j is the difference between the
optimal arm and the suboptimal on and
this allows us to come up with very
efficient bounds for this upper
confidence bound algorithms called UCP
so the algorithm is very simple so at
any time you play the arm j that
maximizes xj bar which is your average
at what so far plus this funny
expression under the root root 2 lon n
by n j when n is the number of arms and
NJ is the number of times you have
played I'm J so far so that expression
actually comes from estimating upper
confidence bonds and this helps us show
that the suboptimal arm can be played
and will be played fewer than 8 by delta
T in all n times so what are the
implication of all of this I'm giving
you a lot of numbers but in practice you
don't really have to worry about these
numbers because all you're interested in
is figuring out with the fewest number
of samples can I estimate what the
outcome will be all right and you see B
essentially gets you there very quickly
even though it doesn't guarantee that it
gives you the best outcome by
reaches there then it reaches close to
the best outcome pretty quickly right so
I was talking about showing ads there's
one of the use cases but if you think
about it for each user you would like to
show different guides you don't want to
show the same ad to different users
right but if you are using a single
bandit algorithm that is learning the
Preferences of all the users that's what
you will end up doing right so one
solution at all this is to build one
bandit for each user right but given the
large volumes of users that are likely
to come to your page and the
restrictions on computation and search
that is not feasible so what we do yes
you typically share features across
different users right it could be
demographic features it could be
browsing history could be location or if
we're talking about patient data it
could be history
in the patient history so it could be a
variety of different features that you
would share and your expected reward for
getting the for pulling then arm will
now be the presenter as a function is
supposed to being a number is a function
of these features right as opposed to
being a single estimated number so you
can solve this in many different ways
you can assume that each user is
represented by a set of features it
could be set up joint features of the
user and of the arm right and the
statistics used for choosing arm is now
dependent on this feature is essentially
what I was telling the statistic in some
cases can just be the mean the war it
could be the upper confidence bond and
variety of things right so the simplest
case is to consider that for each
feature combination you have a different
bandit and once a choice is made as a
stochastic transition to another bandit
it's just to make it conceptually easier
right but that's not really the case
because each of these bandits are
to be closely interacting because the
feature values might be similar in which
case the outcomes for one bandit could
be the same for other bandits right so
earlier work there was on associative
bandits right where they typically use a
small number of states to encode these
features and you don't really worry
about functional representations for
thee so once I have a function that is
going to output a value a real value as
a function of features what you do you
think of doing exactly so we could do
linear regression right so so bad you
see B variation where you use linear
regression to predict T the mean rewards
and you use a upper confidence born
right from the linear regression
algorithm
it's called Lin NUCB and it's one of the
more popular contextual bandit
algorithms out there all right so the
expected reward is assumed to be a
linear function of the features people
typically end up using rich in
regression which is l2 penalized linear
regression to fit the parameters and you
can drive upper confidence bond for the
regression frame right so it gives
better performance with lesser training
data all right so this here is a simple
set of results for predicting
click-through rates on ads and you can
see that if only one percent of the add
data is available for training available
for estimating the parameters you could
see the limb NUCB methods which are this
and this do much better right then
regular youcb methods which don't do
this generalization across different
users so you can see that 5% data again
so the lin NUCB variants are doing
better but then if you have a lot of
data available for training you could
see that the other methods pretty much
catch up with when you see B so the idea
here is that when you see B you
better performance with lesser training
data right and so people now are looking
at more partial approximations looking
at Gaussian processes looking at other
more complex sampling techniques a lot
of work going on it's very active area
so people are looking at budget red band
ads people are looking at case where
there are adversarial bandits and then
people are looking at dependencies
between samples and multi slot cases and
many many many different problems that
people are studying in the valid
literature thank you one thing of
interest is to consider what I call a
full reinforcement learning problem in
the contextual bandit case so you have a
context the user comes and picks an
action and after that you just move on
to another user right but in the full
reinforce polemic problem so you have to
make a sequence of decisions before you
can truly solve the problem so we're
faced with the situation or a state or a
set of features you take an action and
then that results in the set of features
being changed and then you have to take
another action and another action and
another action until the problem is
solved so think of the question of
writing a cycle right all of you know
how to write cycles but think of how we
learn to write a cycle right so you
didn't learn it through supervised
learning
there is nobody telling you how to turn
the hub what pressure to put on a pedal
and what angle you should tilt your
upper body and things like that if
people have been telling you the
technical aspects of cycling he probably
will never learn to cycle all he knew
was get on the cycle and make sure you
don't fall off or if you fall off and
you get hurt you don't do the thing
again the next time and soon you find
yourself cycling right so this is
essentially a form of reinforcement
learning where each action you take I
mean if you make a bad move we are just
going to keep tilting until you fall
right so each action you think causes a
change in the state and you have to
compensate for that and then continue
learning right so this is called the
full tree enforcement learning problem
and the ideas that we describe here
back home DP and optimal exploration and
so on so forth
have been extended to the reinforcement
learning problem as well so here not a
couple of little few tutorials and
source material for learning more about
bandits if you are interested so that
brings us to the end of the bottom thank
you