PAC bandits
===

Author

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

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

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)