Constrained Bandits With Minimum Allocation Shares

Why Put Minimum Shares Into the Policy?

A bandit policy uses accumulating outcomes to guide later treatment assignments. In a clinical trial, however, a reward-seeking rule may allocate too few participants to one or more treatments to satisfy a design requirement. A minimum-share requirement makes that concern explicit: each treatment must receive at least a specified fraction of the trial’s participants.

The important step is to translate a share into a count and then account for the remaining horizon. Checking only whether the current assignment seems reasonable is not enough. A policy must also avoid choices that leave too few enrollment slots to meet outstanding minimums. This is a feasibility constraint on the bandit policy, separate from the rule used to rank treatments by their observed or estimated rewards.

The ceiling is needed because participant counts are integers. For example, a requirement of at least 21% of a 10-person trial means at least \(\lceil 0.21(10)\rceil=3\) participants, not 2.1 participants. The quotas must be checked jointly: since each participant can be assigned to only one arm, a necessary condition for feasibility is \(\sum_{i=1}^{K}m_i\le T\). It is also sufficient when any arm can be assigned at any time and there are no additional restrictions on the assignment sequence.

Feasibility Across the Remaining Horizon

At time \(t\), define the remaining slots as \(r=T-t\). For each arm, its outstanding quota is the number of additional assignments still needed to reach its minimum. The total outstanding quota cannot exceed the number of remaining slots if completion is to remain possible.

A state is feasible when \(D(t)\le T-t\). The quantity \(D(t)\) counts the assignments that must still go to arms with unmet quotas; any remaining slots beyond that total are slack. This yields a direct rule for screening the next action.

In particular, when \(D(t)=r\), there is no slack: the next assignment must go to an arm with an outstanding quota. When \(D(t)<r\), there is at least one spare slot, so an assignment to an arm whose quota is already met can still be feasible. Minimum shares therefore do not necessarily prohibit assignments to other arms; they prohibit assignments only when those choices would make completion impossible.

Why the Feasibility Rule Works

The rule follows by checking what happens to the outstanding total after one assignment. Before the assignment, feasibility gives \(D(t)\le r\). If arm \(j\) has an outstanding quota, then \(d_j(t)\ge1\), so assigning the next participant to \(j\) reduces the total by one. If it does not, the total is unchanged. These are the only two possibilities.

The next state is feasible exactly when \(D(t+1)\le r-1\). If \(D(t)=r\), assigning to an arm with no outstanding quota leaves \(D(t+1)=r\), which exceeds the \(r-1\) slots left. Assigning to an arm with an outstanding quota instead gives \(D(t+1)=r-1\), which is feasible. If \(D(t)<r\), then the integer-valued total satisfies \(D(t)\le r-1\); even an assignment that does not reduce it leaves the next state feasible. This proves the rule for every feasible state.

Applying this check after each assignment maintains feasibility by induction: the initial state is feasible if \(\sum_i m_i\le T\), and every permitted action leads to another feasible state. If the policy continues assigning participants until the horizon, the quotas can therefore be met. This argument concerns quota feasibility, not whether the policy learns the arm rewards well or selects a clinically preferable treatment.

Restricting a Bandit Rule, Not Replacing It

Once infeasible actions are excluded, the policy can use its chosen bandit criterion to select among the remaining actions. For example, it can rank arms using an index rule such as UCB, as in the earlier material on UCB allocation. The constraint does not prescribe how to estimate rewards or rank eligible arms. It only screens out choices that would make the minimum quotas impossible to finish.

This example also shows why the constraint should be applied before selecting the highest-scoring arm. A score alone does not tell whether an action preserves the possibility of meeting the trial’s design requirements. Conversely, if there is slack, an arm with no minimum quota can remain eligible; the policy should not treat “minimum share” as “exclusive allocation.”

Rounding, Diagnostics, and Failure Modes

Share constraints can appear feasible before they are converted to integer quotas but fail after rounding. For example, with \(T=10\), four arms each assigned a minimum share of \(0.21\) have shares summing to \(0.84\), yet each quota is \(\lceil2.1\rceil=3\). The integer quotas sum to 12, exceeding the 10 available assignments. No allocation can satisfy all four requirements. A design must therefore check \(\sum_i\lceil q_iT\rceil\le T\), not just \(\sum_iq_i\le1\).

At each decision point, a useful diagnostic is to calculate the remaining slots and outstanding quotas from the current assignment counts. If \(D(t)>T-t\), the state is already infeasible: some prior action, quota specification, or enrollment record is inconsistent with completion. If \(D(t)=T-t\), every remaining assignment must reduce an outstanding quota. If \(D(t)<T-t\), some allocation flexibility remains. These checks can be automated and logged alongside the arm counts.

The calculation assumes a fixed horizon, one assignment per participant, fixed quotas, and that each remaining participant can be assigned to any arm. A trial that stops early, changes its target enrollment, or introduces restrictions on which arms can be assigned at particular times needs a feasibility check adapted to those conditions. For batch enrollment of \(b\) participants, a proposed batch must leave total outstanding quotas no greater than the slots after the batch, \(T-t-b\); checking only the first assignment in the batch is not enough when the rest are committed simultaneously.

What the Constraint Guarantees—and What It Does Not

A pathwise minimum-share constraint requires the quotas to be met on every allocation path allowed by the policy. This is stronger than requiring only that the expected number assigned to an arm meet a target. For example, an expected count above a quota does not rule out some realized trials falling below that quota. The feasibility rule in this tutorial protects the possibility of meeting integer quotas on the realized assignment path.

Minimum shares also differ from forced exploration and minimum sampling-rate rules discussed in the earlier material on forced exploration. A fixed-horizon minimum quota is a terminal requirement stated in counts; it need not specify how often an arm is sampled at each intermediate time. Many different policies can satisfy the same quotas while producing different reward histories and allocations beyond the minimums.

Finally, a quota is a design constraint, not a guarantee of good statistical or clinical performance. Satisfying the minimum counts does not ensure precise treatment-effect estimates, balanced information at every interim time, or favorable outcomes. Nor does it ensure that the reward-based part of the policy will behave well. The constraint’s narrower guarantee is valuable: if the initial quotas are feasible and every action passes the remaining-horizon check, the policy will not make quota completion impossible.

Common Mistake

A frequent error is to say that, when outstanding quotas exactly equal the remaining slots, an assignment to an arm with no outstanding quota is still acceptable because that arm’s own minimum has already been met. That reasoning ignores the total remaining requirement. If \(D(t)=r\), all \(r\) slots are already needed to fill outstanding quotas. Assigning outside those quotas leaves \(r\) required assignments but only \(r-1\) slots. The correction is to compare the sum of outstanding quotas with the remaining horizon after every proposed action, not merely to check the chosen arm’s status.