Forced Exploration and Minimum Sampling Rates

Why Force Exploration?

A greedy allocation rule assigns the next participant to the treatment with the highest current estimated mean reward. As the earlier material on greedy allocation and irreversible lock-in emphasizes, an initially favorable estimate can attract assignments before there is enough information to distinguish treatments. If other treatments then receive few or no assignments, their estimates may remain unreliable. Forced exploration addresses this specific failure mode by requiring some assignments to treatments even when their current estimates are not the largest.

The requirement can be expressed as a minimum number of assignments, possibly increasing with the trial horizon, or as a minimum share of the total enrollment. These guarantees describe how many times a treatment is assigned. They do not, by themselves, guarantee that the treatment effect is estimated precisely, that the best treatment is identified, or that the trial has low regret.

For concreteness, suppose each treatment has a stationary mean reward \(\mu_i\), and rewards are independent across participants and treatments, with rewards bounded between 0 and 1. These assumptions make the mean-reward and regret calculations below well-defined; they are not needed just to define a quota. Write \(\mu_*=\max_i \mu_i\) for the largest mean, and \(\Delta_i=\mu_*-\mu_i\) for treatment \(i\)'s gap from that mean. The pseudo-regret through time \(T\) is \(R_T=\sum_{t=1}^{T}\Delta_{A_t}\). Under these assumptions, \(0\leq \Delta_i\leq 1\), and each forced assignment has regret equal to the gap of the treatment assigned.

Building a Schedule With a Count Guarantee

One transparent construction starts with a nondecreasing integer-valued quota \(Q(t)\): the number of forced assignments that have occurred by time \(t\). Require \(Q(0)=0\), \(Q(t)\leq t\), and \(Q(t)-Q(t-1)\) to be either 0 or 1. On each forced round, assign the next treatment in a fixed cycle \(1,2,\ldots,K,1,2,\ldots\). On other rounds, use a chosen allocation rule, such as assigning to the treatment with the largest empirical mean. The forced schedule is separate from that rule: even when the empirical leader changes, the forced assignments remain due when the quota says they are due.

The cycle makes the per-treatment guarantee immediate. If \(Q(t)=q\), then \(q\) forced assignments have been distributed as evenly as possible over the \(K\) treatments. Each treatment therefore receives at least \(\lfloor q/K\rfloor\) forced assignments. Any additional assignments made by the non-forced part of the rule can only increase its total count.

A common slowly increasing quota is \(Q(t)=\lfloor c\log(t+1)\rfloor\), with a positive constant \(c\) chosen so that the quota increases by at most one per round. For example, using natural logarithms, \(c=1\) meets this condition: \(\log(t+1)-\log(t)\leq\log 2<1\) for integer \(t\geq1\). The quota grows without bound, so every treatment receives an increasing number of forced assignments, while the proportion of rounds spent on forced assignments tends to zero.

Minimum Rates and Their Allocation Cost

A minimum rate is often stated for the end of a fixed horizon. If each of \(K\) treatments must receive at least a fraction \(\rho\) of the \(T\) assignments, an integer quota is \(m=\lceil\rho T\rceil\) assignments per treatment. This requirement is feasible only if \(K\lceil\rho T\rceil\leq T\). A simple way to guarantee it is to assign each treatment \(m\) times in a forced exploration phase, then use the remaining assignments according to the chosen allocation rule. This construction gives a pathwise endpoint guarantee but does not require the same minimum share at every intermediate time.

Regret From Forced Assignments

The allocation cost can be written directly in terms of treatment counts. Let \(F_i(T)\) be the number of forced assignments to treatment \(i\) by time \(T\), and let \(F(T)=\sum_{i=1}^{K}F_i(T)\) be the total number of forced assignments. Their pseudo-regret contribution is \(\sum_i F_i(T)\Delta_i\). Since each gap is at most \(\Delta_{\max}=\max_i\Delta_i\), this contribution is bounded above by \(F(T)\Delta_{\max}\). With rewards in \([0,1]\), \(\Delta_{\max}\leq1\), so it is also bounded above by \(F(T)\).

For a cyclic schedule, each treatment's forced count is either \(\lfloor F(T)/K\rfloor\) or \(\lceil F(T)/K\rceil\). This fact allows the actual forced contribution to be calculated from the individual counts and gaps, and compared with the bound without confusing the two. The following example makes the distinction explicit.

When \(F(T)\) grows logarithmically, the forced part of regret is at most logarithmic in \(T\). When the rule forces a fixed positive share for each treatment, the number of forced rounds grows proportionally to \(T\), and their regret can also grow proportionally to \(T\) if suboptimal treatments have positive gaps. That linear cost may be acceptable when the minimum sampling requirement has an independent purpose, but it should not be described as a negligible exploration cost.

What the Guarantee Does—and Does Not—Provide

A forced count guarantee prevents complete neglect of a treatment, but a count alone is not a precision guarantee. For instance, one observation per treatment satisfies a positive minimum count yet is generally not enough to estimate a mean precisely. Precision depends on the outcome variability as well as the sample size. Similarly, a quota that grows like \(\log(T)\) ensures each treatment's count grows without bound, but the quota itself does not establish that the allocation rule will identify the best treatment or achieve a particular regret bound. Such conclusions require additional analysis of the estimation and decision rule.

The schedule also needs to match the actual enrollment horizon and operational constraints. A fixed endpoint quota can be infeasible if \(K\lceil\rho T\rceil>T\). If enrollment stops early, the planned endpoint count may not be reached. A treatment that is unavailable or suspended cannot be assigned merely because its quota is unmet. These are feasibility issues, not arithmetic details to be repaired after allocation.

Forced exploration is distinct from several common alternatives. Epsilon-greedy allocation randomizes away from the current leader with a specified probability; unless it is specially designed otherwise, this gives an expected number of exploratory assignments rather than a pathwise minimum count for every treatment. Upper confidence bound allocation uses an index that rewards uncertainty; it encourages sampling but is not, simply by being an index policy, a stated minimum-count guarantee. Explore-then-commit guarantees a planned initial sampling phase, after which it stops forcing exploration. A continuing forced schedule instead reserves assignments for exploration throughout the horizon. Each approach makes a different commitment about when exploration happens and what is guaranteed.

A minimum share per treatment should also not be mistaken for a rule that all treatments must receive equal allocation on every round. A quota controls cumulative counts at its specified time or times. It can coexist with unequal allocation on other rounds, and its value depends on the horizon and the schedule. In a clinical trial, the operational value of collecting more information about a treatment must be weighed against assigning participants to treatments with lower estimated mean reward. The quota makes that trade-off explicit; it does not decide its scientific or clinical acceptability.

Diagnostics and Common Pitfalls

A frequent mistake is to claim that a minimum share guarantees a precise comparison between treatments. The quota guarantees assignments, not a particular standard error or the correctness of a ranking. Another mistake is to equate the worst-case regret bound with the realized forced regret. The bound \(F(T)\Delta_{\max}\) is obtained by charging every forced assignment the largest gap; the actual contribution must instead use the counts and gaps of the treatments actually assigned.