be formulated as a stopping problem [@Shiryaev]. The stopping problem is a decision making problem where at each round, the decision maker observes an input and a (possibly noisy) reward and decides whether he wants to see the next input or not. The objective is to maximize the expected reward when he decides to [*stop*]{}. The stopping problem is studied in various settings in statistics, decision theory, and economics.

More specifically, we can formulate our problem as finding the best option from a pool on options based on some measurements. Assume a number of distributions are given, from which we want to find the one with the highest mean. At each round, we observe a new sample from these distributions. As sampling can be expensive, the objective is to stop sampling and choose 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 approximate the 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].

In our problem, given a 