Deriving UCB from Concentration Inequalities

Why a Confidence Bound Becomes an Allocation Rule

An upper confidence bound (UCB) policy uses uncertainty as a reason to explore. If two treatment arms have similar observed average rewards, the arm with fewer observations generally has a wider uncertainty allowance and may therefore have the larger index. The policy selects the arm with the largest index, balancing observed performance with the possibility that an under-sampled arm is better than its current data suggest.

The derivation starts with a concentration inequality: a statement bounding how far a sample mean can deviate from its population mean. Applying that inequality to each arm gives an upper confidence bound. Making the bound depend on the number of allocation decisions yields an index that can be recalculated as the trial proceeds.

Assumptions and the Concentration Bound

For the derivation below, assume that rewards from each arm are independent and identically distributed over successive allocations, with a fixed mean \(\mu_i\), and lie in the interval \([0,1]\). These conditions allow the standard Hoeffding inequality for bounded independent observations. Independence between different arms is not needed for the union bounds used here. In a bandit formulation, one can think of each arm as having an underlying sequence of rewards, with the policy observing the next value in a sequence only when that arm is allocated.

The boundedness condition matters: a binary clinical outcome coded as 0 or 1 meets it, as does any reward deliberately scaled to \([0,1]\). A reward measured on \([a,b]\) can be shifted and scaled to \([0,1]\); in the original units, the uncertainty allowance is multiplied by \(b-a\). Unbounded outcomes do not meet this assumption without additional distributional conditions or a different concentration result.

For independent observations in \([0,1]\), Hoeffding's inequality gives, for every \(\varepsilon>0\),

The same bound applies to the lower tail, \(P(\mu_i-\bar{X}_{i,n}\geq\varepsilon)\). These are probability statements about repeated samples under the assumed reward model; they do not make the fixed parameter \(\mu_i\) random.

From Hoeffding's Inequality to an Index

To construct a one-sided upper confidence bound with failure probability at most \(\delta\), set the right-hand side of Hoeffding's inequality to \(\delta\) and solve for \(\varepsilon\). This gives

Thus, for a fixed sample size \(n\), the quantity \(\bar{X}_{i,n}+\sqrt{\log(1/\delta)/(2n)}\) is an upper confidence bound: the probability that it falls below \(\mu_i\) is at most \(\delta\). This fixed-sample statement alone does not guarantee coverage after repeatedly checking the data and choosing arms adaptively. A time-dependent allowance is needed for a bound that holds across ongoing decisions.

A common UCB index for rewards in \([0,1]\), used after every arm has been tried at least once, is

Here \(t\) is the decision number, \(N_i(t-1)\) is the number of allocations to arm \(i\) before decision \(t\), and \(\bar{X}_{i,N_i(t-1)}\) is its observed mean. The policy selects an arm maximizing \(U_i(t)\). If an arm has not yet been tried, its index is treated as \(+\infty\) until it has received an initial allocation. This initialization prevents division by zero and ensures that every arm has data before the usual index is used.

The coefficient in this common index can be seen by applying Hoeffding's inequality with \(\varepsilon=\sqrt{2\log(t)/n}\). For a fixed arm and sample size, the one-sided failure probability is at most \(t^{-4}\). The log term increases with decision number, so the policy does not treat a bound that was useful early in the trial as if it were automatically sufficient after many decisions.

For a more explicitly calibrated simultaneous guarantee, choose a target error probability \(\delta\in(0,1)\), let \(K\) be the number of arms, and set \(C=\pi^2/6\). The index

has a useful all-times interpretation. For each decision time \(t\), each arm \(i\), and each possible sample size \(m\leq t\), Hoeffding's inequality bounds the chance of \(\bar{X}_{i,m}-\mu_i\) exceeding the displayed allowance by \(\delta/(CKt^3)\). There are at most \(Kt\) such arm and sample-size pairs at time \(t\). A union bound over those pairs and then over \(t\geq1\) gives total failure probability at most

Consequently, with probability at least \(1-\delta\), every arm's mean is below its index at every decision time for which it has been sampled. This version is deliberately conservative: it pays for simultaneous coverage over arms, sample sizes, and decision times. It is a clear confidence guarantee, not a claim that the usual UCB index has precisely the same error probability.

Worked Examples

Why Optimism Promotes Exploration

The index turns uncertainty into a selection incentive. An arm with few observations has a larger square-root term; if it may plausibly have a high mean, its index can exceed the indices of arms with better observed means. As an arm receives more allocations, its sample-size denominator grows and its uncertainty allowance generally shrinks.

A short justification shows the role of optimism. Let \(\mu_*\) be the largest arm mean. Suppose that, at a particular decision, the indices are genuine upper bounds and also that each empirical mean is no more than its mean plus the same allowance \(r_i\). If the policy selects arm \(i\), its index is at least the index of an optimal arm. Hence

Writing the gap as \(\Delta_i=\mu_*-\mu_i\), this implies \(\Delta_i\leq2r_i\). For the common index, \(r_i=\sqrt{2\log(t)/N_i}\); thus, whenever this confidence event holds, a selected arm with a positive gap must satisfy

This calculation explains the mechanism, not a complete regret guarantee: a full guarantee must also account for the probability of confidence failures, initial allocations, and the trial horizon. It does show why, on a well-behaved confidence event, repeated selection of a clearly inferior arm becomes difficult once that arm has accumulated enough data.

Diagnostics, Alternatives, and Limitations

The validity of the concentration-based index depends on the reward model, not just on correct arithmetic. Before applying it, check that the reward scale is genuinely bounded as assumed, that the target mean is stable over the trial, and that observed rewards are not being selectively omitted in a way that changes their distribution. The adaptive choice of an arm does not by itself invalidate the argument: each arm's successive rewards can be viewed as a fixed independent sequence, and the union bound covers the possible sample sizes. But dependence over time, changing treatment effects, or unmodelled changes in patient mix can undermine the iid, fixed-mean assumption.

Other warning signs include an index that is interpreted as a treatment-effect confidence interval, or a reward definition that does not match the clinical objective. UCB is a reward-allocation rule; its optimism allowance is not automatically a valid interval for comparing treatment effects under a separate inferential analysis. Also, if rewards are recorded on \([a,b]\) rather than \([0,1]\), the radius must be multiplied by \(b-a\). Using the unit-range formula without rescaling can make the index unjustifiably narrow.

UCB differs from greedy allocation because greedy allocation selects the arm with the largest observed mean and gives no explicit allowance for uncertainty. It differs from fixed exploration rules, such as allocating a prespecified fraction of decisions to exploration, because the UCB exploration pressure responds to observed sample sizes and the decision time. The common UCB index is computationally simple and uses only each arm's count and sample mean. Its limits are equally important: a broad bounded-reward inequality can be conservative, the chosen reward may not capture every clinical priority, and changing reward distributions need methods that address nonstationarity. For Bernoulli rewards, a later approach uses the specific information in the Bernoulli model to form a different index; that refinement is not needed for the concentration derivation here.

Common Mistake