# Find bound on my tail distribution

hope you have a nice day. I try to find an (exponentially) decreasing bound on a tail distribution. Reason: I want to create and find the expected cumulative regret (and confidence bounds) for a bandit algorithm.

## So here comes my problem:

$$X_k$$ are $$K$$ independent random variables (my bandit's arms).

The (estimated) averaged win probability of k versus the other random varialbes is $$W_k = \frac{1}{K-1}\sum_{i=1;i\neq k}^KE[X_k>X_i].$$ (This is how my bandit defines success)

$$\hat{X}_{k, t_k}$$ are $$t_k$$ samples of $$X_k$$ where $$\hat{X}_k^j$$ is the j-th sample we got from $$X_k$$ (The results of $$t_k$$ plays of arm $$k$$).

Using $$E[\hat{X}_{k, t_k}>\hat{X}_{i, t_i}] = \frac{1}{t_k \cdot t_i}\sum_{u=1}^{t_k}\sum_{v=1}^{t_i} \{\hat{X}_k^u > \hat{X}_i^v\}$$ we can calculate an empiric estimation of $$W_k$$: $$\hat{W}_k^m = \frac{1}{K-1}\sum_{i=1;i\neq k}^K E[\hat{X}_{k, t_k}>\hat{X}_{i, t_i}].$$

Now, I want to have an exponentially decreasing bound on its tail, like $$Pr(W_k>\hat{W}_{k,m}+c)\leq e^{-c^2m/2}$$ from Chernoff-Hoeffding.

Here I have two problems:

1. $$m$$ is something like the number of times we have samples $$W_k$$; but $$W_k$$ is never sampled directly, but calculated using $$\hat{X}_{k, t_k}$$, which are sampled $$t_k$$ times each. So, what is $$m$$ here?
2. IS $$\hat{W}_{k_m}$$ i.i.d? Somehow it is dependent on how we define $$m$$, but my intuition says that a new sample is dependent on the old ones, since the summation over $$u$$ and $$v$$ directly uses the old samples. So it's not i.i.d and I can not use Chernoff-Hoeffding? If that's true, how do I find a strong bound then?