Pure Exploration and Best-Arm Identification

Corresponds to Lattimore & Szepesvári, Chapter 33.

Motivation: exploration is free; only the answer counts

IntuitionThe mouse never benefits from the experiment

A researcher tests $k$ drug configurations on $n$ mice to choose one for human trials. The mice’s outcomes don’t matter, only the final recommendation does. There is no exploration–exploitation trade-off: every sample can go wherever it is most informative. These are pure exploration problems. The tools are those of cumulative regret (concentration, change of measure), but the optimal behaviour is quite different.

Formulation	Learner controls	Objective	Key result
Simple regret	allocation for $n$ rounds + recommendation $A_{n+1}$	$\mathbb E[\Delta_{A_{n+1}}]$	minimax $\Theta(\sqrt{k/n})$
Fixed confidence	allocation + stopping time $\tau$ + recommendation $\psi$	minimise $\mathbb E[\tau]$ subject to $\mathbb P(\text{wrong})\le\delta$	$\mathbb E[\tau]\sim c^*(\nu)\log\frac1\delta$ (track-and-stop)
Fixed budget	allocation for $n$ rounds + recommendation	minimise $\mathbb P(\Delta_{A_{n+1}} > 0)$	$\exp(-\Theta(n/(H_2\log k)))$ (sequential halving)

Simple regret

DefinitionSimple regret

For a policy $\pi = (\pi_t)_{t=1}^{n+1}$ , where round $n+1$ is the recommendation,

$R_n^{\mathrm{simple}}(\pi,\nu) = \mathbb E_{\nu\pi}\big[\Delta_{A_{n+1}}(\nu)\big]$

Optimisation literature calls this the expected suboptimality.

Component	Detail
Signature	$R_n^{\mathrm{simple}} : \Pi\times\mathcal E\to[0,\infty)$
Counts	only the gap of the final recommendation
Ignores	all rewards during the $n$ exploration rounds

AlgorithmUniform exploration (UE, Algorithm 20)

For $t\le n$ play $A_t = 1 + (t\bmod k)$ (round robin). Recommend $A_{n+1} = \arg\max_i\hat\mu_i(n)$ .

TheoremTheorem 33.1 — Simple regret of uniform exploration

For $\nu\in\mathcal E^k_{SG}(1)$ and $n\ge k$ ,

$R_n^{\mathrm{simple}}(\mathrm{UE},\nu)\le\min_{\Delta\ge0}\Big(\Delta + \sum_{i:\Delta_i>\Delta}\Delta_i\exp\Big(-\frac{\lfloor n/k\rfloor\Delta_i^2}4\Big)\Big)$

ProofEach arm has a deterministic sample count, so the subgaussian tail applies directly

With arm 1 optimal, $A_{n+1} = i$ requires $\hat\mu_i(n)\ge\hat\mu_1(n)$ . Both means use at least $\lfloor n/k\rfloor$ samples, a non-random count, so their difference is $\sqrt{2/\lfloor n/k\rfloor}$ -subgaussian and $\mathbb P(\hat\mu_i\ge\hat\mu_1)\le e^{-\lfloor n/k\rfloor\Delta_i^2/4}$ (33.1). Then $R^{\mathrm{simple}} = \sum_i\Delta_i\mathbb P(A_{n+1} = i)\le\Delta + \sum_{\Delta_i>\Delta}\Delta_i\mathbb P(A_{n+1} = i)$ .

∎

ImportantSimple regret versus cumulative regret

Fixed $\nu$ , $n\to\infty$ : simple regret decays exponentially fast, whereas cumulative regret grows like $\log n$ .
Fixed $n$ , worst case over $\nu$ : with $\Delta = 2\sqrt{\log k/\lfloor n/k\rfloor}$ , each remaining term is at most $\Delta/k$ (since $xe^{-cx^2}$ decreases beyond $1/\sqrt{2c}$ ), so $R_n^{\mathrm{simple}}(\mathrm{UE},\nu)\le C\sqrt{\frac{k\log k}n}\quad\forall\nu\in\mathcal E^k_{SG}(1) \tag{33.2}$ (Constant worked here.)
Lower bound (Exercise 33.1): every policy has some Gaussian $\nu$ with $R_n^{\mathrm{simple}}\ge C\sqrt{k/n}$ , by the Chapter 15 technique. The $\sqrt{\log k}$ is tight for UE (Exercise 33.2), so UE is not minimax-optimal.

