Why Exploration Is Necessary: A Lower-Bound Argument

Why a Trial Must Learn Before It Can Choose Reliably

An adaptive trial may aim to assign patients to the treatment that offers the higher response probability. But the better treatment is not known when enrollment begins. If the two response probabilities are similar, the observations generated by the treatments can look alike for a long time. A policy that quickly favors one arm risks choosing incorrectly; a policy that seeks reliable evidence must spend patients learning about the alternatives.

The earlier material on regret defines the cost of allocating patients to an inferior arm. Here the question is different: how many observations are necessary even to identify the better arm with a specified error probability? A lower bound answers this without prescribing an allocation algorithm. It shows that limited information, not merely a poorly designed rule, can make reliable identification impossible.

Definition: In a two-arm Bernoulli model, arm $a\in\{1,2\}$ produces an independent binary response with probability $\mu_a$ of success whenever it is assigned. A policy chooses each patient's arm using only the past assignments and observed outcomes, possibly with its own randomization. After $T$ patients, it recommends an arm $\hat a$. Its identification error in a model with a unique best arm is the probability that $\hat a$ is not that arm.

The lower bound below concerns a policy that must work over more than one possible model. It assumes that the policy has error probability at most $\alpha$, where $0<\alpha<1/2$, in each of the two models being compared. This is a demanding uniform guarantee: the policy must distinguish both plausible explanations of the data, not just perform well in one model it already knows.

An Information Bound for Arm-Specific Sampling

Consider two environments. In $\theta$, arm 1 has success probability $q$ and arm 2 has success probability $p$, with $p<q$. Arm 1 is best. In the alternative environment $\theta'$, arm 1 still has probability $q$, but arm 2 has probability $r>q$, so arm 2 is best. The only change between these environments is arm 2's outcome distribution.

Theorem: Suppose $p<q<r$, the policy has error probability at most $\alpha<1/2$ in both $\theta=(q,p)$ and $\theta'=(q,r)$, and $N_2(T)$ is the number of patients assigned to arm 2 by time $T$. Then $$ \mathbb{E}_{\theta}[N_2(T)]\, \operatorname{kl}(p,r) \ \geq\ \operatorname{kl}(1-\alpha,\alpha), $$ where $$ \operatorname{kl}(u,v) = u\log\!\left(\frac{u}{v}\right) +(1-u)\log\!\left(\frac{1-u}{1-v}\right) $$ is the Bernoulli Kullback–Leibler divergence, using natural logarithms.

The result says that, in $\theta$, the policy must sample arm 2 even though arm 1 is better. If it rarely assigns patients to arm 2, the observed data will be nearly as compatible with $\theta'$ as with $\theta$; yet those environments have different best arms. A symmetric comparison can establish a corresponding requirement for sampling arm 1 in an environment where arm 2 is best. The need to learn applies to either treatment when either could plausibly be superior.

Why the Bound Holds

Let $A$ be the event that the policy recommends arm 1. Under $\theta$, arm 1 is best, so the error guarantee implies $P_{\theta}(A)\geq 1-\alpha$. Under $\theta'$, arm 2 is best, so $P_{\theta'}(A)\leq\alpha$. Thus the final recommendation must distinguish two data-generating environments.

The Kullback–Leibler divergence between the full observed histories under the two environments is $\mathbb{E}_{\theta}[N_2(T)]\operatorname{kl}(p,r)$. To see why, consider the likelihood ratio of a history. The policy's conditional probabilities for choosing an arm are the same functions of the observed history in both environments, so those factors cancel in the likelihood ratio. Outcomes on arm 1 also have the same distribution in both environments and contribute no log likelihood ratio. Each arm 2 outcome contributes the Bernoulli log likelihood ratio for probabilities $p$ versus $r$; taking its expectation under $\theta$ gives $\operatorname{kl}(p,r)$. Summing over the arm 2 assignments and taking expectation gives the stated history divergence.

