Explore-Then-Commit Allocation

Why explore first and commit afterward?

A clinical trial may have a fixed enrollment horizon and a decision objective that rewards outcomes observed during the trial. Allocating every new patient to the arm with the best current sample mean can be risky: early estimates are noisy, and an initially lucky arm may stay ahead simply because it receives more patients. At the other extreme, continuing to divide patients evenly can spend many assignments on treatments that appear inferior. Explore-then-commit separates these competing aims into two stages: collect an initial balanced sample from every arm, then assign all remaining patients to the arm with the largest initial sample mean.

This policy is simple to specify and analyze, but it makes a consequential choice: once the exploration stage ends, new outcomes do not change the allocation. The number of initial observations per arm therefore controls how much the policy learns before it commits, while the remaining horizon controls the cost of choosing incorrectly.

Model and assumptions

For a standard analysis, represent the outcome on each patient as a reward \(X\) between 0 and 1, with larger values defined to be better. A binary success indicator is a common example. Arm \(i\) has an unknown mean reward \(\mu_i\), and \(\mu^*=\max_{1\leq i\leq K}\mu_i\) is the mean reward of a best arm. The sample mean from the \(m\) exploration outcomes on arm \(i\) is \(\bar{X}_i\). For Bernoulli rewards, it is the observed success proportion.

The usual finite-sample calculations assume that, for each arm, successive rewards are independent draws from a fixed distribution with mean \(\mu_i\), that rewards from different patients are independent, and that rewards lie in \([0,1]\). These conditions describe a stationary reward model: the distribution associated with an arm does not change over the trial or in response to which patients received it. The policy observes only the reward for the arm assigned to each patient, as in bandit feedback. In a clinical application, the reward must be defined before allocation, and its direction must be clear; an undesirable outcome cannot be treated as a benefit merely by calling it a reward.

These assumptions are substantive, not guaranteed by the allocation rule. If outcomes depend strongly on patient characteristics, calendar time, or previous treatment assignments, a single fixed mean \(\mu_i\) may not adequately describe an arm. The simple calculations below do not account for such changes or for the additional goals of estimating treatment effects and maintaining trial validity.

Constructing the policy

The exploration sample is balanced: each arm has exactly \(m\) outcomes before the policy compares arms. In a trial, the order of those assignments can be randomized while preserving the planned counts. After exploration, the policy selects an arm with maximum \(\bar{X}_i\), and every one of the \(L\) remaining patients is assigned to that arm. New observations in the commitment stage are not used to revise this choice.

Regret and the cost of commitment

The gap of arm \(i\) is \(\Delta_i=\mu^*-\mu_i\), which is nonnegative. The pseudo-regret of an allocation is the sum, over assigned patients, of the best arm’s mean reward minus the assigned arm’s mean reward. Expected pseudo-regret averages this quantity over the random outcomes and any random allocation. It measures expected reward foregone relative to assigning every patient to a best arm; it is not a measure of treatment-effect estimation accuracy.

The exploration expression follows because each arm \(i\) is assigned exactly \(m\) times during exploration, and each such assignment has mean-reward gap \(\Delta_i\). For commitment, the policy assigns all \(L\) patients to the same selected arm \(I\). Conditional on selecting arm \(i\), the expected per-patient gap is \(\Delta_i\), so the conditional expected commitment regret is \(L\Delta_i\). Averaging over the possible selected arms gives the stated sum. Therefore, expected total pseudo-regret is the sum of these two contributions.

A probability bound for selecting an inferior arm

Exact selection probabilities can be tedious to calculate. A useful general bound follows from Hoeffding’s inequality: if \(m\) independent observations lie in \([0,1]\) and have mean \(\mu\), then for \(a>0\), each one-sided deviation probability satisfies \(P(\bar{X}-\mu\geq a)\leq\exp(-2ma^2)\) and \(P(\mu-\bar{X}\geq a)\leq\exp(-2ma^2)\). This result requires independent, bounded observations with a common mean for the arm’s exploration sample.

