Fixed-Confidence Best-Arm Identification

Why Stop on Evidence Rather Than a Preset Budget?

In best-arm identification, the objective is to recommend the treatment with the largest mean reward, not to maximize reward accumulated during enrollment. A fixed-budget design samples for a predetermined number of patients and then recommends an arm. A fixed-confidence design instead specifies an acceptable error probability in advance and continues sampling until the data provide a sufficiently strong certificate for one treatment. The total sample size is then random: it depends on the observed outcomes.

A stopping rule must account for the fact that investigators may inspect the data repeatedly and stop at a time chosen from those data. Ordinary confidence intervals formed separately at each sample size do not, by themselves, justify a confidence claim after repeated checking. The construction below uses bounds that hold simultaneously over all arms and all sample sizes. This makes the stated error guarantee valid at the data-dependent stopping time.

Definition: There are \(K\) treatment arms. Arm \(i\) produces rewards \(X_{i,1},X_{i,2},\ldots\) that are independent and identically distributed, take values in \([0,1]\), and have fixed mean \(\mu_i\). After \(t\) observations from arm \(i\), let \(\bar{X}_{i,t}\) be their sample mean. A best arm is an arm whose mean is largest among \(\mu_1,\ldots,\mu_K\). The fixed-confidence goal is to stop and recommend an arm while ensuring that the probability of recommending a suboptimal arm is at most a prespecified \(\delta\), where \(0<\delta<1\).

The bounded-reward assumption is natural for Bernoulli outcomes, such as a success indicator, and for other outcomes scaled to the interval from zero to one. It can be replaced by other assumptions and corresponding concentration bounds, but the bounds and guarantee must then be changed accordingly. Here, the reward distribution for each arm is stationary, and the outcomes in that arm's reward sequence are independent. The allocation rule may use past observations to choose which arm to sample next; it must not use future outcomes.

An Anytime Confidence-Bound Stopping Rule

Choose \(\delta\) before the experiment. For each arm \(i\) and each positive sample size \(t\), define a radius and bounds by

r_t=\sqrt{\frac{\log\!\left(2K t(t+1)/\delta\right)}{2t}},\qquad L_{i,t}=\max\{0,\bar{X}_{i,t}-r_t\},\qquad U_{i,t}=\min\{1,\bar{X}_{i,t}+r_t\}.

The bounds are clipped to the known reward range. If arm \(i\) has currently received \(t_i\) observations, apply the following rule: stop as soon as some arm \(i\) satisfies \(L_{i,t_i}>U_{j,t_j}\) for every other arm \(j\). Recommend that arm. The strict inequality means the leading arm's entire lower bound is above every competitor's upper bound.

The rule is a certificate, not merely a ranking of sample means. An arm can have the largest observed mean without having a lower bound above the other arms' upper bounds. In that case the data do not yet satisfy this stopping rule.

Why the Confidence Guarantee Holds

For independent observations in \([0,1]\), Hoeffding's inequality gives, for any fixed arm \(i\), sample size \(t\), and \(r>0\),

P\!\left(\left|\bar{X}_{i,t}-\mu_i\right|>r\right)\leq 2\exp(-2tr^2).

Substitute \(r=r_t\). Since \(2t r_t^2=\log(2Kt(t+1)/\delta)\), the probability that the bound fails for this arm at this sample size is at most \(\delta/[Kt(t+1)]\). Summing these probabilities over every arm and every positive integer sample size gives

\sum_{i=1}^{K}\sum_{t=1}^{\infty}\frac{\delta}{Kt(t+1)} =\delta\sum_{t=1}^{\infty}\left(\frac{1}{t}-\frac{1}{t+1}\right) =\delta.

This is a union bound, so it does not require independence between the confidence-bound events. In particular, it covers all sample sizes at once. Let \(E\) be the event that every arm's mean is inside its bounds at every sample size. The calculation shows that \(P(E)\geq 1-\delta\). Because \(E\) holds for all sample sizes, it also holds at sample sizes selected by an adaptive allocation rule.