From cumulative to simple regret

TheoremProposition 33.2 — Recommend by play frequency

Given any policy $(\pi_t)_{t\le n}$ , recommend arm $i$ with probability equal to its empirical play frequency: $\pi_{n+1}(i\mid\cdot) = \frac1n\sum_{t\le n}\mathbb I\{a_t = i\}$ . Then

$R_n^{\mathrm{simple}} = \frac{R_n(\pi,\nu)}n$

ProofRegret decomposition

$R_n = n\,\mathbb E\big[\sum_i\Delta_i\frac{T_i(n)}n\big] = n\,\mathbb E[\Delta_{A_{n+1}}]$ , by the regret decomposition and the definition of $\pi_{n+1}$ .

∎

CorollaryCorollary 33.3 — Minimax simple regret

Combining with MOSS ( $R_n\le C\sqrt{kn}$ ): $\inf_\pi\sup_{\nu}R_n^{\mathrm{simple}}\le C\sqrt{k/n}$ , which matches the lower bound.

WarningLow cumulative regret is wasteful on easy instances

Cumulative-regret algorithms play suboptimal arms just barely enough to rule them out. Their worst-case simple regret is fine, but on easy instances the probability of misidentifying the best arm decays only polynomially:

If $\lim_n\mathbb E[T_i(n)]/\log n = 2/\Delta_i$ (asymptotically optimal), then for every $\varepsilon > 0$ some $\nu$ has $\liminf_n\frac{-\log\mathbb P(A_{n+1}\notin i^*)}{\log n}\le1 + \varepsilon$ , no matter how $A_{n+1}$ is chosen (Exercise 33.5; Bubeck et al. 2009).
Their empirical means are also negatively biased: arms are played until their estimates look bad enough.

Fixed-confidence best-arm identification

DefinitionPolicy, stopping rule, selection rule

The learner chooses a policy $\pi$ , a stopping time $\tau$ for $\mathcal F_t = \sigma(A_1,X_1,\ldots,A_t,X_t)$ (possibly $\tau = \infty$ , Definition 3.6), and an $\mathcal F_\tau$ -measurable selection rule $\psi\in[k]$ , the recommendation.

DefinitionSoundness (Def. 33.4)

$(\pi,\tau,\psi)$ is sound at level $\delta$ for $\mathcal E$ if for all $\nu\in\mathcal E$

$\mathbb P_{\nu\pi}\big(\tau < \infty\ \text{and}\ \Delta_\psi(\nu) > 0\big)\le\delta \tag{33.3}$

Goal: among sound triples, minimise $\mathbb E_{\nu\pi}[\tau]$ for every $\nu$ . Soundness plays the role of consistency in the asymptotic lower bounds, giving instance-dependent asymptotic optimality as $\delta\to0$ . Exogenous randomness in $\tau$ or $\psi$ changes nothing.

WarningTies make stopping impossible (Exercise 33.10)

For Gaussian or Bernoulli classes, if $\nu$ has multiple optimal arms, every sound learner has $\mathbb P_{\nu\pi}(\tau = \infty) = 1$ . It can never rule out that one optimal arm is fractionally better than another. For classes with extra structure (for example, a known minimum gap between distinct means), stopping is possible.

Lower bound

DefinitionAlternatives and characteristic time

$i^*(\nu) = \arg\max_i\mu_i(\nu)$ , and $\mathcal E_{\mathrm{alt}}(\nu) = \{\nu'\in\mathcal E : i^*(\nu')\cap i^*(\nu) = \emptyset\}$ are the instances in which no optimal arm of $\nu$ is optimal.

$c^*(\nu)^{-1} = \sup_{\alpha\in\mathcal P_{k-1}}\inf_{\nu'\in\mathcal E_{\mathrm{alt}}(\nu)}\sum_{i=1}^k\alpha_iD(\nu_i,\nu_i') \tag{33.4}$

with $c^*(\nu) = \infty$ when the sup is 0.

