4
$\begingroup$

In a paper on Multi Armed Bandits, I came across the following statement:

This generalizes the well-known fact that one needs of order $\frac{1}{\Delta^2}$ samples to differentiate the means of two distributions with gap $\Delta$.

(cf. Audibert et al. (2010) )

To me, this is not "well known". That is why I would appreciate a hint where this "fact" comes from. In Multi Armed Bandits, a common assumption is that the random variables are bounded between 0 and 1. However, the exact distribution is not known.

$\endgroup$
0
4
$\begingroup$

This "well-known" fact comes from the fact that the lower bound on the sample complexity (i.e. the number of samples needed to differentiate the means of two arms) is proportional to $1/\Delta^2$.

You can actually say more: any algorithm, in order to identify with probability at least $1-\delta$ the best arm (i.e. the one having the largest mean) between two distribution, needs a number of samples $\tau$ that satisfy

$$ \mathbb{E}[\tau] \gtrsim 1/\Delta^2\log(1/\delta), $$

and this comes from a very famous paper in the bandit literature that you can find here. See at the end of page 6 for the inverse gap argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.