Theorem: Under the stated bounded, stationary reward assumptions, the probability that the stopping rule recommends a suboptimal arm is at most \(\delta\), regardless of how the next arm is chosen from past data. This is an error-probability guarantee; it does not, by itself, guarantee that the rule stops by a particular enrollment total.

To verify the claim, suppose the rule stops and recommends arm \(i\). On event \(E\), the true means satisfy \(\mu_i\geq L_{i,t_i}\) and \(\mu_j\leq U_{j,t_j}\) for each \(j\ne i\). Therefore,

\mu_i\geq L_{i,t_i}>U_{j,t_j}\geq\mu_j \quad\text{for every }j\ne i.

Thus arm \(i\) is truly better than every other arm on \(E\). A suboptimal recommendation can occur only if \(E\) fails, whose probability is at most \(\delta\). This proves the guarantee, including when the stopping time is chosen using the observed data.

Worked Examples

Worked Example: Bounds Do Not Yet Separate

Suppose two hypothetical Bernoulli treatments each have 100 observations. Arm 1 has 70 successes and arm 2 has 60 successes. Use \(\delta=0.10\) and determine whether the rule stops.

The observed means are \(\bar{X}_{1,100}=70/100=0.70\) and \(\bar{X}_{2,100}=60/100=0.60\). With \(K=2\) and \(t=100\), the radius is

r_{100}=\sqrt{\frac{\log(2\cdot2\cdot100\cdot101/0.10)}{2\cdot100}} =\sqrt{\frac{\log(404{,}000)}{200}} \approx 0.2541.

Thus arm 1's lower bound is \(0.70-0.2541=0.4459\), and arm 2's upper bound is \(0.60+0.2541=0.8541\). Since \(0.4459\) is not greater than \(0.8541\), the rule does not stop. The higher observed success rate alone does not certify that arm 1 has the higher mean.

Worked Example: A Fixed Budget Can Leave the Rule Unresolved

In a second hypothetical two-arm Bernoulli experiment, suppose each arm receives exactly 500 observations, with 300 successes on arm 1 and 270 on arm 2. Let \(\delta=0.05\). Evaluate the stopping criterion at this point.

The sample means are \(0.60\) and \(0.54\). The common radius is

r_{500}=\sqrt{\frac{\log(2\cdot2\cdot500\cdot501/0.05)}{2\cdot500}} =\sqrt{\frac{\log(20{,}040{,}000)}{1{,}000}} \approx 0.1297.

The leading arm's lower bound is \(0.60-0.1297=0.4703\), while the other arm's upper bound is \(0.54+0.1297=0.6697\). The bounds overlap, so the rule cannot stop at this point. A fixed-budget procedure must still recommend an arm if its budget is exhausted; this fixed-confidence rule instead requires further sampling or remains unresolved.

Worked Example: Three Arms and a Certified Recommendation

Consider hypothetical Bernoulli outcomes from three treatments, each observed 5,000 times. Suppose the success counts are 3,600, 3,000, and 2,750, respectively. Use \(\delta=0.10\) to decide whether the rule stops.

The observed means are \(0.72\), \(0.60\), and \(0.55\). For \(K=3\) and \(t=5{,}000\),

r_{5000}=\sqrt{\frac{\log(2\cdot3\cdot5{,}000\cdot5{,}001/0.10)}{10{,}000}} =\sqrt{\frac{\log(1{,}500{,}300{,}000)}{10{,}000}} \approx 0.0460.

Arm 1's lower bound is approximately \(0.72-0.0460=0.6740\). The upper bounds for arms 2 and 3 are \(0.60+0.0460=0.6460\) and \(0.55+0.0460=0.5960\). Since \(0.6740\) exceeds both, the rule stops and recommends arm 1. Under the stated assumptions, the probability that this rule ever recommends a suboptimal arm is at most \(0.10\); the calculation does not mean that there is a 90% probability that arm 1 is best given these data.

Stopping, Ties, and Practical Diagnostics