Fix an optimal arm \(j\), so \(\mu_j=\mu^*\), and consider a suboptimal arm \(i\) with gap \(\Delta_i>0\). If arm \(i\) is selected, its sample mean must be at least as large as the optimal arm’s sample mean. That event requires at least one of two deviations: arm \(i\)’s sample mean is at least \(\Delta_i/2\) above its mean, or arm \(j\)’s is at least \(\Delta_i/2\) below its mean. Applying the one-sided inequality to each deviation and adding their probabilities yields

The minimum with 1 is included because a probability cannot exceed 1. Combining this bound with the regret decomposition gives the valid, though potentially loose, bound

The first term is exact; the second bounds commitment regret. The exponential term decreases as \(m\) or the gap increases, reflecting that more exploration or more clearly separated means makes an inferior selection less likely under the model. The bound does not say that a particular trial has a high probability of choosing correctly unless its numerical value supports that conclusion.

Choosing \(m\), diagnosing trouble, and alternatives

The exploration size involves a finite-horizon trade-off. Increasing \(m\) raises exploration regret because more patients are assigned to arms below the best mean. At the same time, it reduces \(L\) and can lower the chance of committing to an inferior arm. Since the unknown gaps determine how much information is needed to distinguish arms, there is no universally best \(m\) without further assumptions or design objectives. A choice of \(m\) should be made with the horizon, plausible reward differences, and the consequences of allocation errors in view.

The probability bound can also reveal when a nominal guarantee is uninformative. For example, with \(m=25\) and gap \(\Delta_i=0.20\), the bound is \(\min\{1,2\exp[-25(0.20)^2/2]\}=\min\{1,2\exp(-0.50)\}=1\), since \(2\exp(-0.50)\approx1.2131\). It supplies no nontrivial upper bound on the error probability. Omitting the factor 2 and reporting about 0.6065 would be an arithmetic and inequality error: 0.6065 is approximately \(\exp(-0.50)\), not \(2\exp(-0.50)\).

Practical warning signs include an exploration sample so small that one or two outcomes determine the selected arm, nearly tied sample means, or a commitment period that is long compared with exploration. In those situations, a selection based on noisy early data can have substantial consequences. Conversely, if \(Km\) is close to \(T\), the policy has little or no commitment period and may offer little allocation benefit from selecting a leader. The Hoeffding bound may be especially loose when the gap is small; it is a guarantee, not a diagnostic test of the actual trial’s selection error.

Explore-then-commit differs from a fixed balanced allocation, which continues sampling all arms and therefore does not make a single irreversible allocation decision, but may allocate many patients to arms with lower mean reward. It also differs from a continually adaptive policy, such as Thompson sampling, that can use outcomes throughout enrollment to revise assignments. Those alternatives have different allocation and inferential properties; explore-then-commit’s distinctive feature is the one-time switch from balanced exploration to commitment. Compared with simply selecting the arm with the largest early mean, its deliberate initial sampling protects against leaving an arm nearly unobserved.

The policy’s limitations matter in clinical trials. Maximizing a prespecified reward during enrollment is not the same as maximizing patient welfare across all outcomes, estimating treatment effects precisely, or preserving a conventional randomized comparison. A long commitment to one arm may leave limited concurrent information about alternatives. If the reward distribution changes over time, if patient groups differ in ways relevant to response, or if safety and allocation constraints apply, the stationary bounded-reward calculation may not describe the actual design. The policy should therefore be judged against the trial’s scientific and ethical objectives, not regret alone.

Common mistake

• Wrong reasoning: “Arm 2 had the largest exploration sample mean, so it is the best treatment.” Correction: The selected arm is only the empirical leader in a finite sample. Its true mean may be lower, and commitment makes the cost of that selection error depend on the remaining horizon.
• Wrong reasoning: “The error bound is 0.8897, so the error probability equals 0.8897.” Correction: It is an upper bound, not an exact probability; the exact two-arm example above calculated the probability directly.
• Wrong reasoning: “More exploration is always better.” Correction: More exploration can improve selection but also increases assignments made before commitment and reduces the number of patients remaining for it.