SHPRR: An Algorithm for Pure Exploration under Constrained Regret

1 Introduction

• In live deployment, inferior-arm pulls can immediately penalize an operational baseline, making cumulative loss a direct exploration constraint rather than only a post-hoc metric.The paper contrasts this setting with offline evaluation, where sample complexity is the natural cost.Source: §1 · p. 1
• Realized regret differs from generic resource costs because it can be negative when an arm beats the baseline and is coupled to reward, making better arms cheaper to explore.The authors identify these as signed consumption and consumption–reward coupling.Source: §1 · p. 1
• As Sequential Halving prunes suboptimal arms, the surviving set’s average suboptimality gap contracts, so expected regret per pull decreases across phases.The broad early pool makes the initial phases most costly.Source: §1 · pp. 1–2
• SHPRR front-loads regret budget toward early phases in proportion to the active arm count, with α ∈[0, 1] controlling the allocation.α = 0 recovers uniform allocation; α = 1 gives aggressive early-phase prioritization, while budget enforcement is guaranteed.Source: §1 · pp. 1–2
• Across synthetic and real-world benchmarks, SHPRR controls failure probability under bounded regret and matches or outperforms SH-RR, AT-LUCB, and TTSPRT while maintaining robust performance.The paper reports that competing baselines can perform well in some settings but collapse in others.Source: §1 · pp. 1–2

2 Related Work

• Fixed-confidence BAI minimizes pulls while meeting a target identification probability, whereas fixed-budget BAI maximizes correct identification probability under a limited horizon.Identification quality is measured using success probability or simple regret.Source: §2 · p. 2
• Elimination methods discard weaker arms across rounds, while confidence-bound methods guide sampling with estimates and include LUCB, Track-and-Stop, and UGapE variants.The passage also describes lower-bound and asymptotic-optimality results for particular methods.Source: §2 · p. 2
• Top-two methods select between a current best arm and a challenger, using posterior sampling in TTTS or SPRT likelihood-ratio statistics in the related top-two SPRT approach.The cited variants have δ-PAC guarantees; the SPRT approach is described as asymptotically optimal for exponential-family rewards.Source: §2 · p. 2
• Prior constrained BAI studies cover safety, variance, multi-fidelity, cost-aware, and cumulative-regret formulations, with Li and Cheung (2024) closest through SH-RR.SH-RR uniformly rations phase budgets for arm costs; this paper distinguishes regret as signed and reward-coupled.Source: §2 · p. 2

3 Problem Setting

• The setting augments stochastic multi-armed bandits with an exogenous baseline and a realized-regret budget alongside the usual sampling horizon.The objective is to maximize the probability of exactly identifying the best arm subject to both constraints.Source: §3 · p. 2, §3.1 · p. 3

3.1 Bandit Model

• The model assumes finitely many arms with unknown means, rewards bounded in [0, 1], and a unique best arm; ∆i denotes the gap between its mean and arm i’s mean.The baseline is unavailable to pull, its mean is known, and it is assumed weakly dominated by the best available arm.Source: §3.1 · pp. 2–3
• A sequential policy selects arms from observed history, stops at τ, and outputs a recommendation; realized regret is the observed reward’s shortfall relative to the baseline mean.Because regret can be negative, the pull budget T is needed alongside the regret budget to prevent indefinite sampling.Source: §3.1 · p. 3

4 Structural Properties of SH

• Sequential Halving starts with all arms, samples active arms round-robin in phases, and retains the half with the largest empirical means.The analysis assumes K is a power of 2 and a margin of safety to complete the final round-robin cycle, simplifying notation without changing leading-order bounds.Source: §4 · p. 3
• Under nonnegative resource consumption, SH-RR assigns pull and resource quotas by phase, then performs the usual elimination step when either quota binds.This phase-based resource-rationing principle is attributed to Li and Cheung (2024).Source: §4 · p. 3
• Using positive-part regret as consumption gives a conservative feasible benchmark because it dominates signed regret, so respecting its budget also respects the original constraint.The construction applies SH-RR with each arm’s positive-part regret consumption as its resource.Source: §4 · p. 3

T H2,T , B Hsto

