the one with the highest mean. At each round, we observe a new sample from each distribution. As sampling can be expensive, the objective is to stop sampling and find the distribution with the highest mean as quick as possible. The common approach is to employ certain concentration inequalities (such as Hoeffding’s Inequality [@Hoeffding]) to construct confidence bands around the empirical mean of each distribution after a number of observations. When the approximations are accurate enough and the decision maker has enough confidence, he stops and chooses the distribution with the highest empirical mean [@Hoeffding_races].

To illustrate the ideas, assume we are given two distributions, $p_1$ and $p_2$, and are asked to find the one with the higher mean. Let the expected values of these distributions be $\mu_1$ and $\mu_2$, respectively. Assume that $\mu_1>\mu_2$. Let $x_s\in[0,1], 1\le s\le t$ be samples from $p_1$ and $y_s\in[0,1], 1\le s\le t$ be samples from $p_2$. Define the empirical means by $\overline{X}_t = \frac{1}{t}\sum_{s=1}^t x_s$ and $\overline{Y}_t = \frac{1}{t}\sum_{s=1}^t y_s$ and the empirical gap by $g_t = \overline{X}_t - \overline{Y}_t$. Without loss of generality, assume that $g_t > 0$. From Hoeffding’s Inequality, we get that

$${{\mathbb P}\left(\overline{X}_t - \mu_1 \le g_t/2\right)} \ge 1 - 