Successive Elimination of Inferior Arms

Why Eliminate Arms?

When a trial has several treatments, allocating patients indefinitely to every treatment can spend substantial sampling effort on arms that appear clearly worse. Successive elimination uses a more cautious principle: remove an arm only when its uncertainty interval lies entirely below the interval evidence for another arm. The key is that the intervals must account for repeated looks at the data; ordinary fixed-sample intervals do not automatically provide that protection.

The procedure below is a bandit allocation rule for comparing mean rewards. It does not establish that a treatment is clinically acceptable, nor does it replace a prespecified clinical analysis. Its guarantee concerns identifying arms with lower mean reward under stated sampling assumptions.

Model and Elimination Rule

Suppose there are $K$ treatment arms, indexed by $i=1,\ldots,K$. Each reward is in $[0,1]$, and arm $i$ has a fixed mean reward $\mu_i$. For example, a binary reward may indicate whether a hypothetical participant experienced a specified favorable outcome. For each arm, imagine an independent sequence of rewards $X_{i,1},X_{i,2},\ldots$, with the same distribution and mean $\mu_i$. At any stage, only the next observation from the assigned arm is revealed.

These assumptions mean that an arm's reward distribution does not change over time or in response to which other arms remain active. They also require that observations from an arm are independent draws from its reward distribution. The boundedness assumption is needed for the concentration bound used here. In an actual trial, dependence between participants, changing care, outcome delay, or informative missingness can undermine this model.

Definition: Let $A_r$ be the set of active arms at round $r$, and let $n_i$ be the number of observed rewards for arm $i$. Its sample mean is $\bar{X}_i(n_i)=\frac{1}{n_i}\sum_{s=1}^{n_i}X_{i,s}$. Given an error allowance $0<\delta<1$, define the confidence radius $$ c(n)=\sqrt{\frac{\log\!\left(\frac{\pi^2 K n^2}{3\delta}\right)}{2n}}. $$ The interval for arm $i$ is $L_i=\max\{0,\bar{X}_i(n_i)-c(n_i)\}$ to $U_i=\min\{1,\bar{X}_i(n_i)+c(n_i)\}$. Successive elimination removes every active arm $i$ satisfying $U_i<\max_{j\in A_r}L_j$.

An arm is removed only when its upper confidence bound is strictly below at least one active arm's lower confidence bound. An arm whose interval merely overlaps another's remains active. The intervals are clipped to the known reward range, which can make them more informative near zero or one without reducing their coverage.

A simple version samples every active arm once in each round, updates the intervals, and applies the elimination rule. If only one arm remains, the procedure can assign subsequent participants to it. Other schedules are possible, but the interval calculation and guarantee must still reflect the actual sampling plan and the number of times the data are examined.

Why the Confidence Radius Works

For a fixed arm and fixed sample size $n$, Hoeffding's inequality for independent rewards in $[0,1]$ gives

P\!\left(\left|\bar{X}_i(n)-\mu_i\right|>c(n)\right) \leq 2\exp\{-2nc(n)^2\}.

Substituting the definition of $c(n)$ makes the right-hand side $6\delta/(\pi^2 K n^2)$. A union bound over all $K$ arms and all positive sample sizes $n$ therefore gives

P\!\left(\text{at least one interval misses its }\mu_i \text{ at some arm and sample size}\right) \leq \sum_{i=1}^{K}\sum_{n=1}^{\infty} \frac{6\delta}{\pi^2 K n^2} =\delta,

because $\sum_{n=1}^{\infty}1/n^2=\pi^2/6$. Thus, with probability at least $1-\delta$, every interval covers its arm's mean at every sample size. This simultaneous statement matters: the procedure repeatedly checks intervals, and the number of observations at a check depends on which arms remain active. A guarantee for just one prespecified sample size would not, by itself, cover all those checks.

Theorem: Under the bounded, independent, stationary reward assumptions, with probability at least $1-\delta$, successive elimination never removes an arm whose mean equals the largest mean among all arms. On the same event, every removed arm has a strictly lower mean than at least one arm that was active when it was removed.