• A supplementary phase-wise-estimate variant leaves rationing unchanged and removes the extraneous factor K from the prefactor in (4).Source: T H2,T , B Hsto · p. 3
• A pull can replenish signed regret when its reward exceeds the baseline, but the positive-part reduction assigns such pulls zero consumption and can assign positive expected cost even to arms that replenish in expectation.Source: T H2,T , B Hsto · pp. 3–4
• Generic bounds charge a phase using a worst-case consumption profile for its arm count, whereas signed-regret consumption depends on the surviving set and its average suboptimality.Source: T H2,T , B Hsto · p. 4
• The phase-budget result permits nonuniform allocations, and the declining cost across phases motivates assigning more budget to early phases.Source: T H2,T , B Hsto · p. 4
• The theoretical analysis uses only current-phase observations for elimination, while the experimental algorithm uses all accumulated observations; discarding past data may degrade empirical performance.Source: T H2,T , B Hsto · p. 4
• The analysis shows that surviving-set average gaps improve at a controlled rate, and this phase-wise improvement yields a misidentification-probability bound.Source: T H2,T , B Hsto · p. 4
• The theorem captures declining exploration costs through phase-specific quality scales, but does not fully characterize intrinsic complexity because negative regret complicates lower bounds.Source: T H2,T , B Hsto · p. 4

5 SHPRR Algorithm

• The appropriate degree of front-loading depends on the instance, including how quickly survivors improve and how costly the initial pool is.Too little early spending can leave costly arms in later phases; too much can leave insufficient reserve for closely matched finalists.Source: §5 · p. 4
• SHPRR allocates each phase’s regret budget in proportion to the number of remaining arms raised to α, favoring earlier phases as α increases.At α = 0, allocation is uniform; at α = 1, it is proportional to the number of arms remaining.Source: §5 · pp. 4–5
• Each phase samples active arms in round-robin order until either its regret budget or its pull allowance is exhausted.The total pull budget is initially divided uniformly across phases.Source: §5 · p. 5
• After sampling, SHPRR advances the top half of active arms by empirical mean, computed from the full pull history.The procedure runs for ⌈log2 K⌉ phases and returns the final survivor with the highest empirical mean.Source: §5 · p. 5
• Unused or replenished regret and unused pulls carry into the next phase, preserving resources for later discriminations.Fresh regret allocation is sized to the new active-arm count, while fresh pull allocations are uniform.Source: §5 · p. 5

6 Experiments

• The experiments are organized around a performance overview, sensitivity analyses of reward gaps and baseline-budget choices, and phase-wise arm composition.Figure 1 reports SP and NSR across synthetic and real-world environments.Source: §6 · p. 5, Figure 1 · p. 6

6.1 Experimental Design

• The evaluation covers four synthetic Bernoulli-arm environments and New Yorker Caption Contest and Criteo datasets, using SP and normalized simple regret as outcomes.The study varies the optimal–suboptimal gap and baseline-arm choice, and compares SHPRR with SH-RR, TTSPRT, and AT-LUCB under budget stopping rules.Source: §6.1 · pp. 5–6

6.2 Performance Overview

• SHPRR is best or near-best across environments with nontrivial consumption structure, while a fixed α = 0.5 strongly outperforms every benchmark in all but one environment.In Trap, SHPRR (α = 0.9) reaches SP 0.93 versus 0.528 for SH-RR and 0.462 for AT-LUCB; OneSub is the exception, where AT-LUCB reaches SP 0.998.Source: §6.2 · p. 6

6.3 Sensitivity Analysis

• As δ approaches 0, SHPRR degrades more gracefully than the benchmarks; in Trap, SHPRR (α = 0.9) stays above 0.93 while TTSPRT falls to 0.034.OneSub is the exception, with all methods near ceiling regardless of δ.Source: Gap Magnitude · pp. 6–7
• Across best-arm, top 1%, and top 5% baselines, SHPRR remains strong across regret budgets; at the largest budget it reaches SP 0.77 under the best-arm baseline.With top-quantile baselines, SHPRR (α = 0.5, 0.9) reaches the highest SP (0.77) and uses a smaller budget fraction than TTSPRT and AT-LUCB.Source: Baseline Arm and Regret Budget · p. 7, Figure 3 · p. 7

6.4 Per Phase Arm Composition

• At every displayed phase, increasing α significantly raises the mean reward of surviving arms relative to α = 0.0, with the largest effect in early phases.At phase 9, α = 0.8 has the highest mean reward; the variants converge toward high-reward arms by the end.Source: §6.4 · p. 7, Figure 4 · p. 7

• SHPRR front-loads a tunable regret budget and is reported as the only method robust across all synthetic and real-world environments, with α = 0.5 a strong default.Source: §7 · p. 7
• The per-pull price of information declines across Sequential Halving phases, making early-phase exploration the most expensive in regret.Source: §7 · p. 7
• The paper defines BAI under a realized regret budget, measuring experimentation cost relative to a baseline through signed, reward-coupled, replenishable consumption.Source: §7 · p. 7

1 Sharpening the results of the paper Li and Cheung (2024)