Finally, reducing a full history to the binary event $A$ cannot increase its divergence. This data-processing property gives a lower bound by the divergence between the probabilities of $A$ in the two environments. For $x>y$, the binary divergence $\operatorname{kl}(x,y)$ increases as $x$ increases and as $y$ decreases. Since $P_{\theta}(A)\geq1-\alpha>\alpha\geq P_{\theta'}(A)$, that event divergence is at least $\operatorname{kl}(1-\alpha,\alpha)$. Combining the history-divergence expression with this lower bound proves the theorem.

\begin{aligned} D(P_{\theta}^{\text{history}}\Vert P_{\theta'}^{\text{history}}) &=\mathbb{E}_{\theta}[N_2(T)]\operatorname{kl}(p,r)\\ &\geq \operatorname{kl}\!\left(P_{\theta}(A),P_{\theta'}(A)\right)\\ &\geq \operatorname{kl}(1-\alpha,\alpha). \end{aligned}

Worked Examples

Worked Example: A Numerical Lower Bound on Arm 2 Patients

Suppose the true environment is $\theta=(0.55,0.50)$, while the alternative is $\theta'=(0.55,0.60)$. Assume a policy must recommend the best arm with error at most $\alpha=0.10$ in each environment. How many arm 2 patients must it assign on average under $\theta$?

The theorem applies: the arm 1 response probability is $0.55$ in both environments, arm 2 changes from $p=0.50$ to $r=0.60$, and the best arm switches. The information per arm 2 observation is $$ \begin{aligned} \operatorname{kl}(0.50,0.60) &=0.50\log\!\left(\frac{0.50}{0.60}\right) +0.50\log\!\left(\frac{0.50}{0.40}\right)\\ &=\frac{1}{2}\log\!\left(\frac{25}{24}\right) \approx 0.02041. \end{aligned} $$ The required decision-level divergence is $$ \operatorname{kl}(0.90,0.10) =0.90\log(9)+0.10\log(1/9) =0.80\log(9) \approx 1.758. $$ Therefore, $$ \mathbb{E}_{\theta}[N_2(T)] \geq \frac{1.758}{0.02041} \approx 86.12\text{ patients}. $$ This is a lower bound on the expected number assigned to arm 2 under the true environment, even though arm 2 is inferior there. It is not a prescription to assign exactly that many patients, nor a guarantee that this number suffices for every policy.

Worked Example: Close Bernoulli Probabilities Carry Little Information

For Bernoulli probabilities $0.50$ and $0.55$, calculate the divergence per observation and interpret why it matters for exploration.

Using the definition, not an approximation, $$ \begin{aligned} \operatorname{kl}(0.50,0.55) &=0.50\log\!\left(\frac{0.50}{0.55}\right) +0.50\log\!\left(\frac{0.50}{0.45}\right)\\ &=\frac{1}{2}\log\!\left(\frac{100}{99}\right) \approx 0.005025. \end{aligned} $$ This small positive value means that one observation from the two distributions provides little evidence for distinguishing them. In particular, $-\tfrac12\log(4(0.50)(0.55))$ is not the Bernoulli Kullback–Leibler divergence: it evaluates to about $-0.04766$, which cannot be a divergence. Using the correct formula is essential; inserting a negative value into an information lower bound would produce an impossible negative sampling requirement.

The local behavior makes the effect of a small gap clearer. With $p$ fixed and $\varepsilon$ small, define $f(q)=\operatorname{kl}(p,q)$. Direct differentiation gives $f(p)=0$, $f'(p)=0$, and $f''(p)=1/[p(1-p)]$. Taylor expansion around $q=p$ therefore gives $$ \operatorname{kl}(p,p+\varepsilon) = \frac{\varepsilon^2}{2p(1-p)} +o(\varepsilon^2). $$ Thus, when the two probabilities are close, information per observation shrinks approximately with the square of their difference. A fixed amount of evidence can then require a number of observations growing roughly as the inverse square of that difference.

Worked Example: A Horizon That Cannot Meet the Target

In the first example, the lower bound was about $86.12$ arm 2 patients. Suppose the trial has only $T=60$ patients. Can any policy have error at most $0.10$ in both specified environments?

Since $N_2(T)\leq60$, the largest possible left side of the theorem's inequality is $$ 60\operatorname{kl}(0.50,0.60) =60(0.02041) \approx1.225. $$ But the right side is $\operatorname{kl}(0.90,0.10)\approx1.758$, which is larger. The inequality cannot hold, so no policy can meet both error guarantees with this horizon. This conclusion concerns the stipulated pair of environments and uniform accuracy target; it does not say that every realized trial with 60 patients will make the wrong recommendation.

Assumptions, Diagnostics, and Alternatives

The argument relies on Bernoulli outcomes with stable probabilities within each environment, independent outcomes conditional on assignments, and a policy that bases choices only on the observed history and its randomization. The compared environments must differ only in the arm whose sampling count appears in the bound. The recommendation event must have the stated error probabilities in both environments. If outcomes are dependent, treatment effects change over time, or response probabilities vary with patient covariates, this exact formula need not apply; a model accounting for those features is required.

A practical diagnostic is to inspect whether the proposed policy could plausibly gather the information demanded by the bound. If its maximum possible count for an arm is below the lower bound, the target cannot be uniform over the compared environments. If its expected count is close to the bound, that is not by itself evidence of adequate performance: a lower bound rules out too little information but does not certify a procedure's error rate. Also check the direction of each divergence. For distinct Bernoulli probabilities, $\operatorname{kl}(p,r)>0$; a negative computed value signals an algebra or formula error.

Approach	What it can establish	What it does not establish
Information lower bound	A necessary sampling burden for a specified uniform error target and pair of environments	A policy that attains the bound or its exact allocation sequence
Fixed allocation	A transparent, prespecified way to gather observations from both arms	That the allocation is efficient for every gap, horizon, or objective
Adaptive allocation	A way to use observed outcomes to adjust later assignments	An escape from the information required to distinguish close alternatives

The bound also has limits. It is a necessary condition, not a full characterization of finite-sample performance, and the result depends on which alternative environment is used. Different alternatives can yield different bounds. Nor does a lower bound determine the best balance between identifying a treatment and accumulating patient benefit during the trial; those are distinct objectives.

A Common Mistake

Wrong reasoning: “The policy can assign almost everyone to the treatment that looks better after the first few responses, so it does not need to sample the other arm much.” This overlooks that early responses can be compatible with both environments. If the under-sampled arm has a different response probability in a plausible alternative, the observed history may not distinguish which treatment is best.

Correction: Compare the policy's behavior under two environments that differ only in that arm. If reliable recommendations require different answers in the two environments, the data must contain enough information to separate them. The theorem quantifies a necessary count; it does not require equal allocation or specify when exploration should occur.

Key takeaway: Reliable best-arm identification requires enough observations to distinguish the true environment from plausible alternatives. When arm outcomes are similar, each observation carries little information, and no adaptive rule can eliminate that sampling requirement.

Check Your Understanding

Use the definitions and lower bound above. Solutions follow the questions.

In $\theta=(0.70,0.40)$, which arm must be sampled in the stated comparison to $\theta'=(0.70,0.80)$, and why?
Why must $\operatorname{kl}(p,r)$ be nonnegative, and what should you check if a calculation gives a negative value?
If two compared environments require different recommendations but a horizon permits fewer samples than the lower bound, what conclusion follows?
Does satisfying the lower-bound inequality prove that a policy achieves the target error probability? Explain.

Solutions. (1) Arm 2: it is the only arm whose outcome distribution changes, and the best arm switches. (2) Kullback–Leibler divergence is nonnegative; check the formula, probability arguments, and logarithm arithmetic. (3) No policy can satisfy the stated uniform error target over that pair of environments within that horizon. (4) No. The inequality is necessary, not sufficient; a policy may sample enough in expectation and still fail the target error guarantee.