Upper Confidence Bound Allocation

Why Add an Uncertainty Bonus?

An allocation rule that always chooses the arm with the largest observed average reward can overlook a treatment with few observations. Its average may be low because of chance, or it may be based on too little information to be persuasive. Upper confidence bound (UCB) allocation addresses this tension by scoring each arm using both its observed reward and a bonus for uncertainty. An arm with a smaller sample can therefore remain worth exploring.

In a trial viewed as a stochastic bandit, each treatment is an action and the outcome observed for the assigned participant is that action’s reward. The rule below is for maximizing reward: higher values are preferable. It is an allocation policy, not by itself a method for estimating treatment effects or establishing clinical benefit.

Definition: Suppose there are $K$ treatment arms and rewards lie in $[0,1]$. Before decision $t$, let $N_i(t-1)$ be the number of participants assigned to arm $i$ among the first $t-1$ participants, and let $\bar{X}_i(t-1)$ be the mean of their observed rewards. For an arm with $N_i(t-1)>0$, the canonical UCB1 index is $$ U_i(t)=\bar{X}_i(t-1)+\sqrt{\frac{2\log(t)}{N_i(t-1)}}. $$ At decision $t$, assign the participant to an arm with the largest $U_i(t)$. If several arms tie, a prespecified tie-breaking rule selects among them.

Assumptions and Implementation

The basic rule is most naturally justified in a stationary stochastic reward model: for each arm, successive rewards are independent draws from the same distribution, with mean $\mu_i$, and rewards are bounded in $[0,1]$. The participant’s reward is observed for the assigned arm, but not for the other arms; this is bandit feedback. The rule uses the observed reward as a numerical quantity, so its clinical definition, direction, and scale must be chosen before allocation. If outcomes are adverse events, for example, they must be transformed or defined so that a larger reward consistently represents a more desirable outcome.

The index is undefined for an arm with no observations. A standard implementation therefore assigns at least one initial participant to each arm, in a prespecified order or by a separate randomized initialization. After that, the index is calculated using the number of completed observations before the current assignment. In a clinical trial with delayed outcomes, the update should use only rewards actually available at that decision; treating pending outcomes as observed would change the information set and invalidate the intended calculation.

Initialize.
Assign at least one participant to each arm, and record each observed reward. Do not calculate a UCB index for an arm with no observed rewards.

Calculate the indices.
At decision $t$, use the data available before assigning participant $t$: calculate each empirical mean and add its uncertainty bonus.

Choose and update.
Assign the participant to an arm with the largest index. Once that participant’s reward is observed, update that arm’s count and reward total; leave other arms’ statistics unchanged.

Worked Index Comparisons

Worked Example: Comparing Two Arms at One Decision

Suppose two arms have been observed before decision $t=13$. Arm A has 5 rewards of 8 participants, and arm B has 2 rewards of 4 participants. Assume these are hypothetical binary rewards, so each reward is 0 or 1 and lies in the required range. There are 12 previous participants in total, consistent with decision 13.

For arm A, the empirical mean is $5/8=0.625$. Its bonus is $$ \sqrt{\frac{2\log(13)}{8}} =\sqrt{\frac{5.1299}{8}} \approx 0.8008. $$ Thus $U_A(13)=0.625+0.8008\approx 1.426$.

For arm B, the empirical mean is $2/4=0.500$. Its bonus is $$ \sqrt{\frac{2\log(13)}{4}} =\sqrt{\frac{5.1299}{4}} \approx 1.132. $$ Thus $U_B(13)=0.500+1.132\approx 1.632$. UCB selects arm B, despite its smaller observed mean, because its smaller sample count gives it a larger uncertainty bonus. The index can exceed 1 even though rewards are bounded by 1; it is a decision score, not a possible reward.

Worked Example: Initialization and Sequential Updates

Consider two hypothetical treatments with binary rewards. Assign one participant to each arm initially; arm A returns 1 and arm B returns 0. At decision $t=3$, each arm has one observation. Both bonuses are $\sqrt{2\log(3)}\approx1.482$. Therefore $U_A(3)=1+1.482=2.482$, while $U_B(3)=0+1.482=1.482$, and the policy selects A. Suppose the next observed reward from A is 0.

At decision $t=4$, arm A has one success in two observations, and arm B still has zero successes in one observation. For A, $$ U_A(4)=\frac{1}{2}+\sqrt{\frac{2\log(4)}{2}} =0.500+\sqrt{1.3863} \approx 0.500+1.177 =1.677. $$ For B, $$ U_B(4)=0+\sqrt{\frac{2\log(4)}{1}} =\sqrt{2.7726} \approx1.665. $$ The policy selects A, because its index is slightly larger. The example also shows why the decision time and the count have distinct roles: $t$ is the overall decision number, whereas the denominator is the number of observations for that arm.

Worked Example: Ranking Three Arms

At decision $t=21$, suppose three hypothetical arms have the following binary-reward records: A has 7 rewards in 10 observations, B has 4 in 5, and C has 2 in 5. The counts sum to 20, as required before decision 21. Since $2\log(21)\approx6.0890$, the bonuses for A and for each arm with 5 observations are: $$ \sqrt{\frac{6.0890}{10}}\approx0.7803, \qquad \sqrt{\frac{6.0890}{5}}\approx1.104. $$ The indices are $U_A(21)=0.700+0.7803=1.480$, $U_B(21)=0.800+1.104=1.904$, and $U_C(21)=0.400+1.104=1.504$, to three decimals. UCB selects B. B has both the largest observed mean and a larger bonus than A. C’s substantial bonus does not compensate for its lower mean enough to give it the highest index.

