Batch Bandit Policies for Group Enrollment

Why Update Between Groups?

In an individually updated bandit policy, an outcome can affect the allocation of the next patient once that outcome is observed. Group enrollment changes this timing. If patients are enrolled in cohorts, or if allocations must be prepared before a group starts, the policy may have to hold its allocation rule fixed until the group’s outcomes are available. The policy then uses older information for some assignments, even when outcomes arrive during enrollment.

The key design choice is therefore not only which treatment-allocation rule to use, but also when the rule is allowed to change. A batch policy makes an allocation decision at each group boundary using the data available then, and does not use outcomes from that group to revise assignments within the same group. This is a formulation of timing, not a guarantee that a particular treatment will be selected or that the trial will be statistically valid for every clinical objective.

Formalizing the Timing and Allocation

Suppose there are \(K\) treatments, called arms. Let \(Y_{ij}\) be the reward for the \(j\)th patient assigned to arm \(i\), and suppose for the basic bandit formulation that outcomes on arm \(i\) have a stable mean \(\mu_i\). A common model for binary benefit is \(Y_{ij}\sim\mathrm{Bernoulli}(\mu_i)\), with outcomes independent across patients conditional on their assigned arms. The Bernoulli model assumes the same success probability for every patient assigned to a given arm; it does not include changing patient mix, calendar-time trends, or treatment-by-covariate variation.

At the start of batch \(m\), let \(\mathcal{H}_{m-1}\) denote the assignments and outcomes available from completed batches. The policy maps this history to an allocation vector \(q_m=(q_{m1},\ldots,q_{mK})\), where \(q_{mi}\geq 0\) and \(\sum_{i=1}^{K}q_{mi}=1\). One implementation assigns each patient in the batch independently to arm \(i\) with probability \(q_{mi}\). Another chooses one arm and assigns all patients in the batch to that arm. Both are batch policies; they have different within-batch allocation variation.

The vector \(q_m\) is fixed for the batch. Under independent random assignment with this vector, the realized number assigned to arm \(i\) need not equal \(b_mq_{mi}\), although that is its conditional expectation. Under an all-to-one-arm policy, \(q_m\) has one component equal to 1 and all others equal to 0. In either case, outcomes from batch \(m\) enter the history only after they are observed and made available for the next decision.

For an index policy such as UCB, a convenient batch implementation calculates each arm’s index at the start of the batch and holds those indices fixed during enrollment of that batch. If one arm with the largest index is selected for all assignments, the policy is deterministic within the batch apart from any rule for ties. A randomized variant can instead use the frozen indices to set a batch allocation vector. This tutorial’s calculations use the all-to-one-arm version when illustrating UCB.

Expected Regret for a Batch

Let \(\mu^*=\max_i\mu_i\), and define the reward gap for arm \(i\) as \(\Delta_i=\mu^*-\mu_i\). The gap is nonnegative and is measured in reward units per patient. Regret compares the expected reward under the policy with the expected reward from assigning every patient to an arm with mean \(\mu^*\). It is a reward criterion, not a statement that the best-mean arm is necessarily the clinically preferred treatment once safety, uncertainty, and other objectives are considered.

Under the stable-mean model, conditional on the history before batch \(m\) and on its allocation probabilities \(q_m\), each patient has expected reward \(\sum_i q_{mi}\mu_i\). The best-arm benchmark has expected reward \(\mu^*\) per patient. Subtracting gives the following conditional expected regret for the batch:

The second equality follows because \(\sum_i q_{mi}=1\): \(\mu^*=\sum_iq_{mi}\mu^*\), so subtracting the weighted means yields \(\sum_iq_{mi}(\mu^*-\mu_i)\). Adding the conditional batch contributions over enrollment gives cumulative expected regret. The allocation probabilities may depend on earlier data, so an unconditional expected regret averages these conditional contributions over the histories generated by the policy.

Batch-UCB: Freeze the Index Until the Next Boundary

The earlier material on upper confidence bound allocation defines indices that combine an estimated mean with an exploration bonus. In a batch implementation, calculate those indices from completed, available data at the boundary, then hold the resulting choice for the batch. For a two-arm Bernoulli illustration with \(N_i>0\) observed outcomes on arm \(i\), \(\hat p_i\) the observed success proportion, and \(n\) total completed assignments, use the illustrative index \(U_i(n)=\hat p_i+\sqrt{2\log(n)/N_i}\). The formula is meaningful here only after each arm has observations; an initial allocation must ensure this, or an explicit rule must handle an unobserved arm. The indices are not constrained to the interval from 0 to 1, since they are upper confidence scores rather than predicted probabilities.

Batch Size and the Cost of Delayed Adaptation

A larger batch reduces how often allocation decisions must be prepared, but it also keeps the policy from responding to new information for longer. If a batch policy chooses a single suboptimal arm \(i\) for \(b_m\) patients, its conditional expected regret for that batch is \(b_m\Delta_i\). With an allocation vector spread across arms, the corresponding cost is \(b_m\sum_iq_{mi}\Delta_i\). Thus, for a fixed allocation decision, doubling the batch size doubles that batch’s expected regret under the stationary-mean model.

Assumptions, Diagnostics, and Alternatives

The basic calculations require a clearly defined reward, stable arm means over the period being modeled, and outcomes whose distributions are adequately represented by the chosen model. The Bernoulli version additionally requires a binary outcome and a common success probability within each arm. Assignments must follow the stated allocation rule, and each update must use only outcomes actually available at that decision time. If follow-up completion differs across patients, the rule should specify whether an update waits for the whole batch or uses the subset of outcomes available; those are different policies and may produce different allocations.

Several diagnostics help reveal when the intended policy and the implemented trial have diverged:

• Audit decision times. Record the data cutoff and allocation rule used for every batch. Check that no outcome from the current batch affected its own assignments.
• Compare planned and realized counts. For probabilistic allocation, counts vary randomly around their expected values. Persistent deviations beyond ordinary random variation may indicate an implementation or logging error.
• Inspect information by arm. Very few observations on an arm can make estimates unstable. The earlier material on forced exploration and minimum sampling rates addresses a separate design choice about maintaining exploration; batching alone does not guarantee adequate sampling.
• Check outcome availability and calendar time. A long delay or a changing patient population can make older outcomes less relevant to current assignments. A stationary-mean model does not automatically adjust for time trends or case-mix changes.
• Review clinical outcomes beyond reward. A reward-maximizing allocation rule does not, by itself, provide a safety constraint, preserve a desired allocation share, or settle the trial’s inferential goals.

Individual updating can react sooner to available outcomes, but may require reliable real-time data processing and patient-by-patient allocation. Fixed allocation does not adapt to observed outcomes, but has a simple, prespecified structure and avoids policy changes driven by interim reward estimates. Batch allocation is between these alternatives: it supports adaptation while reducing the frequency of decisions, at the cost of stale information within each group. There is no universally optimal batch size without specifying the enrollment schedule, outcome delays, operational constraints, reward objective, and acceptable inferential properties.