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.