• The analysis uses a phase-wise-estimate SH-RR variant with current-phase empirical means, preserving the rationing mechanism and enabling standard Sequential Halving arguments.The passage notes that this modification need not improve practical performance.Source: §1 · p. 9
• The general resource-constraint guarantees assume rewards in [0, 1], a stronger condition than the 1-subgaussian assumption in Li and Cheung (2024).The passage says this stronger assumption is needed when regret is a resource; without regret resources, a modified concentration constant can recover the same bound for 1-subgaussian rewards.Source: §1 · p. 9

1.1 The deterministic consumption bound

• The deterministic-consumption analysis sharpens the number-of-arms prefactor in Li and Cheung (2024) from K log2(K) to log2(K).Source: §1.1 · p. 9

1.2 Stochastic consumption setting

• For stochastic consumption, the section gives an SH-RR best-arm identification failure-probability guarantee and uses aggregate phase-consumption concentration to avoid an armwise union bound.Source: §1 · p. 9, §1.2 · p. 11

2 Proof of the main Theorem

• Conditional on arm-quality event Aq, the phase completes at least τq cycles with high probability; fewer cycles occur only if regret budget B(q) is exhausted early by upward deviations of realized consumption above expectation.The probability of this early exhaustion decays exponentially in τq∆2.Source: §2 · p. 16

2.1 Proof of Proposition 2.1

• Proposition 2.1 propagates good-arm conservation until survivors become sufficiently concentrated, then carries that concentration through later phases to establish Aq with high probability.The proof chains conservation, a transition to the concentrated regime, and subsequent propagation across phases.Source: §2.1 · pp. 17–19

2.2 Proof of the propositions

• The proposition proofs use maximal Azuma–Hoeffding control for phase regret and anytime bounds for retaining good arms and tracking the true top arms after empirical selection.The helper results include a specialized anytime selection bound and an anytime bound on top-arms mean decay.Source: §2.2 · pp. 20–21

2.3 Proof of the Helper Lemmas

• The helper-lemma proof bounds failures of empirical top-half selection by relating excluded arms to included arms whose empirical means exceed theirs.It first counts excluded good arms and then considers pairs of excluded and included arms under the top-half selection rule.Source: §2.3 · pp. 23–24
• The helper-lemma proof combines Claim 2.2 and anytime concentration inequalities, then union-bounds over possible arm sets A and B.The events concern empirical means deviating from the corresponding arm means by d_ℓ at times t ≥ τ.Source: §2.3 · p. 24
• The proof uses B_s being the set with the largest empirical means, together with the selection of arms in V(t) and non-selection of arms in U(t), to derive an intermediate relation.Source: §2.3 · p. 25
• It extends the fixed-set claim by taking a union bound over all deterministic sets T.Source: §2.3 · p. 25
• For a fixed set T, the proof sets ℓ = s − |B_s ∩ T| and applies Claim 2.2 with m = 2ℓτ and a = sϵ; the claim follows from ℓ ≤ s.Source: §2.3 · p. 25

• OneSub gives all suboptimal arms mean 0.8, Trap combines near-optimal arms with many low-reward arms, and Geom decays geometrically from 0.9 to 0.1.Source: §3 · p. 26
• The New Yorker data uses three caption contests with binary human-vote rewards, top-1% baseline arms, regret budgets of 1.6 times the arm count, and 500 seeds.The contests contain approximately 3,000–6,000 arms each, with a 100,000-pull maximum.Source: §3 · p. 26
• Figure 3 depicts phase-wise arm quality under a polynomial reward family for β ∈ {0.25, 0.5, 0.75, 1.0}.Source: Figure 3 · p. 27
• Criteo campaigns are treated as arms; evaluation varies the baseline among the top 5%, top 1%, and best arm and sweeps regret budgets from 0.06 to 1.8 times the arm count.The dataset uses campaign-level aggregation and filters campaigns with insufficient impression volume.Source: §3 · pp. 26–27

4 Per-Phase Arm Composition across Polynomial Reward Structures

• The analysis tests whether rationing’s effect on arm quality persists across polynomial reward structures of differing steepness.Source: §4 · p. 27
• Reward profiles with β ∈ {0.25, 0.5, 0.75, 1.0} vary in decay steepness, with larger β producing a gentler decay and more near-optimal arms.The profiles use rewards following µ_i = 0.9 · (1 − (i/n)^β).Source: §4 · p. 27
• Across displayed phases, boxplots show surviving-arm mean rewards over 500 seeds for SHPRR variants with α ∈ {0.0, 0.2, 0.8, 1.0}, using α = 0.0 as the paired-test reference.Boxes span the interquartile range, white bars mark medians, significant paired t-test comparisons are bracketed, and a star marks the highest-mean variant at each phase.Source: §4 · p. 27