Why the Index Has This Form

The score combines an estimate of current performance with an allowance for uncertainty. The empirical mean is the observed reward average for an arm; it is the natural estimate of that arm’s mean reward under a stationary model. The bonus decreases as the arm accumulates observations, at a rate proportional to $1/\sqrt{N_i}$, because an average is generally more precise when based on more independent observations. The $\log(t)$ term grows with the overall decision number, so an arm that has been sampled rarely can become competitive again as the trial continues.

The UCB name reflects an optimistic decision principle: treat the arm’s plausible reward as its empirical mean plus an allowance for uncertainty, then choose the most promising such score. In a bounded-reward model, concentration inequalities motivate bonuses of this general form. The particular UCB1 bonus above is a standard choice, not a universal clinical confidence interval with a stated coverage probability. Its statistical analysis depends on the model assumptions; the following tutorial develops the concentration-inequality connection.

A useful check is how the index responds to its inputs. Holding $t$ fixed, increasing $N_i$ decreases the bonus. Holding $N_i$ fixed, increasing $t$ increases it. Increasing the empirical mean increases the index by the same amount. These properties explain how the rule can allocate to an arm with a lower observed mean while still favoring an arm that has been sampled little.

Diagnostics, Alternatives, and Limitations

Implementation checks can catch many failures before they affect allocation. Confirm that every arm has an initial observation, the reward scale is bounded and oriented consistently, and the denominator is the arm-specific count before the current assignment. Also verify that observed rewards update only the assigned arm, and that delayed or missing outcomes are handled according to a stated rule. A log of decision time, counts, empirical means, bonuses, indices, and selected arm makes discrepancies auditable.

An unexpectedly persistent allocation to one arm is not automatically a coding error: a high empirical mean can dominate the bonus. However, inspect the reward definition, outcome availability, count updates, and index calculations if an arm receives implausibly little allocation. Basic UCB is especially sensitive to nonstationarity: if reward distributions change over time, old observations continue to influence the mean even when they no longer describe current outcomes. It also does not account automatically for prognostic covariates, delayed outcomes, treatment interactions, safety constraints, or minimum allocation requirements.

Approach	How it chooses	Contrast with basic UCB
UCB	Maximizes empirical mean plus a count-dependent uncertainty bonus.	Exploration is determined by the index rather than a fixed random-exploration probability.
Epsilon-greedy	Usually chooses the empirically best arm, but explores at a specified probability.	Exploration is controlled directly by epsilon and need not target arms according to their uncertainty.
Explore-then-commit	Samples arms during a designated exploration phase, then commits to one arm.	Exploration is concentrated in a fixed initial phase rather than adapted at every decision.

These alternatives answer the same broad exploration-versus-exploitation problem, but none automatically guarantees that a trial is ethically or statistically suitable. UCB’s standard form can allocate very unevenly, and its reward-maximization objective can conflict with balanced treatment-effect estimation, safety monitoring, or preserving adequate data on every arm. Its deterministic choice conditional on the history is not the same thing as a fixed randomization probability for each treatment. A trial protocol must separately address clinical equipoise, participant protection, estimands, and the inferential consequences of adaptive allocation.

Common Mistake

Common pitfall: “Arm A has the larger observed mean, so UCB must select A.” This ignores the uncertainty bonus. The policy compares $\bar{X}_i+\sqrt{2\log(t)/N_i}$ across arms, not empirical means alone. In the first comparison above, B’s smaller sample produces a sufficiently larger bonus to give it the highest index. The reverse mistake is to interpret a larger index as proof that an arm’s true mean is larger; an index is a rule for choosing an action, not proof of treatment superiority.

Check Your Understanding

Answer each question using the stated UCB1 index. Solutions follow the questions.

At decision $t=10$, an arm has 4 successes in 8 binary-reward observations. Write its index and explain why its bonus is not based on 10 observations.
Two arms have the same empirical mean at a fixed decision time, but arm A has fewer observations. Which has the larger UCB index, assuming both counts are positive?
Why must a basic UCB implementation initialize every arm before calculating its indices?
Does an index greater than 1 contradict the assumption that rewards lie in $[0,1]$? Explain.
Name one reason the standard stationary UCB rule might be unsuitable without modification in a clinical trial.

Solutions. (1) The mean is $4/8=0.5$, so $U(10)=0.5+\sqrt{2\log(10)/8}\approx0.5+\sqrt{0.5756}\approx1.259$. The denominator is the arm’s 8 observations; 10 is the overall decision time. (2) Arm A has the larger bonus because, at fixed $t$, a smaller positive denominator gives a larger bonus; therefore it has the larger index. (3) With zero observations, the empirical mean and the stated bonus are undefined, so an initial assignment is needed. (4) No. The index adds a nonnegative bonus to the empirical mean and is a decision score, not a reward value. (5) For example, changing reward distributions violate stationarity, or delayed outcomes mean the observed information may not be available when the policy needs it.