Consider a 2-armed bandit problem with distributions of the two arms being $\nu_1 = Ber(1/2)$ and $\nu_2 = Ber(1/2 + \xi \Delta)$ where $Ber$ refers to the Bernoulli random variable and $\xi \in \{-1, 1\}$ is unknown. Let $\tau$ be the expected number of observations from arm $\nu_2$. Then the following result is true according to some time probability rule:

There is a probability of at least $\exp(-\tau \Delta^2)$ to make the wrong guess on the value of $\xi$.

I am just able to get how the above result is true. This problem is mentioned as some easy probability application at the blog.


1 Answer 1


I’m not familiar with the multi-armed bandit problem, and here’s my best shot. Please let me know if my understanding of the setting is wrong.

The goal is to guess which of the two $$~p_{+} \equiv \frac{1}2 + \Delta\quad \text{or} \quad p_{-} \equiv \frac{1}2 - \Delta$$ is the actual success probability of the Bernoulli random variable $\nu_2$

We have some history-dependent strategy switching between the two arms, so the $$T\equiv \text{number of observations of $\nu_2$}$$ is a random variable as well with $\tau \equiv E[T]$ and $\sigma_T > 0$.

Here we consider the lower bound of the error probability. The variance $\sigma_T$ due to the strategy can only add to that probability. Therefore, first we either consider long term observations in which $T$ is so large that $\sigma_T$ is relatively very small, or that we just postpone this additional layer of modeling to the next stage, if it is still desired.

That is, consider the number of observations of $\nu_2$ to be exactly $\tau$, for the case $\xi = -1$. Denote the estimate to this $p_{-}$ as $\theta \equiv \hat{p}_{-}$, which follows a scaled Binomial distribution that can be approximated by Gaussian $$\theta \sim N\left( \mu_{\theta} = p_{-},~ \sigma_{\theta} = \sqrt{ \frac{ p_{-} (1 - p_{-}) }{\tau} } \right)$$

The simple-minded selection (estimation) criteria suggested by the symmetric setting is that $$\begin{align} &\text{Guess} &&\hat{\xi} = 1 &&\text{if} &&\theta > \frac{1}2 \\ &\text{Guess} &&\hat{\xi} = -1 &&\text{if} &&\theta < \frac{1}2 \end{align}$$

There definitely can be other better estimate for $\xi$ more suitable for its binary nature, but anyway here’s how this one works out: the (symmetric) probability of a wrong guess is $$\text{Pr}\left( \xi = -1 \quad \text{yet} \quad \theta > \frac{1}2 \right) $$

So we want the right tail probability of Gaussian a distance $\frac{1}2 - p_{-} = \Delta$ away from the mean, namely, $$\Phi \left( x \right) = \frac{1}2 \text{erfc}( \frac{x}{\sqrt{2}} ) \qquad \text{at} \quad x = \frac{\Delta}{ \sigma_{\theta} }$$ where erfc$(x)$ is the complement of the error function.

There are numerous approximations of various orders to the error function that yield nice algebraic results, and here for the purpose of ad-hoc arriving at the desired outcome, the single term LOWER bound does the job (see the last inequality at the end of this section; also see Burmann series)$$ \text{erfc}( x ) \geq \sqrt{ \frac{2e}{\pi}} \frac{ \sqrt{\beta - 1} }{ \beta } e^{ -\beta x^2 }$$ where $\beta > 1$ can be tuned however one likes to tailor the error for your target interval.

Thus our desired quantity is bounded from below as $$\begin{gather} \text{Pr}\left( \text{wrong guess}\right) = \Phi \left( \frac{\Delta}{ \sigma_{\theta} } \right) \geq \sqrt{ \frac{2e}{\pi} } \frac{ \sqrt{\beta - 1} }{ \beta } e^{ -\beta \frac{\Delta^2}{ \sigma_{\theta}^2 } } \tag*{, with}\\ \sigma_{\theta}^2 = \frac{ p_{-} (1 - p_{-}) }{\tau} = \frac{ \frac{1}4 - \Delta^2 }{\tau} \\ \frac{\Delta^2}{ \sigma_{\theta}^2 } = \tau \Delta^2 \left( \frac{1}4 - \Delta^2 \right)^{-1} \approx 4\tau \Delta^2 \tag*{for $\Delta^2 \ll 1$} \\ \implies \Phi \left( \frac{\Delta}{ \sigma_{\theta} } \right) \geq \sqrt{ \frac{2e}{\pi} } \frac{ \sqrt{\beta - 1} }{ \beta } e^{ -4\beta \tau \Delta^2 } \end{gather} $$

In his blog, Sébastien Bubeck just mentioned in passing this as a "probability 102" result. I'm looking forward to see a different derivation that is more general (not just for small $\Delta$) and that gives tighter bounds. Whatever that might be, to me it’s not unreasonable that he omitted the proportionally factors in or outside the exponential, since it is the dependence $\tau \Delta^2$ in exponential decay that’s important.


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.