# [Multi-Armed Bandits and how to solve them](#)

###### tags: `Blog` `bandits` `PAC` `UCB` `epsilon-greedy`

#### Author
[Raj Ghugare](https://github.com/RajGhugare19)

# [Multi-Armed-Bandit problem](https://en.wikipedia.org/wiki/Multi-armed_bandit)

Author

[Raj Ghugare](https://github.com/Raj19022000)

###### tags: `notes` `multi-armed bandits`

### Introduction :
* Multi-armed bandits is a rich area of research on its own but it is often treated by the RL community as an immediate RL problem. It scales down the more intricate details of full RL problems while maintaining the same gist.
* The basic setup of a K-armed bandit problem is as follows:
* There are K number of arms, $A = {0,1,2.....K}$ is the Arm set.
* Each time an arm is selected a reward will be generated, sampled from any distribution but specific to every arm.This means that every arm will have its own reward distribution.

Before we start off, lets get aquainted with the notations
* $q_*(a)$ is the true value function of all arms.
* $Q(a)$ is our empirical estimate of the true value function of all arms.
* $k$ is the number of arms.
* $a^*$ is the true best action.
* A is the set of all arms.

### Solutions :

There are three ways in which we can the think of the solutions for a bandit problem :

1. ##### Asymptotic Correctness :
As the name suggests this concept of a solution will guarantee that eventually the agent will reach the optimal arm. Old and naive techniques like Epsilon-greedy and softmax exploration techniques will provide you with an asymptotic solution.

2. ##### Regret Optimality :
Rather than just asymptotically converging towards the solution this puts up another level of optimality by trying to maximise the likelyhood of reward that we obtain initially while exploring.Many algorithms like UCB and its variants try to maximize the expected reward while exploring.

3. ##### Pac optimality :
Given an ($\epsilon$,$\delta$) pair, the agent should return an arm with a gaurantee that the value of that arm should be within $\epsilon$ limits of the value of the true best arm with a probablity of 1-$\delta$.In mathematical terms
$$pr[q_*(a) \geq q_*(a^*) - \epsilon] \geq 1 - \delta $$
where $\epsilon$,$\delta$ $\in [0,1]$

### Implementation :

Every algorithm was tested with 10 arms having a bernoulli distribution with :
$q_*(a) = [0.1, 0.5, 0.7, 0.73, 0.756, 0.789, 0.81, 0.83, 0.855, 0.865]$

`NOTE`
> You can change the distribution to a gaussian by using the GaussianStationaryBandit imported from bandits class

### Results :


This graph does not tell you the complete story as there are many other aspects of a multi-armed bandit problem like regret,noisy rewards,$(\epsilon,\delta)$ guarantees etc.
You can easily run these algorithms by importing my implementation and testing them out in various conditions.

Regret Optimalities
===

Author

[Raj Ghugare](https://github.com/Raj19022000)

###### tags: `notes` `multi-armed bandits` `Regret` `UCB`

Topic of discusion:

Upper Confidence Bounds for multi-armed bandits

## Review and research notes

### Introduction

* Optimizing regret for a multi-armed bandit is basically adding a new dimension of optimality or correctness rather than the naive asymptotic guarentees.
* It focuses on maximising the expected reward during learning process; i.e. during exploring to gain insight on all arms.
* Regret in the sense of our problem is the expected reward we could have obtained if we have had chosen the best arm since the start.
* Therefore, for any time step n the regret :
$z_n = q_*(a^*) - q_*(a_n)$

### Notion behind UCB :
* Upper Confidence bounds as the name suggests tries to determine an optimistic upper bound to the value of every arm even if the arm isnt explored many times.
* We then chose the arm which has the luxury of our higest confidence.
* The upper confidence bound for an arm j is :
$Q(j) + \sqrt{2ln(n)/n_j}$

* Where :
$n$ is number of trials we've played.
$n_j$ is the number times we've played arm $j$.
* The second term in the bound is the optimistic factor which is inversely proportional to $n_j$ because, as the number of times we try that arm increases it is only obvious that we'd be surer about its empirical value and not be over optimistic about it. The $ln(n)$ is just a normalising term which does not affect any action relative to the others.

* The only question remains is that how did we get to this magic term?
$\sqrt{2ln(n)/n_j}$

### UCB1:
* Initialization - Play each arm once
* loop :
Play the arm j that maximises the term
$Q(j) + \sqrt{2ln(n)/n_j}$
##### Note
This algorithm assumes that the rewards are binary.

### Reaching the algorithm:

#### Notatations :
$\sqrt{2ln(n)/s} = C_{n,s}$
$I_m(i) = indicator function$ which takes the value 1 if ith action is played at time "m", else it takes a value of 0.

Let's try and formalize our problem first and realize that we need to mathematically define regret and bound it.

* $T_i(n)$ be a random variable specifying the number of times an arm $i$ is played in the first $n$ trials.
* $\Delta_i = q_*(a^*)-q_*(i)$

Hence we can define the cummulative regret for the first n trials as:
$Z_n = \sum_{x = 1}^{|A|} E[T_i(n)]\Delta_i$
The expected number of times we play arm *i* in the first n trials multiplied by its distance from the true value of the best arm.

We have to prove that using our upper confidence values($Q(a) + \sqrt{2ln(n)/s}$) we can bound the regret as well.

It is evident from the above equation that we cannot calculate regret, as the true action values are unkown and $T_i(n)$ is also unkown at the start of them problem.

To bound the regret lets first try and bound $T_i(n)$
Let's assume that we've played n trials according to our algorithm.
Hence for any arm $i$

$T_i(n)$ = 1 + $\sum_{m = K+1}^{n}$($I_m=i$)

Because we have to play each of the K arms once. To try and upper bound,we write $t_i(n)$ in this manner:

$T_i(n) \leq l$ + $\sum_{m = K+1}^{n}$($I_m$ && $T_i(m) \geq l$) --(i)

We take an arbitrary number $l$ which we'd later optimize. Don't worry about $l$ right now,as we have to decide a suitable value for it.Two cases arise
Case 1: In our experiment we play $ith$ arm more than $l$-times
Then the equality sign will hold.
Case 2:If we play the arm less than $l$-times
Then the equation would have a strict inequality.

Hence you should be able to see how the RHS is an overcount of the former one. Now,

$T_i(n) \leq l$ + $\sum_{m = K+1}^{n}$($Q(a^*)+C_{m-1,t_a*(m-1)}\leq Q(i)+C_{m-1,T_i(m-1)}$ && $T_i(m) \geq l$) --(ii)

We know that according to our algorithm we'd chose the $ith$ arm when our upper confidence estimate for it is more than all other arms. Let $E_2$ be the event when the upper confidence estimate for $ith$ arm is atleast better than the true best($a^*$) arm. It should be now understood than $E_2$ is an overcount of the actual number of times we'd play the arm $i$.Hence the $\leq$ sign remains.

Now let's take a further overcount:
$T_i(n) \leq l$ + $\sum_{m = K+1}^{n}$$(($$min_{0<s<m}$($Q(a^*)+C_{m-1,t_a*(m-1)})\leq(($$max_{l\leq s_i \leq m}$$Q(i)+C_{m-1,T_i(m-1)})$ && $T_i(m) \geq l$) --(iii)

Now, we are counting every time the maximum of upper confidence estimate of $ith$ arm from the $lth$ time step to the $mth$ one is greater than the minmum of the upper confidence estimate of $a^*$ from the $0th$ to the $mth$ time-step. Try to think of how the event used in RHS of (iii) equation will take place atleast the number of times the event in the RHS of (ii) equation. In other words the RHS of (iii) will surely take place if RHS of (ii) has occured.

A further overcount to get rid of all the comparing signs is

$T_i(n) \leq (\sum_{x = a}^{b} \sum_{s=1}^{m-1} \sum_{s_i=l}^{m-1}(Q_s(a^*)+C_{m-1,T_{a^*}(s)} \leq Q_{s_i}(i)+C_{m,T_i(s_i)}$) && $T_i(m) \geq l$)

if for any values $s$ or $s_i$:
$Q_s(a^*)+C_{m,T_{a^*}(s)} \leq Q_s(i) + C_{m,T_{i^*}(s)}$

This implies that either of the three things must've atleast occured

1) $Q_s(a^*) + C_{m,T_{a^*}(s)} \leq q_*(a^*)$
This means that the optimistic upper confidence value for $a^*$ is wrong,the true value of $a^*$ is even higher.

2) $Q_s(i) - C_{m,T_{i}(s_i)} \geq q_*(i)$
This means that the the value of $ith$ action has been grossly over-estimated by a factor greater than $C_{m,T_{a^*}(s)}$

3) $q_*(a) \leq q_*(i) + 2C_{m,T_i(s_i)}$
This says that the $ith$ arm is very close to the true best action in value and hence mistakes are bound to happen.

Using Chernoff hoeffding bounds
* Probablity of event 1
$pr(Q_s(a^*) \leq q_*(a^*)-C_{m,T_{a^*}(s)}) \leq m^{-4}$
* Probablity of event 2
$pr(Q_s(i) \geq q_*(i)+C_{m,T_{i}(s_i)}) \leq m^{-4}$
* Now we'll chose $l$ in such a way that event three never occurs.
If we chose $l = 8ln(n)/\Delta_i^2$ then:
$q*(a)-q_*(i)-2C_{m,T_{a^*}(s_i)} > q*(a)-q_*(i)-2\sqrt{2ln(n)/l} > 0$ ; for $l = 8ln(m)/\Delta_i^2$

Hence if we play the $ith$ arm more than "$l$" times then:

$E[T_i(n)] \leq E[l] + \sum_{m = 1}^{\infty} \sum_{s=1}^{m-1} \sum_{s_i=l}^{m-1}(2m^{-4})$

Because the the occurence of an event is counted as $1$ and its absence is counted as $0$, its expectation will be its probablity of occuring.($m^{-4}+m^{-4}$)

$E[T_i(n)] \leq 8ln(n)/\Delta_i^2 +1+ \sum_{m = 1}^{\infty} (2m^{-2})$
The above step is just algebraic manipulations.The next step uses a result from [basel's problem](https://en.wikipedia.org/wiki/Basel_problem)
$E[T_i(n)] \leq 8ln(n)/\Delta_i^2 + 1 + \pi^2/3$

multiyplying both sides by $\Delta_i$ and taking a sum over all actions we obtain :

$\sum_{i}E[T_i(n)]\Delta_i \leq \sum_{j \in A}8ln(n)/\Delta_j + \sum_{j \in A}(1+\pi^2/3)\Delta_i$

Hence this proves that the UCB algorithm does actually bound regret.

##### Note:

Don't just read these proof, instead try and understand how the author of the algorithm must've thought while coming up with this.Try to understand the amount of hardwork it would require to come up with any one of these steps by yourself.This would give you a direction if you are trying to come up with an algorithm of your own.

Go through this excellent article by Jeremykun on [UCB](https://jeremykun.com/2013/10/28/optimism-in-the-face-of-uncertainty-the-ucb1-algorithm/) if you need further clarity or different approach of understanding.

PAC bandits
===

Topic of discussion:
[PAC Bounds for Multi-Armed Bandit and Markov Decision Process](https://link.springer.com/chapter/10.1007/3-540-45435-7_18)

## Review and research notes

### Introduction

* The motivation for this paper was to provide a novel way of solving the immediate RL problem of Multi-armed bandits with a better sample complexity(number of time steps the agent takes to return an arm).
* *What exactly does it mean to get to an optimal solution of multi armed bandit problem?* This paper addresses a Probably Approximately Correct(PAC) way to solve the problem.
* Given an ($\epsilon$,$\delta$) pair, the agent should return an arm with a guarantee that the value of that arm should be within $\epsilon$ limits of the value of the true best arm with a probability of 1-$\delta$.In mathematical terms
$$pr[q_*(a) \geq q_*(a^*) - \epsilon] \geq 1 - \delta $$
where $\epsilon$,$\delta$ $\in [0,1]$
Where a is the action returned and $a_*$ is the most optimal action.
$q_*(a)$ is the true value function.

Before we start off with discussing the methods, lets get acquainted with the notations
* $q_*(a)$ is the true value function of all arms.
* $Q(a)$ is our empirical estimate of the true value function of all arms.
* $k$ is the number of arms.
* $a^*$ is the true best action.
* A is the set of all arms.

NOTE
Instead of just jotting down the technical details of the algorithm I would like to take an intuitive approach of reaching the solution by starting off with a logical approaches and the mathematical evidences to back it up and then eventually reaching the algorithm

### Prerequisite mathematical knowledge :

##### [Markov inequality](https://en.wikipedia.org/wiki/Markov%27s_inequality)
* The probability that X, a non negative random variable,is greater than "a", is less than or equal to the expectation of X divided by "a". Mathematically
$$pr[X \geq a] \leq E[X]/a $$
$$E[X] = \sum_0^\infty x^*pr[X=x]$$
* In this formula, instead of x, for all values of X $\geq$ a we put in a. Hence the total sum is bound to be greater than or at the least equal to this new RHS.

##### [Chernoff Hoeffding bound](https://en.wikipedia.org/wiki/Hoeffding%27s_inequality)
* This is used put a bound on our estimated expectation of a random variable, given the number of times we sample that variable from its distribution.
1. Let x₁,x₂ ... x_t be random variables with a common range within [0,1].
2. E[ x_t | x₁,x₂....x_t-1 ] = $\mu$ for all t
3. S_n = (x₁ + x₂ + ... + x_n)/n
ie S_n is the empirical mean of x after sampling it n-times.
4. Given these conditions the Chernoff Hoeffding bound says that :
$$pr[S_n \geq \mu+\epsilon] \leq exp[-2\epsilon^2n] $$
$$pr[S_n \leq \mu-\epsilon] \leq exp[-2\epsilon^2n] $$
5. How does it apply to our situation?
We are trying to estimate the true expected payoff of each arm by sampling their rewards at different time steps.For a particular arm "a"
* Reward is the random variable
* q_*(a) is $\mu$
* n is the number of times arm "a" has been pulled.(often confused with the total time-steps)
* Q(a) is S_n, because we are maintaining Q(a) by calculating the mean of all the previous sampled rewards of arm "a" after every time step.

### Methods

##### 1. Naive PAC algorithm:

Now that we have the prerequisite tools, what would be the first step toward solving this problem ?
We know that if our algorithm manages to return an arm "a", which is epsilon close to the best arm in value, we are safe. So lets think of providing an assurance that this will happen eventually, or, in slightly more relevant terms, lets try to bound the probability of us going wrong by $\delta$.

Let a' be any non-optimal arm,
i.e., $$ q_*(a') < q_*(a^*) - \epsilon $$

It is clear that we don't want to return such an arm. But our algorithm *could* (could is used Because its estimate should be higher than all the arms for it to be actually returned) return it if our estimate for this arm is higher than that of the real best arm.
i.e., if, $$Q(a') > Q(a^*)$$

Obviously, we would want to bound the probability of this event happening.

$$pr[Q(a') > Q(a^*)] \leq pr[Q(a^*)<q_*(a^*)-\epsilon/2] + pr[Q(a')>q_*(a')+\epsilon/2] $$

$$pr[Q(a') > Q(a^*)] \leq 2exp[(-\epsilon^2l)/2]$$

* The first equation tries to bound the probability of the event that our estimation of a non optimal arm (a') is greater than our estimation of the real best arm (a^*) by the probability of another event which is *atleast as likely to happen*. In simpler terms, our estimation *could* go wrong if we either have under-estimated the best arm by more than $\epsilon$/2 or over-estimated the arm $a'$ by more than $\epsilon$ /2. This is what the RHS of the first equation denotes.Another point of view to encapsulate this is that if neither of two events on the RHS happen, then there is no chance that the event on the LHS will occur, because there is atleast gap of $\epsilon$ between the true values of $a'$ and $a^*$.
* The second equation is obtained by applying the Chernoff Hoeffding bound.Here, *l* is the number of times action a' was pulled.

It is in our hands to decide the value of *l* now. We know that the probability of error should be smaller than $\delta$.And hence for each action it should be lesser than $\delta$/k.To find the value of *l* we equate

$$2exp[(-\epsilon^2l)/2] = \delta/k $$

$$l = (2/\epsilon^2)log(2k/\delta)$$

Now that we've obtained the number of times we should pull every arm(l) our naive algorithm is ready:

1. Sample every arm "a" (2/$\epsilon$²)log(2k/$\delta$) times
2. Let Q(a) be the average of all *l* rewards
3. Output $a^*$ which is argmax_a(Q(a))

Another important thing about PAC algorithms is their sample efficiency.Since we sample every arm (2/$\epsilon$²)log(2k/$\delta$) times, the sample efficiency of this algorithm is O((k/$\epsilon$²)log(k/$\delta$).

##### 2.Median Elimination method :
Instead of pulling every arm a fixed number of times and then deciding the best one,this algorithm pulls every arm for some number of time-steps and then eliminates half of the inferior arms and repeats the same thing again until it is left with only one arm. It should be clear that this will require log₂(k)(because half arms are eliminated at each round) of such rounds to return an epsilon best arm.
* *l* = the current round.
* $\epsilon_l$ is the epsilon for *lth* round.
* $\delta_l$ is the delta for the *lth* round.
* $S_l$ is the set of all arms in the *lth* round.

Let's take a look at the algorithm first and then understand the intuition behind it.

##### Median Elimination($\epsilon$,$\delta$):
1. Set $S_l$ = A ,l=1
2. $\delta_l$ = $\delta$/2
3. $\epsilon_l$ = $\epsilon$/4
4. repeat :
* sample every arm $a \in A$, $\frac{2log(3/\delta_l)}{\epsilon_l^2}$ times
* find the median of Q(a) and denote it by $M_l$.
*let
$$S_{l+1} = S_l \sim {a : Q_l(a) < M_l}$$
This means that we remove all the arms that are lower in value than the median(half of the arms).

* Let,
$$\epsilon_{l+1} = \frac{3\epsilon_l}{4}$$$$\delta_{l+1} = \frac{\delta_l}{2}$$$$l = l+1$$
until $|S_l|$ = 1

This might seem cumbersome, but it is just a clever modification of the naive algorithm. To provide an ($\epsilon$,$\delta$) guarantee we normally try to bound the probability of going wrong by $\delta$. But now that our algorithm works in rounds, we need to bound the probability of going wrong for every round.This was how the developers of this algorithm must have thought while trying out this "every round PAC" style.

let E be the desirable event that after every round our losses in the best arm shouldn't be more than $\epsilon_l$, ie
$$pr[E] = pr[max_{j\in S_l} q_*(j) \leq max_{i\in S_{l+1}} q_*(i) + \epsilon_l]$$
Event "E" might not occur if the subsequent two events take place
1. The algorithm grossly underestimate the value of the best arm at *lth* step.Let $E_1$ be this event.

Let
$$ E_1 = Q(a_l^*) < q_*(a_l^*) - \epsilon_l/2 $$
Where, $a_l^*$ = the real best arm at round *l*.
We apply the Chernoff bound to the probability of this event and obtain:
$$pr[E_1] \leq \delta_l/3 -(i)$$
2. Given that the first event($E_1$) doesn't occur, still we could grossly over-estimate |S_l|/2 bad arms to be empirically better than the real best arm at round *l*.

Given that E₁ doesn't occur,
$$E_2 = Q(j) \geq Q(a_l^*)| !E_1 $$
where, j is not an $\epsilon_l$ optimal arm.Hence $E_2$ is the event where we grossly over-estimate a non optimal action j,given $E_1$ doesn't occur.We again apply Chernoff bound to place an upper bound on its probability.
$$pr[E_2] \leq pr[Q(j) \geq q_*(a_l^*) + \epsilon_l/2 | !E_1] \leq \delta_l/3$$

To fail, we need $\frac{S_l}{2}$ arms like non $\epsilon_l$ optimal arms(like j) to be empirically better than $a_l^*$
Lets #bad be the number of bad arms for which $E_2$ holds.

Therefore, we have an upper bound on the expected number of #bad arms.(sum of the probablities of every arm going being a #bad arm($\sum_{a = 1}^{|S_l|} \delta_l/3$))

$$E[bad|!E_1] \leq |S_l|(\delta_l/3)$$

Now we use the Markov inequality to find probability that the number of #bad arm is atleast $|S_l|/2$

$$ pr[ bad \geq \frac{|S_l|}{2} |!E_1] \leq \frac{|S_l|(\delta/3)}{|S_1|/2} = 2\delta/3 -(ii)$$

Since (i) and (ii) are the probabilities of two unfavorable and independent events we can add them directly to obtain the upper bound of the failure at the *lth* round

$$pr[E] = pr[max_{j\in S_l} q_*(j) \leq max_{i\in S_{l+1}} q_*(i) + \epsilon_l] \leq \delta_l$$

We have proved that the algorithm can give an ($\epsilon_l,\delta_l$) guarantee for every round,we just need to prove that
1. $\sum_{l = 1}^{log_2(k)} \epsilon_l \leq \epsilon$
2. $\sum_{l = 1}^{log_2(k)} \delta_l \leq \delta$

Which can be easily shown as the series of coefficients of epsilon's and delta's converge to 1 when extended till infinity. Since they only reach upto $log_2(k)$ they are always less than one.

Check out my Python implementation of Median Elimination methods [here](https://github.com/Raj19022000/RL-research/tree/master/Unit1-Multi-Armed-Bandits)