The confidence guarantee and eventual stopping are separate properties. If there is a unique best arm and every arm continues to be sampled infinitely often whenever the rule has not stopped, the strong law of large numbers implies that each sample mean converges to its arm's mean. Also, \(r_t\) tends to zero as \(t\) grows. The positive gap between the best mean and each competing mean then eventually exceeds the combined uncertainty, so the bounds separate and the rule stops with probability one. Without continued exploration of every arm, this termination argument does not apply: an arm that is rarely or never sampled can retain a wide bound indefinitely.

If two or more arms tie for the largest true mean, strict separation of one of them from all others is impossible on event \(E\). In that case, this particular rule need not stop. Outside \(E\), finite-sample bounds can fail and the rule can separate tied arms; such a mistaken recommendation is part of the event controlled by the \(\delta\) guarantee. Thus the guarantee does not promise termination in every configuration of means.

The principal alternative is fixed-budget best-arm identification: choose a total sample size in advance, allocate those observations, then recommend an arm, often the one with the largest sample mean. Fixed-budget designs make enrollment easier to plan but do not automatically provide a prespecified upper bound on the probability of a wrong recommendation. Fixed-confidence designs target that error probability directly, but have a data-dependent sample size and may require substantial enrollment when the means are close. Neither objective is uniformly preferable; the choice depends on whether a firm sample budget or an explicit error guarantee is the primary design requirement.

Useful diagnostics include tracking each arm's sample count, observed mean, and current bounds. If bounds remain wide, more data may be needed; if an arm receives too few observations, the allocation rule may be preventing a useful decision. The stated coverage is invalid if the reward assumptions or the bound construction are mismatched—for example, if rewards are unbounded but the bounded-reward formula is used. Repeatedly checking ordinary pointwise intervals and stopping when one looks favorable is also not a substitute: the simultaneous construction above is what justifies checking at data-dependent times.

Common Pitfalls

Stopping because one sample mean is largest. A ranking is not a certificate. Check that the leading lower bound is strictly greater than every competing upper bound.
Reading \(\delta\) as the probability that the null hypothesis is true. It bounds the design's probability of a suboptimal recommendation under the assumptions; it is not a posterior probability about which arm is best.
Assuming the rule has a fixed sample size. The stopping time depends on the data. A confidence guarantee does not impose a maximum enrollment total.
Ignoring ties or insufficient exploration. Tied best arms may prevent strict separation on the simultaneous-coverage event, and an arm that is not sampled enough may prevent termination.

Key takeaway: Fixed-confidence best-arm identification stops only when simultaneous confidence bounds strictly separate one treatment from all competitors. The all-times coverage argument protects the error guarantee under adaptive sampling and data-dependent stopping, while termination still depends on the reward gaps and continued sampling.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

Why does the confidence guarantee remain valid when the sample size from an arm is chosen adaptively?
For two arms with 500 observations each, \(\delta=0.05\), and sample means \(0.60\) and \(0.54\), calculate the radius and decide whether the rule stops.
Does the error guarantee alone ensure that the rule stops if an allocation policy stops sampling one of the arms? Explain.
What does the rule's guarantee say when the best treatment is tied with another treatment?

Solutions. (1) The construction bounds the probability of failure for every arm and every positive sample size; the union bound gives simultaneous coverage over all those possibilities. The coverage event therefore includes whichever sample sizes the adaptive rule reaches. (2) The radius is \(\sqrt{\log(20{,}040{,}000)/1{,}000}\approx0.1297\). The leading lower bound is \(0.60-0.1297=0.4703\), and the other arm's upper bound is \(0.54+0.1297=0.6697\), so the rule does not stop. (3) No. The error guarantee bounds the chance of a wrong recommendation if one is made; it does not guarantee a recommendation or termination. A persistently undersampled arm can retain a wide bound. (4) The chance of recommending a suboptimal arm is at most \(\delta\), but strict separation may not occur on the simultaneous-coverage event when best arms are tied, so termination is not guaranteed in that case.