Component	Detail
$\alpha$	the long-run fraction of samples given to each arm
Inner inf	the hardest alternative to rule out under allocation $\alpha$
*$c^(\nu)^{-1}$**	best achievable rate of evidence per sample against the closest wrong world
*$c^(\nu)$**	samples needed per unit of $\log(1/\delta)$

TheoremTheorem 33.5 — Fixed-confidence lower bound

If $(\pi,\tau,\psi)$ is sound at level $\delta$ for $\mathcal E$ , then for every $\nu\in\mathcal E$

$\mathbb E_{\nu\pi}[\tau]\ge c^*(\nu)\log\frac1{4\delta}$

This needs no unstructuredness, and extends to infinitely many arms under measurability.

ProofChange of measure at the stopping time

Step 1: assume $\mathbb E[\tau] < \infty$ , so $\tau < \infty$ a.s. Fix $\nu'\in\mathcal E_{\mathrm{alt}}(\nu)$ and $E = \{\tau < \infty,\ \psi\notin i^*(\nu')\}\in\mathcal F_\tau$ . Soundness under both instances, and $i^*(\nu)\cap i^*(\nu') = \emptyset$ , give $E^c\subseteq\{\tau = \infty\}\cup\{\tau < \infty,\ \psi\notin i^*(\nu)\}$ , so

$2\delta\ge\mathbb P_\nu(E^c) + \mathbb P_{\nu'}(E)\ge\frac12\exp\Big(-\sum_i\mathbb E_\nu[T_i(\tau)]D(\nu_i,\nu_i')\Big) \tag{33.5}$

by Bretagnolle–Huber and the stopped divergence decomposition (Exercise 15.7).

