Best-Arm Identification

A team runs a two-week test of five checkout designs and will ship one. Revenue during the test barely matters; shipping the wrong design for a year does. Running UCB here is a mistake of objective. UCB is built to minimise cumulative regret, so once one design looks good it pours traffic into it and starves the runners-up, which is exactly where the remaining uncertainty lives. The question "which arm is best?" needs a different algorithm.

Simple regret and the conflict with cumulative regret

In pure exploration the learner samples for \(n\) rounds, then recommends an arm \(J_n\). Its simple regret is \(r_n = \mu^* - \mu_{J_n}\), the gap between the best mean and the mean of the recommendation. Bubeck, Munos and Stoltz showed that the two objectives genuinely conflict: an algorithm that keeps cumulative regret small necessarily has simple regret that decays slowly, so no strategy is optimal for both (Bubeck et al., 2008, Pure Exploration for Multi-Armed Bandit Problems, arXiv:0802.2655). Earning while learning and learning to decide are different jobs. This is the pure-exploration counterpart to the regret-focused view in regret and the exploration-exploitation tradeoff.

Two formulations

Fixed confidence. Choose \(\delta\). The algorithm samples until it decides to stop at time \(\tau\), and must satisfy \(P(J_\tau \ne i^*) \le \delta\). Minimise \(\mathbb{E}[\tau]\). This fits a test that can run until it is sure.

Fixed budget. Given exactly \(n\) samples, minimise \(P(J_n \ne i^*)\). This fits a test with a hard deadline.

Both have difficulty governed by the gaps \(\Delta_i = \mu^* - \mu_i\). The central quantity is

and fixed-confidence sample complexity scales as \(H_1 \log(1/\delta)\) up to logarithmic factors. It is intuitive: distinguishing two means \(\Delta\) apart takes on the order of \(1/\Delta^2\) samples, and each suboptimal arm needs ruling out once. Kaufmann, Cappé and Garivier derived information-theoretic lower bounds for both settings and found, against the intuition from classical hypothesis testing, that fixed-budget complexity can be smaller than fixed-confidence complexity (Kaufmann et al., 2016, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, JMLR, arXiv:1407.4443).

A worked case. Five designs with conversion means \(0.50, 0.45, 0.40, 0.40, 0.30\) have gaps \(0.05, 0.10, 0.10, 0.20\), so \(H_1 = 400 + 100 + 100 + 25 = 625\). Uniform allocation must sample every arm enough to resolve the smallest gap, on the order of \(K/\Delta_{\min}^2 = 5 \times 400 = 2{,}000\) in the same units. The adaptive saving comes from dropping the 0.30 arm after a few dozen samples' worth and spending the rest on the close pair. With several close contenders the two numbers converge, and adaptivity buys little.

Algorithms

Successive elimination. Keep an active set. Each round, sample every active arm once, so after \(t\) rounds each has \(t\) samples. Using a Hoeffding radius with a union bound over arms and rounds, of the form \(c_t = \sqrt{\log(c K t^2/\delta)/(2t)}\) for a small constant \(c\), remove arm \(i\) when \(\hat{\mu}_{\max} - \hat{\mu}_i > 2c_t\). Stop when one arm remains. Easy arms leave early, so sampling concentrates where the gaps are small (Even-Dar et al., 2006, Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems, JMLR 7).

LUCB. Rather than sampling everything, sample the two arms that matter most: the empirical leader \(h_t\), and among the others the arm \(l_t\) with the highest upper confidence bound, the most plausible challenger. Stop when the leader's lower bound clears the challenger's upper bound, \(L_{h_t} > U_{l_t} - \epsilon\). The expected sample complexity is \(O(H \log(H/\delta))\) with \(H\) a gap-based complexity like \(H_1\) (Kalyanakrishnan et al., 2012, PAC Subset Selection in Stochastic Multi-armed Bandits, ICML).

Successive Rejects handles the fixed budget. Split \(n\) into \(K-1\) phases of increasing length, sample survivors equally within a phase, and drop the empirically worst arm at each phase end. It needs no knowledge of the gaps, and its error probability decays exponentially in \(n/(\log K \cdot H_2)\), where \(H_2 = \max_i i\,\Delta_{(i)}^{-2}\) over gaps in increasing order (Audibert, Bubeck & Munos, 2010, Best Arm Identification in Multi-Armed Bandits, COLT).

When it breaks

Near-ties cost unboundedly. As the top gap goes to zero, \(1/\Delta^2\) explodes and a fixed-confidence test never stops. The practical fix is \(\epsilon\)-good identification: accept any arm within \(\epsilon\) of the best, which caps the cost at roughly \(1/\epsilon^2\) per contender.

The winner's estimate is biased upward. Selecting the arm with the highest empirical mean selects for arms that got lucky, so the reported lift of the chosen design overstates what shipping will deliver. Identification guarantees which arm, not how much better.

Theory and practice disagree about constants. Asymptotically optimal methods such as Track-and-Stop match the lower bound as \(\delta \to 0\) (Garivier & Kaufmann, 2016, Optimal Best Arm Identification with Fixed Confidence, COLT, arXiv:1602.04589), but those guarantees are asymptotic, and at a practical \(\delta\) such as 0.05 the finite-sample behaviour is driven by how conservative the stopping threshold is. Experiments in this literature often use heuristic thresholds smaller than the ones the proofs license, which stops sooner and, strictly, voids the formal guarantee. Guarantees and good behaviour at realistic sample sizes are separate claims.

Stationarity is assumed. Weekday and weekend traffic convert differently. An elimination rule that drops an arm on Tuesday data has drawn a conclusion about a population that changes by Saturday.