e^{-g_t^2 t/2}\,,$$ and $${{\mathbb P}\left(\overline{Y}_t - \mu_2 \ge -g_t/2\right)} \ge 1 - e^{-g_t^2 t/2}\;.$$ Thus, with probability at least $1-2e^{-g_t^2 t/2}$, $\overline{X}_t - \mu_1 \le g_t/2$ and $\overline{Y}_t - \mu_2 \ge -g_t/2$, which implies that $$\mu_1 > \mu_2\;.$$ Thus, we have correctly identified the distribution with the highest mean (here $p_1$) with probability at least $1-2e^{-g_t^2 t/2}$. If we demand that this probability be at least $1-\delta$ for some $\delta\in (0,1)$, then we need to have $$\label{eq:num_samples}
g_t\ge \sqrt{\frac{2\log(2/\delta)}{t}}\;.$$ Equation  can be used as a stopping condition to make the right decisions with high probability. We might ask how many samples are needed before Condition  is satisfied? By applying Hoeffding’s Inequality, it is not difficult to see that if the true gap ($g=\mu_1-\mu_2$) is small, then the number of samples $t$ in Condition  needs to be larger. This implies that the identification is more difficult when there is a small gap between the two distributions.

0 $$\label{eq:num_samples}
t\ge \frac{2\log(2/\delta)}{g^2},$$ with probability at least $1-\delta/2$, it holds that $$\label{eq:error1}
\overline{X}_t - \mu_1 \ge -g/2\;.$$ Similarly, it can be shown that if holds, then with probability at least $1-\delta/2$, it holds that $$\label{eq:error2}
\overline{Y}_t - \mu_2 \le g/2\;.$$ Then, by and , 