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?

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.