Source-linked AI summary
Batched bandit problems
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg
TL;DR
The paper asks how much regret stochastic bandits incur when clinical trials must be divided into only a few batches. It develops explore-then-commit policies with carefully chosen grids and shows that very small batch counts can attain near-optimal regret while also reducing switching. The analysis includes lower bounds and simulations, including settings with five batches.
Problem
The paper studies stochastic bandit regret when policies may update decisions only across a small number of batches, as required in clinical trials.
Method
It develops explore-then-commit policies that test for a dominant arm after nonterminal batches and choose batch grids to control regret across gap values.
Results
M = Θ(log log T) batches suffice for the optimal minimax rate, while adaptive optimal bounds use M = Θ(log(T/log(T))) batches.
Takeaways & Limitations
Near-optimal regret can be achieved with batch counts feasible for clinical settings, and the corresponding policies require few arm switches.
Takeaways & Limitations
The formal framework assumes two arms and standardized sub-Gaussian rewards, with extensions to more arms described as mostly technical.
Abstract
from arXiv · showhide
Motivated by practical applications, chiefly clinical trials, we study the regret achievable for stochastic bandits under the constraint that the employed policy must split trials into a small number of batches. We propose a simple policy, and show that a very small number of batches gives close to minimax optimal regret bounds. As a byproduct, we derive optimal policies with low switching cost for stochastic bandits.
1. Introduction.
Clinical trials naturally operate in batches because outcomes cannot be measured patient by patient, yet the statistical implications of few batches remain underexplored. The paper studies how to choose batch sizes and update decisions while retaining near-optimal regret.
- Motivation: Clinical trials treat groups of patients simultaneously, using each batch’s data to design the next.This batching is practical because patient outcomes are unavailable quickly enough for sequential decisions.
- Bandit formulation: The bandit formulation captures the ethical tradeoff between exploring treatment efficacy and exploiting the best treatment.A policy chooses among treatment arms to maximize expected cumulative reward over T rounds.
- Broader relevance: Batching also matters in internet advertising and other applications, where technical constraints often require grouped data decisions.In advertising, batch sizes are commonly chosen for technical convenience rather than statistical reasoning.
- Clinical-trial structure: Clinical practice may use formal approval phases or informal pilot-to-diffusion stages, contrasting with the single-patient batches of the basic bandit problem.Early stages generally emphasize exploration, while the final stage emphasizes exploitation.
- Contribution: A proposed policy achieves minimax regret bounds as low as those of the best non-batched algorithms with a small fixed number of batches.The batch sizes also perform well empirically, suggesting near-optimal policies may require only small changes to clinical practice.
2. Description of the problem.
The paper formalizes two-armed stochastic bandits in which decisions can use only data from completed batches, then develops explore-then-commit policies and analyzes their regret. It targets the practically important regime of very few batches, where existing optimal procedures generally require more frequent updating.
- Problem setup: The framework uses a two-armed bandit with unknown standardized sub-Gaussian reward distributions and a finite horizon T.An M-batch policy partitions the horizon into batches and fixes within-batch actions using only earlier-batch observations.
- Problem setup: Regret measures the expected loss from pulling the suboptimal arm, equivalently the gap Δ times its expected number of pulls.The optimal arm has the larger expected reward, and Δ denotes the difference between the two arm means.
- Prior results and gap: Existing fully sequential policies achieve adaptive regret, while optimal minimax regret is known with M = Θ(log log T) batches up to logarithmic factors.The paper focuses on smaller constant values such as 2, 3, or 4 batches, which arise in clinical practice.
- Prior results and gap: Earlier two-batch Gaussian work established T^2/3 regret for explore-then-commit policies, which this paper recovers and extends.Related Bayesian work commonly studies two or three batches and often selects a first batch of order √T, up to logarithmic factors.
- Policy class: The paper introduces explore-then-commit policies that explore equally within nonterminal batches, test for dominance, and commit once one arm dominates.If no arm dominates before the terminal batch, the policy commits to the arm with the largest past average reward.
- Results: Two instantiations provide adaptive and minimax regret bounds, respectively, with explicit dependence on the number of batches.The paper also proves lower bounds showing these policies are optimal within the M-batch class up to logarithmic terms and evaluates them in simulations.
3. Explore-then-commit policies.
Explore-then-commit policies repeatedly test whether one arm dominates while allocating equal pulls across non-terminal batches, then commit to a selected arm. Their behavior is determined by the testing criterion and batch grid, with regret controlled by how the grid aligns with the time needed to identify the better arm.
- Policy structure: Explore-then-commit policies pull each arm equally in non-terminal batches and test whether one arm dominates before committing.If no arm is declared dominant by the terminal batch, the policy selects the arm with the largest average past reward.
- Policy structure: The policy class is completely characterized by its testing criterion and batch sizes.
- Statistical test: The statistical tests return arm 1, arm 2, or an inconclusive outcome, and are implemented at times when both arms have been pulled equally often.The empirical means and confidence bounds support these tests.
- Grid and batch timing: A deterministic grid restricts when past observations can be inspected, so the relevant batch time is the first grid point after the test’s theoretical identification time.The grid is fixed beforehand, and unresolved decisions continue with equal sampling in the next batch.
- Regret analysis: Regret arises from exploration, selecting the wrong arm before the identification time, or failing to commit at that time.Exploration contributes an additional term t̄_m∆/2, while the other errors must be made unlikely.
- Regret analysis: 9∆t̄_m bounds regret when the relevant grid point occurs before the final testing time.When the relevant point is the final grid time, the analysis instead uses the go-for-broke test’s error probability.
4. Functionals, grids and bounds.
The paper studies how grid choices shape regret for explore-then-commit policies under a small batch budget. Arithmetic grids are poor with few batches, while geometric and minimax grids recover strong bounds with substantially fewer batches.
- Grid design: For fixed Δ, choosing M = 2 and t1 ≃ τ(Δ) yields optimal regret R∗(Δ) = log(TΔ^2)/Δ.When Δ is unknown, no single grid uniformly optimizes regret across all gaps.
- Arithmetic grid: The arithmetic grid recovers the optimal rate only when M = T, while constant M gives excess regret of order ΔT for large T.Its excess-regret bound is optimal up to logarithmic factors, but offers little guidance for small M.
- Geometric grid: For M = Θ(log T), the geometric grid achieves the optimal regret bound.Its deterioration for smaller M is characterized by a factor (T/log(T))^1/M, interpreted as a uniform competitive-ratio bound.
- Minimax grid: The minimax grid recursively selects batch times so that the key term Δf(τ(Δ)) is constant across gaps.This design targets maximum risk rather than a gap-specific criterion.
- Minimax grid: ⌊log2 log(T)⌋ batches suffice to obtain the optimal minimax rate, and additional batches can be implicitly combined.The resulting bound is stated for M ≥ log2 log(T).
- Switching cost: The minimax-grid policy can be adapted to use only O(log log T) switches while retaining regret of optimal order.Within each batch, it switches at most once before committing to one arm.
5. Lower bounds.
The paper proves lower bounds for arbitrary M-batch policies, not only for its explore-then-commit constructions. These bounds establish near-optimality of the proposed policies for several regret criteria.
- Scope: The lower-bound analysis applies to all M-batch policies, beyond the class of explore-then-commit policies.It targets the functionals Fxs, Fcr and Fmx.
- Regret criteria: The lower bounds are obtained by analyzing excess risk, competitive ratio, and maximum risk separately.The excess-risk argument uses an arithmetic spacing of batch times, while analogous arguments yield the competitive-ratio bound.
6. Simulations.
Simulations compare batched policies across standard reward distributions and clinical-trial timing. The minimax grid performs well with few batches, while Ucb2 often trades lower regret for many more batches.
- Clinical timing: A six-month STI follow-up would take 1.5 years with minimax batch sizes but 28 years with Ucb2’s 56 batches.The example illustrates why low regret with few batches matters for medical trials with delayed outcomes.
- Experimental setup: The simulations compare policies over Gaussian, Student’s t, Bernoulli, and Poisson distributions, generally using M = 5 and Δ = 0.1.For each T, the experiment repeats grid construction and policy evaluation 100 times.
- Observed patterns: The arithmetic grid produces nearly constant average regret once T is sufficiently large.The first batch becomes a constant fraction of the participant pool, and the policy tends to commit after that batch.
- Observed patterns: The minimax grid achieves lower regret than arithmetic or geometric grids when M is small.Its batch sizes allow commitment closer to the theoretical decision time τ(Δ).
- Comparison with Ucb2: The minimax grid can outperform Ucb2 while using an order of magnitude fewer batches.For Gaussian draws with T between 10,000 and 40,000, five minimax-grid batches outperform Ucb2, which uses roughly 50.
- Comparison with Ucb2: Ucb2 generally has lower regret except for heavy-tailed Student’s t rewards, where batched policies perform significantly better.The comparison reflects Ucb2’s sub-Gaussian calibration and the averaging effect of batching.
APPENDIX A: TOOLS FOR LOWER BOUNDS
The appendix derives lower bounds by reducing arm selection to hypothesis testing. It relates policy errors to regret and controls distinguishability through the information accumulated across batches.
- Testing reduction: The proof considers two reward setups in which the identity of the optimal arm is reversed between P1 and P2.Under P1, arm 1 has mean Δ and arm 2 mean 0; under P2, the assignments are reversed.
- Testing reduction: At time t, choosing an arm is treated as a statistical test between the observation distributions P1^t and P2^t.An incorrect choice incurs instantaneous regret Δ.
- Information bound: The analysis uses a change-of-measure lemma involving Kullback–Leibler divergence to relate testing errors under P1 and P2.The appendix introduces KL divergence before applying the resulting inequality to batched observations.
- Batched information: For an M-batch policy, the observations available at time t depend on the current batch index J(t) and the previously selected arms.This structure determines the distributions used in the testing argument.
- Lower-bound proposition: Proposition A.1 supplies regret lower bounds for some reward distributions with gap Δ on any fixed batch grid.The proposition is then used to establish several lower bounds in Section 5.
APPENDIX B: TECHNICAL LEMMAS
Appendix B develops technical lemmas for sub-Gaussian martingale differences and auxiliary sequences. The proofs use Chernoff, Jensen, Doob maximal, optimization, peeling, induction, and parameter conditions to establish the stated inequalities.
- Sub-Gaussian martingale bounds: Lemma B.1 treats sub-Gaussian martingale differences and derives a time-uniform bound using exponential submartingales and Doob’s maximal inequality.The argument combines Jensen’s inequality with the sub-Gaussian moment bound, optimizes over α > 0, and then applies a peeling argument.
- Parameter inequalities: Lemma B.2 assumes positive integers T and M ≤ log(T) and proves its inequality by reparameterizing with x := T∆2/32 and θ := aM−1/T.The proof uses the implication M ≤ log T ⇒ a ≥ e and reduces the first inequality to a condition in x and θ.
- Parameter inequalities: The auxiliary inequality (7) is verified over separate intervals, including (0,e], [e,a∗], and a further range controlled by θ and a.The proof uses log(x) = a ≥ e, the bound xe−θx ≤ 1/(θe), and a derivative comparison to extend validity across the required ranges.
- Auxiliary sequence bounds: Lemma B.3 defines a recursively generated sequence beginning with u1 = a and establishes bounds under 15aSM−2 ≤ b.Its proof introduces zk = log(b/aSk), relates successive z-values to aSk+2 ≤ b, and uses induction for the final indices.
- Proof conclusions: The remaining technical inequalities follow from Chernoff bounds, induction, and conditions such as 2M ≤ log(4T) or 2M ≤ log(2T)/6.These conditions yield the final bound involving (2T)21−M.