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:

- $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?
- 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?