Greedy Allocation and Irreversible Lock-In

Why Greedy Allocation Can Get Stuck

Adaptive allocation uses observed outcomes to decide who receives each treatment next. A purely greedy rule makes this decision using the empirical rewards observed so far: it assigns the next patient to whichever treatment currently has the larger sample mean. This can look sensible when the sample means are reliable. Early in a trial, however, a small number of outcomes can be unusually favorable or unfavorable. If the rule then stops assigning patients to one treatment, it cannot collect the evidence that might correct its initial impression.

This tutorial isolates that risk. The key point is not that a greedy rule always chooses the inferior treatment, or that every early error is permanent. Rather, certain early histories create an absorbing allocation pattern: the treatment that appears better continues to be selected, and the neglected treatment’s estimate never changes. The distinction between a treatment’s true response probability and its observed mean is essential.

Model and Definition

Consider a trial with two treatments, \(A\) and \(B\), and a fixed horizon of \(T\) patients. Let \(Y_t\) be the binary reward observed for the patient assigned at time \(t\), where 1 denotes a favorable outcome and 0 an unfavorable outcome. Assume that each treatment \(i\) has a stationary response probability \(\mu_i=P(Y_t=1\mid\text{treatment }i)\). Conditional on the assignments, outcomes are independent Bernoulli observations with the response probability of the assigned treatment. Assume also that each outcome is observed before the next assignment, and that one patient’s treatment does not change another patient’s potential outcome.

These assumptions make the sample mean for a treatment a natural estimate of its response probability. They are substantive: changing patient mix over time, delayed outcome feedback, or treatment effects that vary with calendar time can make a simple stationary two-arm model inadequate. The examples below are hypothetical illustrations, not reports of a real trial.

An initial allocation to both treatments is necessary because an empirical mean is undefined before a treatment has been sampled. Pure greedy allocation describes what happens after this initialization. The number and order of initial assignments, as well as tie-breaking, are part of the policy and can affect its behavior.

A Simple Lock-In Mechanism

With Bernoulli rewards, one especially clear trap occurs when the apparently leading treatment has at least one observed success, while the neglected treatment’s observed mean is zero. If the greedy rule keeps assigning patients to the leading treatment, its sample mean remains strictly positive: the original success stays in the data, even if later outcomes are failures. The neglected treatment’s estimate stays at zero because it receives no further assignments. Thus the leading treatment remains strictly ahead at every subsequent decision.

Here \(S_A(t)\) is the number of successes observed on \(A\). This is a sufficient condition for permanent lock-in, not a claim that every greedy allocation error is permanent. If the neglected treatment has a positive empirical mean, enough new failures on the selected treatment can bring its mean below the neglected estimate and cause a switch. A greedy rule can therefore escape some bad starts, but it has no general guarantee of doing so promptly.

How Often Can This History Occur?

The lock-in condition can be translated into a probability under the model. If each treatment receives one initial patient, the two initial outcomes are independent Bernoulli variables. The particular history “success on inferior \(A\), failure on superior \(B\)” has probability \(\mu_A(1-\mu_B)\). On this history, the preceding argument shows that all later patients are assigned to \(A\).

Lock-In Is Possible, Not Inevitable

A greedy rule does not invariably remain with its first choice. If both initial empirical means are positive, continued outcomes on the selected treatment can eventually reduce its mean below the other treatment’s unchanged mean. The allocation then switches. The amount of evidence needed depends on the initial counts and outcomes. The following example makes the distinction concrete.

The contrast also explains why “irreversible” should be interpreted precisely. Once a treatment is no longer assigned, its estimate cannot improve or deteriorate; however, the selected treatment’s estimate can move. Permanent lock-in follows when the selected estimate is guaranteed to remain above the frozen estimate, as in the zero-mean Bernoulli example. In other histories, escape is possible, but the policy does not ensure that it will occur within a useful number of assignments.

Why the Problem Matters and How to Diagnose It

An allocation policy should be assessed not only by which treatment it selects at the next step, but also by whether its observations can correct a mistaken early ranking. In a finite trial, each assignment to an inferior treatment can carry an opportunity cost, while failing to sample a genuinely better treatment can leave uncertainty unresolved. The balance between patient benefit and learning is part of the allocation objective; earlier material on cumulative reward and regret formalizes these costs.

Several features of the allocation history can signal that pure greedy allocation is behaving poorly:

• Assignment counts stop growing for one treatment. If its observed mean has not changed for a long stretch, it may be starved of information rather than convincingly shown to be inferior.
• A large allocation imbalance follows very few observations. A high sample mean based on one or two patients is much noisier than the same mean based on many patients.
• Results depend strongly on the initial outcomes or tie rule. If small changes in initialization reverse most later assignments, the apparent allocation preference is fragile.
• The model’s assumptions are doubtful. Changing response rates, patient heterogeneity, dependence, or delayed outcomes can make a running sample mean a misleading summary even apart from greedy lock-in.

These are diagnostics, not proofs that one treatment is better. In particular, a low observed mean for an under-sampled treatment may reflect chance. A trial report should distinguish treatment response estimates from allocation frequencies and make clear how much information supports each estimate.

Comparison With Other Allocation Rules

The central difference between pure greedy allocation and its main alternatives is whether the rule deliberately gives weight to uncertainty or to additional learning. The table summarizes that distinction without implying that any alternative is automatically suitable for every clinical trial.

These approaches involve different trade-offs in reward, information, and allocation balance. A rule that explores more can reduce the chance of abandoning a superior treatment early, but may allocate more patients to a treatment that is in fact inferior. The appropriate choice depends on the trial’s objective, horizon, ethical constraints, and assumptions. Pure greediness is especially difficult to defend when initial samples are tiny and the cost of a mistaken early ranking is substantial.

Derivation of the Lock-In Bound

The probability calculation above also gives a short general justification for why greedy allocation can have expected regret that grows with the horizon. Suppose \(\mu_A<\mu_B\), both are in \((0,1)\), and exactly one initial observation is taken from each treatment. Consider the event \(E\) that the initial outcome on \(A\) is 1 and that on \(B\) is 0. Independence gives \(P(E)=\mu_A(1-\mu_B)\). On \(E\), the empirical means are 1 and 0. After any number \(k\geq0\) of further assignments to \(A\), its mean is at least \(1/(k+1)>0\), while \(B\)'s stays zero. Consequently, all \(T-2\) remaining assignments go to \(A\).

The gap for each such assignment is \(\Delta_A=\mu_B-\mu_A\). Since pseudo-regret is nonnegative on every history, restricting its expectation to \(E\) yields

For the numerical probabilities \(0.40\) and \(0.60\), the coefficient of \(T-2\) is \(0.40(0.40)(0.20)=0.032\), giving \(\mathbb{E}[R_T]\geq0.032(T-2)\) under this initialization and model. The bound is not an exact regret formula and does not describe all possible histories. It establishes that this one nonzero-probability failure mode alone can contribute an amount proportional to the number of remaining patients.

Limitations and Common Mistake

The examples rely on known, stationary Bernoulli response probabilities to assess what is truly better, but a real trial does not know those probabilities. The policy only sees realized outcomes. Nor does a lock-in calculation by itself settle whether an adaptive design is ethically or scientifically appropriate: outcome definitions, safety monitoring, delayed responses, inferential validity, and practical allocation constraints require separate consideration. A reward-maximizing rule is not a substitute for those design decisions.

The practical lesson is to inspect how the allocation rule uses uncertainty, not just which treatment currently has the higher estimated response. When small early samples determine almost all later assignments, the policy can convert random variation into a persistent imbalance.