To justify the result, let $\mu_*=\max_i\mu_i$, and consider an arm $i_*$ with mean $\mu_*$. On the simultaneous-coverage event, its lower and upper bounds contain $\mu_*$. Every other active arm $j$ has $L_j\leq\mu_j\leq\mu_*$, so $\max_j L_j\leq\mu_*\leq U_{i_*}$. The elimination condition $U_{i_*}<\max_j L_j$ cannot hold. For any arm $i$ that is eliminated, there is an active arm $j$ with $U_i<L_j$. Coverage then gives $\mu_i\leq U_i<L_j\leq\mu_j$, proving that $i$ is strictly inferior to $j$. The probability of leaving this simultaneous-coverage event is at most $\delta$, which is the source of the error guarantee.

Applying the Rule

Worked Example: Eliminating One Arm From Three

Consider three hypothetical treatments with binary rewards and 1,000 observations per arm. Suppose the observed success counts are 800, 680, and 300, giving sample means $0.800$, $0.680$, and $0.300$. Use $\delta=0.05$ and $K=3$. Rewards are bounded, and for this example assume independent observations with a stable success probability within each arm.

For $n=1{,}000$, the common radius is

c(1000)=\sqrt{\frac{\log\!\left(\frac{\pi^2(3)(1000)^2}{3(0.05)}\right)}{2(1000)}} =\sqrt{\frac{\log(197{,}392{,}088}{2000}} \approx 0.0977.

The displayed substitution needs careful parentheses: the numerator inside the logarithm is $\pi^2(3)(1000)^2/[3(0.05)]$, approximately $197{,}392{,}088$. The resulting intervals, clipped to $[0,1]$, are approximately $[0.7023,0.8977]$, $[0.5823,0.7777]$, and $[0.2023,0.3977]$. The largest lower bound is $0.7023$, from the first arm. The third arm's upper bound, $0.3977$, is below it, so the third arm is eliminated. The second arm remains because its upper bound is not below $0.7023$; these data do not yet establish that it is inferior.

Worked Example: Elimination After Further Sampling

Suppose three hypothetical Bernoulli arms have, after 4,000 observations each, 2,880, 2,560, and 1,720 successes. Their sample means are $0.720$, $0.640$, and $0.430$. With $K=3$ and $\delta=0.05$, the radius at $n=4{,}000$ is

c(4000)=\sqrt{\frac{\log\!\left(\frac{\pi^2(3)(4000)^2}{3(0.05)}\right)}{8000}} \approx 0.0523.

The intervals are approximately $[0.6677,0.7723]$, $[0.5877,0.6923]$, and $[0.3777,0.4823]$. The third arm is removed because $0.4823<0.6677$, while the first and second remain because their intervals overlap.

Now suppose the two remaining arms each receive 4,000 further observations. Their cumulative totals are 5,760 successes from 8,000 observations for the first arm, and 4,960 from 8,000 for the second. The means are $0.720$ and $0.620$. Keep $K=3$ in the confidence radius, since the guarantee was set up for all three original arms. Then

c(8000)=\sqrt{\frac{\log\!\left(\frac{\pi^2(3)(8000)^2}{3(0.05)}\right)}{16000}} \approx 0.0381.

The intervals are approximately $[0.6819,0.7581]$ and $[0.5819,0.6581]$. Because $0.6581<0.6819$, the second arm is eliminated at this stage. The calculation uses cumulative, not just newly observed, successes. The additional observations for that arm correspond to 2,400 successes in 4,000 trials, so the stated cumulative total is consistent.

Worked Example: When Intervals Still Overlap

Suppose two hypothetical binary-reward arms have 3,100 and 2,900 successes from 5,000 observations each. Their sample means are $0.620$ and $0.580$. For $K=2$ and $\delta=0.05$,

c(5000)=\sqrt{\frac{\log\!\left(\frac{\pi^2(2)(5000)^2}{3(0.05)}\right)}{10000}} \approx 0.0468.

The intervals are approximately $[0.5732,0.6668]$ and $[0.5332,0.6268]$. Neither upper bound is below the other arm's lower bound, so neither arm is eliminated. The observed difference of $0.040$, or 4.0 percentage points, is not enough to overcome the uncertainty required by this confidence rule. This is not evidence that the arms have equal means; it is a decision to retain both because the data do not establish the required separation.

Allocation, Diagnostics, and Alternatives

In a round-based implementation, active arms are sampled, intervals are updated, and the elimination decision is made before the next round. Eliminating an arm reallocates future assignments among the survivors. The rule is therefore adaptive, but it is not the same as choosing the arm with the largest current sample mean at every assignment. In particular, an interval that is wide or overlaps its competitors can keep an arm active even when its current mean is lower.

Check the reward definition. A bounded numerical reward must have a consistent clinical interpretation. If rewards are not in $[0,1]$, the stated radius is not justified as written.
Inspect the sampling assumptions. Marked changes in patient mix, outcome ascertainment, or treatment delivery can make a single fixed $\mu_i$ an inadequate description. Dependence between responses also weakens the stated concentration guarantee.
Track interval width and sample counts. Very wide intervals can delay elimination. A small observed mean is not sufficient by itself; the upper bound must be below another arm's lower bound.
Do not treat an uneliminated arm as equivalent. Overlap means the rule has not established inferiority. It is not a test result proving equality or a conventional p-value for a treatment contrast.
Check the schedule and repeated looks. The radius here protects all arms and sample sizes under the stated model. Replacing it with an unadjusted fixed-sample interval while repeatedly checking can invalidate the error guarantee.

Compared with UCB allocation, successive elimination uses confidence intervals primarily to remove arms; UCB instead uses optimistic bounds to guide ongoing choices while retaining candidate arms. Greedy allocation chooses according to the current largest sample mean and can stop exploring a promising but initially unlucky arm. Continued uniform sampling avoids data-dependent removal but keeps allocating to every arm, including ones already separated by the intervals. These alternatives answer different operational needs, and none removes the need to specify the reward and check the data-generating assumptions.

The procedure also has limitations. Its confidence radius can be conservative, especially when many arms are considered or when the true mean gaps are small. It may consequently retain inferior arms for a long time. Conversely, its $1-\delta$ protection is only as credible as the assumptions and the calculation used to construct the intervals. In a clinical setting, an arm's reward mean is not the only consideration: safety, patient benefit, and the validity of treatment-effect inference require separate attention.

Common Mistake

Common mistake: “The lowest sample mean is clearly worse, so eliminate that arm.” A low sample mean alone does not establish inferiority. The correction is to compare the arm's upper confidence bound with the largest lower confidence bound and eliminate only if $U_i<\max_j L_j$. If intervals overlap, retain the arm under this rule, even if its current mean is lowest.

Check Your Understanding

Answer each question, then compare with the short solutions below.

What does the parameter $\delta$ control in the simultaneous confidence statement?
Arm A has interval $[0.61,0.74]$, and arm B has interval $[0.47,0.59]$. Which arm, if either, can be eliminated by the rule?
Why is it not enough to use a confidence interval designed for one fixed sample size when intervals are repeatedly checked?
Two arms have overlapping intervals. Does this establish that their mean rewards are equal? Explain.

Solutions. (1) It bounds the probability that at least one of the constructed intervals misses its arm mean at any arm or sample size, under the assumptions; the simultaneous coverage probability is at least $1-\delta$. (2) Arm B can be eliminated because its upper bound $0.59$ is below arm A's lower bound $0.61$. (3) Repeated checking creates multiple opportunities for a fixed-sample interval to miss; the stated radius uses a union bound over arms and sample sizes to control those opportunities together. (4) No. Overlap means the elimination condition is not met; it does not prove equality or rule out a real difference in means.