Step 2: rearranging, $\sum_i\mathbb E_\nu[T_i(\tau)]D(\nu_i,\nu_i')\ge\log\frac1{4\delta}$ for every alternative (33.6).

Step 3: Normalise. The proportions $\alpha_i = \mathbb E[T_i(\tau)]/\mathbb E[\tau]$ form a distribution, so

$\frac{\mathbb E[\tau]}{c^*(\nu)}\ge\mathbb E[\tau]\inf_{\nu'}\sum_i\frac{\mathbb E[T_i(\tau)]}{\mathbb E[\tau]}D(\nu_i,\nu_i') = \inf_{\nu'}\sum_i\mathbb E[T_i(\tau)]D(\nu_i,\nu_i')\ge\log\frac1{4\delta} \tag{33.7}$

∎

ImportantWhat the bound says about optimal algorithms

Optimal allocation: if $\alpha^*(\nu)$ attains the sup, then (33.7) is tight only when $\mathbb E[T_i(\tau)]/\mathbb E[\tau]\to\alpha_i^*(\nu)$ . An optimal learner must sample in the proportions $\alpha^*(\nu)$ , which are unknown and must be learned.
Uniqueness: $\alpha^*(\nu)$ is unique for unit-variance Gaussian bandits with a unique optimum, and for unstructured exponential families.
Equivalent primal form (Note 6, Exercise 33.3): $\mathbb E[\tau]\ge\min\{\lVert\alpha\rVert_1 : \alpha\ge0,\ \inf_{\nu'}\sum_i\alpha_iD(\nu_i,\nu_i')\ge\log(4/\delta)\}$ . This is the cheapest sample budget that refutes every alternative, which is the same allocation problem as the linear-bandit asymptotic constant, with regret weights replaced by sample counts.

ExampleTwo Gaussian arms

With $\mathcal E = \mathcal E^2_N(1)$ and $\Delta = \mu_1 - \mu_2 > 0$ , the cheapest alternative makes the two means equal at their $\alpha$ -weighted average, costing $\alpha(1-\alpha)\Delta^2$ :

$c^*(\nu)^{-1} = \frac12\sup_{\alpha\in[0,1]}\alpha(1-\alpha)\Delta^2 = \frac{\Delta^2}8,\qquad\alpha^* = (\tfrac12,\tfrac12)$

So $\mathbb E[\tau]\ge\frac8{\Delta^2}\log\frac1{4\delta}$ : split samples evenly, since both means must be pinned down equally.

TheoremGaussian bandits with known variances (Exercise 33.4)

For $\mathcal E = \{(\mathcal N(\mu_i,\sigma_i^2))_i\}$ with arm 1 uniquely optimal:

$\inf_{\tilde\nu\in\mathcal E_{\mathrm{alt}}(\nu)}\sum_i\alpha_iD(\nu_i,\tilde\nu_i) = \frac12\min_{i>1}\frac{\alpha_1\alpha_i\Delta_i^2}{\alpha_1\sigma_i^2 + \alpha_i\sigma_1^2}$

Two arms: $c^*(\nu) = \dfrac{2(\sigma_1 + \sigma_2)^2}{\Delta_2^2}$ (33.8), attained by sampling in proportion to the standard deviations. It grows with either variance.
$k$ arms: $\frac{2\sigma_1^2}{\Delta_{\min}^2} + \sum_{i>1}\frac{2\sigma_i^2}{\Delta_i^2}\le c^*(\nu)\le\frac{2\sigma_1^2}{\Delta_{\min}^2} + \sum_{i>1}\frac{2\sigma_i^2}{\Delta_i^2} + 2\sqrt{\frac{2\sigma_1^2}{\Delta_{\min}^2}\sum_{i>1}\frac{2\sigma_i^2}{\Delta_i^2}} \tag{33.10}$ with equality on the right when all $\sigma_i^2/\Delta_i^2$ equal $\sigma_1^2/\Delta_{\min}^2$ .

Reading: each suboptimal arm needs about $\sigma_i^2/\Delta_i^2$ samples to be told apart from the best arm, and the best arm needs about $\sigma_1^2/\Delta_{\min}^2$ to be told apart from the runner-up. For $k = 2$ the upper bound equals (33.8) exactly, so it is the lower bound that is loose there, by up to a factor of 2.

Track-and-stop

Setting. $\mathcal E = \mathcal E^k_N(1)$ , unit-variance Gaussian arms.

DefinitionGLR stopping statistic

With $\hat\nu(t)$ the Gaussian bandit with means $\hat\mu(t)$ ,

$Z_t = \inf_{\nu'\in\mathcal E_{\mathrm{alt}}(\hat\nu(t))}\sum_iT_i(t)D(\hat\nu_i(t),\nu_i') = \frac12\inf_{\mu'\in\mathcal E_{\mathrm{alt}}(\hat\mu(t))}\sum_iT_i(t)(\hat\mu_i(t) - \mu_i')^2$

the empirical evidence against the closest world in which the current leader $\hat\imath$ is not best. In closed form, by the two-arm projection above,

$Z_t = \min_{j\ne\hat\imath}\frac{T_{\hat\imath}(t)T_j(t)}{T_{\hat\imath}(t) + T_j(t)}\cdot\frac{(\hat\mu_{\hat\imath}(t) - \hat\mu_j(t))^2}2$

(Closed form worked here.) This is a generalised likelihood-ratio test in the tradition of Chernoff (1959) (sequential testing).

IntuitionWhere the stopping rule comes from

(33.6) says a sound learner must accumulate $\inf_{\nu'}\sum\mathbb E[T_i]D(\nu_i,\nu_i')\gtrsim\log\frac1\delta$ . Replace the unknown $\nu$ by $\hat\nu(t)$ and expectations by realised counts, and stop once $Z_t$ exceeds a threshold of about $\log(t/\delta)$ .

AlgorithmTrack-and-stop (Algorithm 21; Garivier–Kaufmann 2016)

Play each arm once; $t = k$ . While $Z_t < \beta_t(\delta)$ :

Forced exploration: if $\min_iT_i(t)\le\sqrt t$ , play the least-sampled arm.
Tracking: otherwise play $\arg\max_i\big(t\hat\alpha_i^*(t) - T_i(t)\big)$ , where $\hat\alpha^*(t) = \alpha^*(\hat\nu(t))$ is the plug-in optimal allocation.

Return $\psi = i^*(\hat\nu(\tau))$ and $\tau = t$ .

Ingredient	Purpose
GLR stopping $Z_t\ge\beta_t(\delta)$	soundness, and stops as soon as the evidence suffices
Tracking $\hat\alpha^*(t)$	matches the optimal proportions, so $\mathbb E[\tau]$ attains the lower bound
Forced $\sqrt t$ exploration	guarantees $\hat\nu(t)\to\nu$ , so $\hat\alpha^\to\alpha^$

TheoremTheorem 33.6 — Track-and-stop is asymptotically optimal

For a suitable $\beta_t(\delta)$ , track-and-stop is sound, and for every $\nu\in\mathcal E$ with a unique optimal arm

$\lim_{\delta\to0}\frac{\mathbb E_{\nu\pi}[\tau]}{\log(1/\delta)} = c^*(\nu)$

(only $\tau$ depends on $\delta$ ; the policy does not).

LemmaLemma 33.7 — A sound threshold

With $f(x) = e^{k-x}(x/k)^k$ on $[k,\infty)$ (strictly decreasing from $f(k) = 1$ to 0, with $f^{-1}(\delta) = (1 + o(1))\log\frac1\delta$ , expressible via the Lambert W function) and

$\beta_t(\delta) = k\log(t^2 + t) + f^{-1}(\delta)$

the rule $\tau = \min\{t : Z_t\ge\beta_t(\delta)\}$ satisfies $\mathbb P(i^*(\hat\nu(\tau))\ne i^*(\nu))\le\delta$ .

ProofA wrong answer means the truth looks like an alternative

If the leader is tied, $Z_t = 0$ , so at stopping the leader is unique. A wrong answer means $\nu\in\mathcal E_{\mathrm{alt}}(\hat\nu(\tau))$ , so by the definition of $Z_\tau$ , $\frac12\sum_iT_i(\tau)(\hat\mu_i(\tau) - \mu_i)^2\ge\beta_\tau(\delta)$ . Bound this with:

Lemma 33.8 (per-arm anytime bound). For i.i.d. unit Gaussians, $\mathbb P\big(\exists n : \frac n2(\hat\mu_n - \mu)^2\ge\log\frac1\delta + \log(n(n+1))\big)\le\delta$ , by Corollary 5.5 and a union bound over $n$ with weights $\frac1{n(n+1)}$ .

Proposition 33.9 (combining arms). If each of $k$ independent sequences satisfies $\mathbb P(\exists s : S_{is}\ge g(s) + \log\frac1\delta)\le\delta$ with $g$ increasing, then $\mathbb P\big(\exists s\in\mathbb N^k : \sum_iS_{is_i}\ge kg(\sum_is_i) + x\big)\le f(x)$ . Define $W_i$ as the smallest per-arm confidence level that still covers arm $i$ for all $s$ . Then the $W_i$ are independent, stochastically larger than uniform, and $\sum_iS_{is_i}\le kg(\sum s_i) + \sum_i\log\frac1{W_i}$ . Then apply the tail bound for $\sum\log(1/W_i)$ (Exercise 5.16).

With $g(s) = \log(s(s+1))$ , $\sum_is_i = t$ and $x = f^{-1}(\delta)$ , this gives the threshold.

∎

RemarkBetter thresholds

The threshold is about $2k\log t + \log(1/\delta)$ . Replacing Lemma 33.8 with a law-of-the-iterated-logarithm bound (peeling, the method of mixtures as in Exercise 20.9, or Bachelier–Lévy for Gaussians) improves it to about $k\log\log t + \log(1/\delta)$ . This matters a lot in practice.

ProofProof sketch of Theorem 33.6 (Exercise 33.6)

Forced exploration gives $\hat\nu(t)\to\nu$ . Continuity of $\alpha^*$ at $\nu$ (it is unique) gives $\hat\alpha^*(t)\to\alpha^*(\nu)$ , and tracking gives $T(t)/t\to\alpha^*(\nu)$ . Each of these has a “last bad time” with finite expectation. After those times,

$Z_t\approx t\inf_{\tilde\nu\in\mathcal E_{\mathrm{alt}}(\nu)}\sum_i\alpha_i^*(\nu)\frac{(\mu_i(\nu) - \mu_i(\tilde\nu))^2}2 = \frac t{c^*(\nu)}$

so stopping happens once $t/c^*(\nu)\ge\beta_t(\delta) = (1 + o(1))\log\frac1\delta$ , i.e. at $t\approx c^*(\nu)\log\frac1\delta$ .

∎

WarningAsymptotic only

The proof works for forced exploration at any rate $Ct^p$ with $p\in(0,1)$ . Nothing singles out $\sqrt t$ , and no principled tuning is known.
Finite-time upper bounds matching Theorem 33.5 are open.
Improvements: optimism plus online-learning solutions of the allocation problem (Degenne–Koolen 2019; Degenne et al. 2019); Bayesian top-two Thompson sampling with optimal posterior convergence (Russo 2016), optimal in both senses (Qin et al. 2017).

Fixed-budget best-arm identification

Setting. The horizon $n$ is given, and the goal is to minimise $\mathbb P(\Delta_{A_{n+1}} > 0)$ . The theory is less clean than for fixed confidence: there are no asymptotically matching upper and lower bounds.

WarningUniform exploration is non-adaptive

$\mathbb P_{\mathrm{UE}}(\Delta_{A_{n+1}} > 0)\le\sum_{i:\Delta_i>0}e^{-\lfloor n/k\rfloor\Delta_i^2/4}$ . It wastes samples on obviously bad arms when the gaps differ widely.

AlgorithmSequential halving (Algorithm 22; Karnin et al. 2013)

$L = \lceil\log_2k\rceil$ phases, $\mathcal A_1 = [k]$ . In phase $\ell$ :

play each arm in $\mathcal A_\ell$ exactly $T_\ell = \big\lfloor\frac n{L\lvert\mathcal A_\ell\rvert}\big\rfloor$ times;
compute $\hat\mu_i^\ell$ from this phase’s samples only;
keep the top $\lceil\lvert\mathcal A_\ell\rvert/2\rceil$ arms.

Return the single survivor. Each phase uses about $n/L$ samples, so surviving arms get exponentially more samples per phase.

TheoremTheorem 33.10 — Sequential halving

For $\nu\in\mathcal E^k_{SG}(1)$ with $\mu_1\ge\cdots\ge\mu_k$ ,

$\mathbb P(\Delta_{A_{n+1}} > 0)\le3\log_2(k)\exp\Big(-\frac n{16H_2(\mu)\log_2k}\Big),\qquad H_2(\mu) = \max_{i:\Delta_i>0}\frac i{\Delta_i^2}$

The algorithm is symmetric in the arms; the ordering only serves to define $H_2$ .

ProofSketch (Exercise 33.8; take

k

a power of 2)

Step 1: in phase $\ell$ , if the best arm survived so far, $\mathbb P(\hat\mu_1^\ell\le\hat\mu_i^\ell)\le e^{-T_\ell\Delta_i^2/4}$ .

Step 2: Elimination needs many upsets. Halving removes the best arm only if at least half the arms beat it. Then at least $\frac13$ of the bottom three-quarters $\mathcal A_\ell'$ must beat it: $N_\ell\ge\frac13\lvert\mathcal A_\ell'\rvert$ .

Step 3: Markov on the upset count. Every arm in $\mathcal A_\ell'$ has index at least $i_\ell = \min\mathcal A_\ell'$ , so its gap is at least $\Delta_{i_\ell}$ , and $i_\ell\gtrsim\lvert\mathcal A_\ell\rvert/4$ . Hence $\mathbb E[N_\ell]\le\lvert\mathcal A_\ell'\rvert\exp\big(-\frac{n\Delta_{i_\ell}^2}{16i_\ell\log_2k}\big)$ , and Markov gives $\mathbb P(1\text{ eliminated in phase }\ell)\le3\exp\big(-\frac{n\Delta_{i_\ell}^2}{16i_\ell\log_2k}\big)\le3e^{-n/(16H_2\log_2k)}$ .

Step 4: union bound over the $\log_2k$ phases.

∎

DefinitionComplexity measures

$H_1(\mu) = \sum_{i=1}^k\min\Big\{\frac1{\Delta_i^2},\frac1{\Delta_{\min}^2}\Big\},\qquad H_2(\mu)\le H_1(\mu)\le(1 + \log k)H_2(\mu) \tag{33.9}$

$H_1$ is the natural “total samples needed” (each arm about $1/\Delta_i^2$ , the best arm $1/\Delta_{\min}^2$ , as in fixed confidence). $H_2$ is the “hardest-tail” version that sequential halving’s phase structure produces.

ProofBoth inequalities (Exercise 33.7)

$H_1\le LH_2$ with $L = 1 + \sum_{i=3}^k\frac1i\le1 + \log k$ : arms 1 and 2 contribute $2/\Delta_2^2\le H_2$ , and for $i\ge3$ , $1/\Delta_i^2\le H_2/i$ by the definition of $H_2$ .

$H_2\le H_1$ : for the maximising $i$ , gaps are sorted, so $i/\Delta_i^2\le\sum_{j\le i}\min\{1/\Delta_j^2,1/\Delta_{\min}^2\}\le H_1$ .

Both are tight: equal gaps make $H_1 = H_2$ up to constants, and $\Delta_i^2\propto i$ makes $H_1\approx LH_2$ .

∎

ExampleSequential halving versus uniform exploration

Gap profile	$H_2$	SH exponent	UE exponent	Winner
all gaps $= \Delta$	$k/\Delta^2$	$\Theta(n\Delta^2/(k\log k))$	$\Theta(n\Delta^2/k)$	UE, by $\log k$
$\Delta_2 = \Delta$ small, others 1	$\Theta(1/\Delta^2)$	$\Theta(n\Delta^2/\log k)$	$\Theta(n\Delta^2/k)$	SH, by about $k/\log k$

Adaptivity pays when gaps are heterogeneous. UE wastes samples on arms that are clearly bad. Sequential halving is known to be roughly optimal (lower bounds: Carpentier–Locatelli 2016).

Notes

RemarkConceptual points

An exploration dilemma remains. No reward trade-off exists, but the optimal allocation depends on the unknown $\nu$ , so samples must be split between learning how to explore and actually exploring.
Is best-arm identification the right goal? In practice any arm with a small enough gap is fine, which simple regret captures better. $R^{\mathrm{simple}}\le\max_i\Delta_i\cdot\mathbb P(\Delta_{A_{n+1}} > 0)$ is sometimes tight, sometimes loose.
Open: instance-dependent upper and lower bounds on simple regret, and the full distribution of $\Delta_{A_{n+1}}$ , are not understood. This is arguably the most practical setting.
Optimal experimental design: if the goal is reliable information about all differences between treatments, that is the design problem, not best-arm identification.

TheoremPAC identification (Exercise 33.11)

An $(\varepsilon,\delta)$ -PAC learner stops with $\mathbb P(\Delta_{A_\tau}\ge\varepsilon)\le\delta$ .

Naive: sample each arm about $\frac1{\varepsilon^2}\log\frac k\delta$ times, so $\mathbb E[\tau]\le\frac{Ck}{\varepsilon^2}\log\frac k\delta$ .
Median elimination (Even-Dar et al. 2002): halve the arm set each phase with geometrically tightening $(\varepsilon_\ell,\delta_\ell)$ , giving $\mathbb E[\tau]\le\frac{Ck}{\varepsilon^2}\log\frac1\delta$ , with no $\log k$ .
This is tight up to constants in the worst case. PAC is where the ML pure exploration literature began (Even-Dar, Mannor, Tsitsiklis, 2002–2006), restarted by Bubeck et al. (2009) and Audibert–Bubeck (2010).

TheoremOrdinal optimisation needs no dependence on $k$ (Exercise 33.9)

To find an arm in the top $\alpha$ -fraction (by quantile $\mu^*_\alpha$ ), just sample candidates at random: with $n\ge\log(1/\delta)/\log(1/(1-\alpha))$ independent draws $X_i\sim P$ , $\max_i\mu(X_i)\ge\mu_\alpha^*$ with probability $1-\delta$ , independent of the number of arms. Ordinal targets (“find a good one”) are exponentially easier than cardinal ones (“estimate the best value”, error about $n^{-1/2}$ ; Ho et al. 1992). The price is uncontrolled simple regret.

RemarkRelated literatures

Ranking and selection (statistics, 1950s on): Chan–Lai (2006) give a sound, asymptotically optimal track-and-stop-like procedure for exponential families. OCBA (optimal computing budget allocation; Chen et al. 2000) is a Bayesian heuristic for the Gaussian optimal allocation, a precursor to $\alpha^*$ (Glynn–Juneja 2015 bridge the literatures).
Beyond finite arms: linear BAI (Soare et al. 2014, the origin of the clouds-for-optimism example), continuous arms (Valko et al. 2013), tree search (Garivier et al. 2016), combinatorial (Chen et al. 2014).
Zeroth-order (derivative-free) stochastic optimisation: continuous $\mathcal A\subseteq\mathbb R^d$ with only noisy function values. For strongly convex and smooth objectives, the minimax simple regret is $\Theta(\sqrt{d^2/n})$ (Shamir 2013). Noise-injection gradient estimates are limited to $\Omega(n^{-1/3})$ (Hu et al. 2016) versus the optimal $O(n^{-1/2})$ , yet they win empirically. With unbiased gradient estimates, mirror descent is optimal.
Adversarial BAI (Jamieson–Talwalkar 2016: successive halving for hyperparameter search; Hyperband) and max-armed bandits (maximise the single largest reward).

Quick reference

Object	Statement	Note
Simple regret	$\mathbb E[\Delta_{A_{n+1}}]$	only the recommendation counts
Uniform exploration	$\min_\Delta(\Delta + \sum_{\Delta_i>\Delta}\Delta_ie^{-\lfloor n/k\rfloor\Delta_i^2/4})$	exponential in $n$ ; worst case $\sqrt{k\log k/n}$
Lower bound	$\Omega(\sqrt{k/n})$	Chapter 15 technique
Frequency recommendation	$R^{\mathrm{simple}} = R_n/n$	MOSS gives $O(\sqrt{k/n})$
Caveat	cumulative-regret algorithms misidentify with polynomial probability	wasteful on easy instances
Soundness	$\mathbb P(\tau < \infty,\ \Delta_\psi > 0)\le\delta$	like consistency
Characteristic time	$c^*(\nu)^{-1} = \sup_\alpha\inf_{\mathrm{alt}}\sum\alpha_iD(\nu_i,\nu_i')$
Lower bound	$\mathbb E[\tau]\ge c^*(\nu)\log\frac1{4\delta}$	stopped change of measure
Two Gaussians	$c^* = 8/\Delta^2$ ; $2(\sigma_1 + \sigma_2)^2/\Delta^2$ with known variances
GLR statistic	$Z_t = \min_{j\ne\hat\imath}\frac{T_{\hat\imath}T_j}{T_{\hat\imath} + T_j}\frac{(\hat\mu_{\hat\imath} - \hat\mu_j)^2}2$	Gaussian
Threshold	$k\log(t^2 + t) + f^{-1}(\delta)$ , $f^{-1}(\delta)\sim\log\frac1\delta$	LIL versions are better
Track-and-stop	$\mathbb E[\tau]/\log(1/\delta)\to c^*(\nu)$	track $\hat\alpha^*$ , force $\sqrt t$
Sequential halving	$3\log_2k\cdot e^{-n/(16H_2\log_2k)}$	$H_2 = \max_ii/\Delta_i^2$
Complexities	$H_2\le H_1\le(1 + \log k)H_2$	both tight
PAC	$\frac{Ck}{\varepsilon^2}\log\frac1\delta$	median elimination
Ordinal	$\log(1/\delta)/\log(1/(1-\alpha))$ samples	independent of $k$

Facts to keep to hand

Pure exploration rewards answers, not rewards. Simple regret decays exponentially for fixed instances, and the worst case is $\sqrt{k/n}$ . Converting a cumulative-regret algorithm via play frequencies is minimax-optimal but wasteful on easy instances: its error decays only polynomially.
Fixed confidence is a sequential hypothesis test against the closest wrong world. The characteristic time $c^*(\nu)$ comes from an allocation game: choose sampling proportions to maximise the evidence rate against the hardest alternative. Any sound learner needs about $c^*(\nu)\log(1/\delta)$ samples.
Track-and-stop attains it by plugging in estimates, tracking the optimal proportions with a little forced exploration, and stopping on a GLR statistic with an anytime threshold. It is asymptotic, with open finite-time questions.
Fixed budget favours adaptive elimination. Sequential halving’s $\exp(-n/(H_2\log k))$ beats uniform exploration when gaps are heterogeneous and loses only $\log k$ when they are equal.

References

Lattimore & Szepesvári, Bandit Algorithms — Chapter 33
Garivier & Kaufmann, “Optimal best arm identification with fixed confidence” (2016)
Karnin, Koren & Somekh, “Almost optimal exploration in multi-armed bandits” (2013)
Even-Dar, Mannor & Mansour, “PAC bounds for multi-armed bandit and Markov decision processes” (2002)