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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .