Why Compare These Policies?
A response-adaptive allocation rule must balance two aims: learning about uncertain treatments and assigning participants to treatments expected to perform well. Explore-then-commit makes this balance in two distinct phases: it gathers a planned amount of information, then commits the remaining assignments to the arm with the best observed average. Upper confidence bound (UCB) makes the balance repeatedly, favoring arms whose observed averages are high or whose estimates remain uncertain.
The policies can make different decisions even when given the same early outcomes. A useful finite-trial comparison therefore states the horizon, reward model, policy settings, and objective. The examples below use Bernoulli rewards: an outcome is either 1 (a success) or 0 (no success). All data and trial settings are hypothetical.
Two Allocation Rules
For explore-then-commit, choose an exploration count \(m\) in advance and assign \(m\) participants to each arm. This requires \(Km\leq T\). Let \(\hat{\mu}_i\) be arm \(i\)'s mean reward in this exploration phase. Assign all remaining \(T-Km\) participants to an arm with the largest \(\hat{\mu}_i\), using a prespecified tie rule if needed. The rule does not revise its choice after commitment.
For UCB, first assign at least one participant to each arm so that every empirical mean is defined. After \(t\) assignments, let \(N_i(t)\) be the number assigned to arm \(i\), and let \(\hat{\mu}_i(t)\) be the mean reward observed on that arm. The common UCB1 index is
The next participant is assigned to an arm with the largest index. The first term rewards arms with high observed success; the second gives an exploration bonus that is larger for arms with fewer observations. Specify a tie rule, such as choosing the lowest-numbered arm. The index is a decision rule, not a promise that the arm’s true mean lies below it.
The bonus has a standard concentration-based motivation. For independent rewards bounded between 0 and 1, Hoeffding’s inequality gives \(P(\hat{\mu}_i-\mu_i\geq\epsilon)\leq\exp(-2N_i\epsilon^2)\) for a fixed arm and sample size. Substituting \(\epsilon=\sqrt{2\log(t)/N_i}\) makes this upper bound \(t^{-4}\). This motivates an optimism bonus that shrinks with sample size and changes with the horizon’s progress; it does not make each index an exact confidence bound for every adaptively selected arm.
Worked Finite-Trial Comparison
Worked Example: Explore-Then-Commit in Six Assignments
Consider three arms \(A\), \(B\), and \(C\), with horizon \(T=6\). Use \(m=1\), assigning one participant to each arm in the exploration phase. Suppose the observed rewards are \(A:0\), \(B:1\), and \(C:1\). Break ties in favor of \(C\). For evaluating allocations, suppose the working arm means are \(\mu_A=0.35\), \(\mu_B=0.50\), and \(\mu_C=0.65\). These means define a hypothetical reward model; the policy does not know them.
The exploration averages are \(\hat{\mu}_A=0/1=0\), \(\hat{\mu}_B=1/1=1\), and \(\hat{\mu}_C=1/1=1\). The tie rule selects \(C\). There are \(6-(3)(1)=3\) assignments left, so the final allocation counts are \(N_A=1\), \(N_B=1\), and \(N_C=4\).
Suppose the three additional observed rewards on \(C\) are \(0,1,0\). Total realized reward is \(0+1+1+0+1+0=3\) successes in six assignments. The pathwise pseudo-regret is calculated from the means and assignments, not those realized outcomes:
Thus, on this allocation path, the model assigns 0.45 expected successes’ worth of opportunity cost relative to assigning all six participants to the best-mean arm. The observed total of three successes is a different quantity.
Worked Example: UCB on the Same Initial Outcomes
Use the same three arms and initial outcomes \(A:0\), \(B:1\), \(C:1\), with \(T=6\). Assign each arm once, then apply the UCB1 index. If indices tie, choose \(B\) before \(C\). The working means remain \(0.35\), \(0.50\), and \(0.65\).
After three assignments, \(t=3\) and all counts equal 1. The bonus is \(\sqrt{2\log(3)/1}=1.482\), so the indices are \(U_A=1.482\), \(U_B=2.482\), and \(U_C=2.482\). The tie rule selects \(B\). Suppose this second reward on \(B\) is 0. Now \(t=4\), with counts \((1,2,1)\) and empirical means \((0,0.5,1)\). The indices are approximately \(1.665\), \(0.5+\sqrt{2\log(4)/2}=1.677\), and \(1+\sqrt{2\log(4)}=2.665\), respectively. UCB selects \(C\).
Suppose the second reward on \(C\) is 0. At \(t=5\), counts are \((1,2,2)\) and averages are \((0,0.5,0.5)\). The indices are \(1.794\), \(0.5+\sqrt{\log(5)}=1.768\), and \(0.5+\sqrt{\log(5)}=1.768\). UCB selects \(A\). If the second reward on \(A\) is 1, the six-assignment sequence is \(A,B,C,B,C,A\), with rewards \(0,1,1,0,0,1\). Total realized reward is 3.
The allocation counts are now \((2,2,2)\). Its pathwise pseudo-regret is
For these stipulated paths, the two policies both realized three successes, while UCB’s allocation has larger pseudo-regret under the stated means. That does not establish that explore-then-commit is generally better: different outcomes or means can reverse the comparison. It illustrates why the policy, the realized reward, and the modeled allocation objective must be reported separately.
What the Objective Does—and Does Not—Say
When the arm means are fixed, pathwise pseudo-regret summarizes the allocation’s model-based opportunity cost. Its expectation over all possible reward histories is the policy’s expected pseudo-regret. A single simulated path is not that expectation: other Bernoulli outcomes could produce different estimates, assignments, and regret. Estimating expected performance requires averaging across the policy’s possible paths, analytically or by simulation.
The following comparison is about decision structure, not a universal ranking. Both rules use reward information, but they use it differently.
| Feature | Explore-then-commit | UCB |
|---|---|---|
| Exploration | Set in advance by \(m\); every arm receives the same initial count. | Continues through the horizon, driven by the index bonus and observed rewards. |
| Response to new outcomes | After commitment, the selected arm does not change. | Recalculates indices after each assignment and reward. |
| Key design choice | Exploration count and tie rule. | Index definition, initialization, and tie rule. |
| Potential difficulty | A noisy early ranking can lock the policy onto a suboptimal arm. | Short-horizon index bonuses may devote assignments to learning when few assignments remain. |
Worked Example: A Noisy Commit Can Persist
Suppose \(T=6\), \(K=3\), and explore-then-commit uses \(m=1\). The hypothetical means are again \((0.35,0.50,0.65)\), but the initial observed rewards are now \(A:0\), \(B:1\), and \(C:0\). The empirical averages select \(B\), so the final allocation is \((1,4,1)\). Its pseudo-regret is
The policy commits to \(B\), although \(C\) has the largest stipulated mean. This is a possible consequence of one Bernoulli observation per arm, not proof that the policy is defective in every setting. Increasing \(m\) can reduce sensitivity to a single observation, but it uses more assignments before commitment and still cannot eliminate sampling uncertainty.
Assumptions, Diagnostics, and Alternatives
The comparison is most interpretable when each arm’s reward has a stable meaning and its distribution does not change during the trial. In the examples, rewards are independent Bernoulli draws conditional on assigned arms, with fixed means; assignments are sequential; all arms are available; and there are no minimum-share or safety constraints. These assumptions make the index and mean-based objective well-defined, but they may not adequately describe an actual clinical trial. Outcomes can be delayed, missing, or affected by calendar time, and clinical allocation may require safeguards not represented by either rule.
Before applying either policy, check that the reward is defined consistently, that its direction is clinically meaningful, and that each arm can be observed on the relevant timescale. During a design exercise or simulation, inspect allocation counts and observed averages at each decision. A zero count makes a UCB index undefined, so initialization must be explicit. For explore-then-commit, verify \(Km\leq T\), and examine whether plausible early outcomes could select an inferior arm. For UCB, check the index convention and tie rule, and inspect whether the bonus dominates the observed averages late in a short horizon. These checks can reveal coding or design problems; they do not establish clinical validity.
The choice also depends on the objective. Fixed-budget best-arm identification emphasizes learning which arm is best, whereas cumulative reward values rewards accrued during the trial as well as learning. Explore-then-commit and UCB are allocation rules whose consequences can be summarized using the stated cumulative-reward or regret objective; neither automatically solves a best-arm identification problem. Successive elimination, for example, removes arms when evidence supports doing so, while UCB keeps all initialized arms eligible. Other randomized rules, such as softmax allocation, use a different mechanism for retaining exploration. Comparisons are meaningful only when the horizon, reward definition, constraints, and target objective are held consistent.
A common mistake is to claim, “UCB has a confidence bound, so it must allocate more safely and achieve lower regret.” The correction is that UCB’s index is an optimistic selection score, not a clinical safety guarantee, exact confidence interval, or finite-sample ranking of policies. Another mistake is to read a lower pseudo-regret on one hypothetical path as proof of better expected performance. A single path gives a conditional illustration; expected performance concerns the distribution of paths under the model.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- With \(K=4\), \(T=20\), and \(m=3\), how many assignments remain after explore-then-commit exploration?
- For UCB, why does an arm with a small count often have a larger index bonus than an arm with a large count?
- A policy makes 2 assignments to arm \(A\), 3 to arm \(B\), and 1 to arm \(C\). If their means are \(0.20\), \(0.50\), and \(0.70\), respectively, calculate pathwise pseudo-regret.
- Why does observing a higher total reward for one policy on one simulated path not establish that it has higher expected cumulative reward?
Solutions. (1) Exploration uses \(Km=4(3)=12\) assignments, leaving \(20-12=8\). (2) The bonus is \(\sqrt{2\log(t)/N_i(t)}\); holding \(t\) fixed, a smaller \(N_i(t)\) makes the denominator smaller and the bonus larger. (3) The best mean is \(0.70\), so regret is \(2(0.70-0.20)+3(0.70-0.50)+1(0.70-0.70)=1.00+0.60+0=1.60\) expected successes’ worth of opportunity cost. (4) A simulated path is only one possible sequence of Bernoulli outcomes and resulting assignments. Expected cumulative reward averages over the policy’s possible paths under the model, so a comparison needs repeated simulation or a suitable calculation, not one realized total.