Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

• The objective is terminal posterior certification that a recommended design’s mean exceeds a prespecified target, unlike best-arm identification’s goal of finding the largest-mean design.Source: §1 · p. 1
• The objective differs from Bayesian satisficing regret and exploration–validation formulations because it evaluates a fixed-budget terminal certificate using all observations, without a separate validation test.Source: §1 · p. 2
• HTG combines a large initial balanced allocation, successive halving, and a final posterior-greedy phase to exploit both easily screened unfavorable arms and multiple favorable arms.Source: §1 · p. 2
• The paper proves instance-dependent finite-budget exponential posterior-failure bounds and shows that, on one-positive-arm families, HTG matches an asymptotic sample-complexity lower bound up to a logarithmic factor in the number of arms.Source: §1 · p. 2
• Uniform sampling and sequential halving can require Ω(K) and Ω(log K) times as many samples as HTG, respectively, on the analyzed instance family.Source: §1 · p. 2

• The model uses K arm means drawn independently from a common Gaussian prior, and observations are independent across arms and samples conditional on the true means.Source: §2 · p. 2
• The stated performance guarantees fix the true mean vector and evaluate probability over observation noise and algorithm randomization, despite using the Gaussian prior to form posterior beliefs.Source: §2 · p. 2
• A general target threshold τ is reduced to zero by subtracting τ from observations, arm means, and the prior mean.Source: §2 · p. 2
• Posterior success requires the recommended arm’s terminal posterior probability of exceeding the target to be at least 1−δ, but does not require its true mean to be positive.Source: §2 · p. 2
• For a fixed mean vector, the algorithm’s finite-budget failure probability is evaluated over observation noise and any algorithm randomization, with the goal of making it decrease rapidly as the budget grows.Source: §2 · p. 2

• The posterior quantities used by HTG are defined using the standard normal cumulative distribution function, the prior-to-observation variance ratio λ, and z=Φ^-1(1−δ).Source: §3 · pp. 2–3
• The algorithm uses round-robin sampling when T is below Tcut, defined as 3K max{nλ, Q}, and otherwise proceeds through halving followed by greedy sampling.Source: §3 · p. 3
• The two phases update each arm’s posterior using all its observations; eliminated arms remain eligible for greedy sampling and final recommendation.Source: §3 · p. 3
• HTG recommends the arm with the largest posterior Z-score, which maximizes the posterior probability that the selected arm has positive mean.Source: §3 · p. 3
• A deliberately large initial balanced batch gives every arm broad coverage and nontrivial evidence before adaptive allocation, helping HTG exploit instances with several positive means.Source: §3 · p. 3
• During successive halving, HTG allocates observations to increasingly promising active arms and retains those with the largest posterior Z-scores, equivalent to ranking by empirical means when active arms have equal sample counts and common prior parameters.Source: §3 · p. 3
• At least T/3 observations remain for posterior-greedy sampling, which chooses among all original arms by current posterior probability of positive mean.Source: §3 · p. 3
• Balanced allocation, progressive screening, and greedy concentration jointly let HTG adapt to multiple positive arms and quickly separable unfavorable arms.Source: §3 · pp. 3–4

4.1 Certification complexities

• Hcap captures the cost of distinguishing promising arms from unfavorable ones, while Hpos reflects the benefit of having multiple positive arms that could provide a certificate.Neither complexity uniformly dominates the other, so their minimum captures distinct favorable instance structures.Source: §4.1 · p. 4
• The finite-budget analysis defines HHTG as a related complexity, and Lemma 1 compares it with the simpler certification complexity Hcert for mean vectors with µ⋆ > 0.The terms in (8) correspond to guarantees from posterior-greedy sampling, the initial allocation, and successive halving.Source: §4.1 · p. 4

4.2 Finite-budget posterior certification

• After the offset T0, HTG’s posterior-failure probability decreases exponentially at a rate governed by HHTG(µ), which is within a factor Q = O(log K) of Hcert(µ).T0 accounts for the initial allocation, the prior mean, and additional samples needed to reach the prescribed posterior credibility level.Source: §4.2 · p. 5

4.3 Interpretation and proof ideas

• On the one-positive-arm example with other arms strongly negative, HHTG lies between σ2/a2 and 2σ2/a2, and its complexity can be a factor of order K smaller than Hpos.The posterior-greedy term is at most 2σ2/a2, compared with Qσ2/a2 for the successive-halving term.Source: §4.3 · p. 5
• When all K arms have the same positive mean a, HHTG is a factor K smaller than Hcap, although the sufficient-budget offset includes a term proportional to K.Any positive arm can provide the required certificate in this example; the offset is T0 = Tcut + 96Kc2σ2/a2.Source: §4.3 · p. 5
• The final posterior-greedy phase and successive-halving phase yield separate budget-counting arguments for the first and third terms in (8), respectively.The proof starts from a concentration event holding simultaneously over arms and sample counts.Source: §4.3 · p. 5
• The initial allocation gives every arm at least q1 = ⌊T/(3K)⌋ samples, enabling the guarantee to account for the possibility of several positive arms.The proof bounds failure events for each positive arm and multiplies their probabilities using the independence of the arms’ observation sequences.Source: §4.3 · p. 5

5.1 Families with one positive arm

• The one-positive-arm family varies the location of the arm with mean ∆, while each other arm has mean −εi, which need not be equal across arms.The family parameters and model parameters are held fixed as T tends to infinity.Source: §5.1 · p. 6
• The lower-bound quantities h and S capture, respectively, the complexity of certifying a known positive-arm location and uncertainty over which arm is positive.Each term in S uses the difference ∆ + εi between arm i’s possible means ∆ and −εi.Source: §5.1 · p. 6

5.2 An asymptotic lower bound

• For each fixed profile (∆, ε), Theorem 2 bounds the asymptotic exponent of any admissible algorithm’s worst-case posterior-failure probability.The instance attaining the worst-case failure probability may depend on both the algorithm and the budget T.Source: §5.2 · p. 6
• The lower-bound argument combines bounds involving 1/(2S) and 1/(2h) to obtain the stated bound on the failure exponent.For the h term, changing the positive mean ∆ to −β and then letting β decrease to zero yields 1/(2h).Source: §5.2 · pp. 6–7

5.3 Comparison with the upper bound

• On one-positive-arm families, HTG’s asymptotic sample complexity is within an O(log K) factor of the lower bound.The lower-bound complexity and Hcert agree up to universal constants on this class.Source: §5 · pp. 5–6, §5.3 · p. 7
• When all arms have the same positive mean, every admissible algorithm has exact asymptotic posterior-failure exponent 1/(2Hpos(µ)), with K and model parameters fixed.This is the many-positive-arm case analyzed as a complement to the one-positive-arm families.Source: §5.3 · p. 7

Uniform sampling.

• Uniform sampling allocates observations round-robin, while sequential halving divides the budget across elimination stages and retains arms with the highest posterior Z-scores.With equal cumulative samples among active arms, sequential halving’s ranking is equivalent to ranking by empirical means.Source: Uniform sampling · p. 7
• Uniform sampling’s exact failure exponent reflects multiple positive arms through Hpos, but it cannot redirect observations away from unfavorable arms.Sequential halving also has a finite-budget guarantee for posterior success, with a leading instance-dependent complexity.Source: Uniform sampling · p. 7

6.1 Uniform sampling and sequential halving

• At the level of leading instance-dependent complexities, HTG is no larger than uniform sampling or sequential halving and can be strictly smaller through adaptive allocation.The comparison concerns the complexities in the methods’ guarantees.Source: Uniform sampling · p. 8

6.2 Frequentist interpretation

• In the flat-prior limit, the posterior probability that an arm’s mean is positive equals one minus its one-sided Gaussian p-value for a fixed arm and deterministic sample count.HTG’s halving, greedy, and terminal-selection steps then respectively retain, sample, and recommend arms with the smallest current p-values.Source: §6.2 · p. 8

Experiments and Discussion

• The simulations use K=32, known variance σ²=1, a N(0,1) working prior, δ=0.01, and budgets from 576 to 65,536.They estimate posterior-success probability using 10,000 repetitions per instance and budget, with success assessed after exactly T samples.Source: §7 · p. 8
• Increasing negative-arm separation substantially benefits HTG and makes its advantage over both baselines more pronounced.Figure 1’s left column varies b from 0.02 to 1 while keeping one arm positive; error bars are pointwise 95% Wilson Monte Carlo intervals from 10,000 repetitions.Source: §7 · p. 8, Figure 1 · p. 8
• With multiple positive arms, the experiments illustrate the multiple-opportunity effect: more favorable arms provide more chances to obtain a posterior certificate.Figure 1’s right column compares m=4 and m=16 positive arms, with remaining means −1.Source: §7 · p. 8, Figure 1 · p. 8
• On the reported instance family, uniform sampling and sequential halving require Ω(K) and Ω(log K) times as many samples as HTG, respectively.Empirical scalings with K are consistent with the theoretical rates established on this family.Source: §7 · p. 8
• The conclusion identifies certification relative to an unknown shared control mean as an extension, with a tradeoff between learning that mean and gathering evidence for candidate arms.HTG’s finite-budget failure bound has complexity within O(log K) of Hcert, and its asymptotic sample complexity matches the lower bound up to a logarithmic factor on one-positive-arm families.Source: §7 · pp. 8–9

A Related Work

• Unlike objectives defined by true-mean correctness, posterior success asks whether the terminal recommendation meets a posterior-evidence criterion; it neither requires the best arm nor treats abstention as a separately budgeted outcome.The discussion also distinguishes this fixed-budget terminal criterion from cumulative satisficing regret and separate exploration-validation procedures.Source: A Related Work · pp. 12–13

B Gaussian posterior calculations

• For an arm observed n times, the posterior update is proportional to its prior density times the likelihood of its observed rewards, with Bayes’ rule used to obtain the update.The derivation collects the terms that depend on the arm’s mean.Source: B Gaussian posterior calculations · p. 13

C Proof of the Complexity Comparison

• The complexity comparison establishes Hcert≤Hthr, Hcert≤Hpos, and Hcert≤QH2,cap.The proof defines HHTG as min{Hthr, Hpos, QH2,cap} and Hcert as min{Hcap, Hpos}.Source: C Proof of the Complexity Comparison · pp. 13–14

D Proof of the Finite-Budget Guarantee for HTG

• Combining instance-dependent bounds yields the finite-budget guarantee using h = min{Hthr, Hpos, QH2,cap}.The proof derives separate greedy-phase and halving-phase bounds, including T ≤ 24Hthr(R + c)^2 and T ≤ 48QH2,cap(R + c)^2.Source: D Proof of the Finite-Budget Guarantee… · pp. 16–19

E An Explicit Sufficient Budget

• Corollary 1 gives an explicit sufficient budget Tη for target failure probability η, removing T from the theorem’s logarithmic condition.It applies under Theorem 1’s assumptions for every integer T ≥ Tη.Source: E An Explicit Sufficient Budget · p. 19

F.1 One positive arm with other arms strongly negative

• On the one-positive-arm, strongly-negative family, Hcert and HHTG are within a factor of two of σ^2/a^2, while the greedy phase avoids the halving term’s factor Q.The calculation gives Hthr < 2h, whereas the halving analysis contributes Qh.Source: §F.1 · p. 21

F.2 Many positive arms

• When all K arms have mean a > 0, Hcap = Kh while Hpos = Hcert = h, making HHTG a factor K smaller than Hcap.Although HHTG = h is independent of K for fixed a and σ, the offset grows with K, so the example does not give a K-independent sufficient budget.Source: §F.2 · p. 21

F.3 A competing arm with mean close to zero

• With a competing arm of mean −ε, Hcert stays bounded as ε approaches zero, but Hthr diverges and equals +∞ at ε = 0.For ε ≤ a/K, Hthr ≥ Kh; the halving term gives a smaller bound when K is sufficiently large.Source: §F.3 · pp. 21–22
• As ε ↓ 0, HHTG ≤ 2Qh and T0 ≤ Tcut + 192Qc2h, so neither HTG complexity nor offset diverges.The competing arm’s mean approaching zero can make Hthr arbitrarily large, while Hpos remains Kh.Source: §F.3 · p. 22

G.1 Finite-budget lower bounds

• Proposition 1 establishes finite-budget search and certification lower bounds for every algorithm in the stated class.The algorithms use exactly T observations, sample every arm at least once, and use the prescribed posterior and terminal recommendation.Source: §G.1 · p. 22
• An event guaranteeing posterior failure has probability independent of the algorithm and budget, and causes failure regardless of the allocation.The argument uses that every arm is sampled at least once.Source: §G.1 · pp. 23–24
• The search bound takes a maximum over locations, whereas the certification bound holds for every fixed location.The search-bound conclusion follows by maximizing over locations; the certification bound is stated for any fixed a.Source: §G.1 · p. 26

G.2 Proof of the asymptotic lower bound

• For every fixed profile of one-positive-arm instances, the proof combines search and certification bounds to establish an asymptotic sample-complexity lower bound.The finite-budget inequalities are minimized over algorithms before taking the limit, and the argument allows the algorithm to depend on the budget.Source: §G.2 · pp. 26–27

G.3 Sample-complexity consequence

• As the target failure probability tends to zero, any budget achieving it uniformly over the family must diverge.For each fixed budget cap, sufficiently small target failure probabilities cannot be achieved on every instance in the family.Source: §G.3 · p. 27

G.4 Proof of Lemma 2

• On the instance with unique positive arm a, its contribution to Hcap is h, and each other arm contributes at most h.Here h is the contribution identified for the positive arm in the supplied proof passage.Source: §G.4 · p. 28

H Equal positive means

• Every admissible algorithm has the same exact asymptotic posterior-failure exponent when all arm means equal a>0.The result includes randomized algorithms and algorithms that depend on the budget, including HTG and uniform sampling.Source: H Equal positive means · p. 28

I.1 Uniform sampling

• Uniform sampling allocates observations round-robin and recommends the arm with the largest terminal posterior Z-score.The appendix also states uniform-sampling guarantees, but the supplied proposition passage does not include their formulas.Source: §I.1 · pp. 31–32

I.2 Sequential halving

• Sequential halving uses equal-stage-budget elimination based on cumulative posterior Z-scores, then recommends by the terminal score across all arms.Arms eliminated during halving remain eligible for the terminal recommendation.Source: §I.2 · p. 33, §I.1 · p. 33

Algorithm 3 satisfies

• Under the stated finite-budget condition, the sequential-halving guarantee bounds posterior-failure probability using HSH(µ) and R.The proof shows that the event ER implies posterior success, yielding the stated failure guarantee.Source: §I.2 · p. 33, Algorithm 3 satisfies · pp. 34–35

I.3 Strict separations

• Uniform sampling and the specified sequential-halving allocation can require factors Ω(K) and Ω(log K) more observations, respectively, than HTG.The comparison first takes the target failure probability to zero at fixed K, then compares the resulting coefficients as K grows through powers of two.Source: §I.3 · pp. 35, 37
• The extra log K cost of sequential halving comes from splitting its budget across Θ(log K) elimination stages, not from erroneous elimination.On this family, the probability of eliminating the positive arm is asymptotically negligible relative to certificate failure by the surviving positive arm.Source: §I.3 · p. 37

J Flat-Prior Frequentist Interpretation

• In the flat-prior limit, ranking arms by posterior Z-score is equivalent to ranking them by increasing one-sided p-value.HTG’s halving and greedy phases then correspond to retaining and sampling arms with the smallest current p-values.Source: J Flat-Prior Frequentist Interpretation · pp. 37–38

K Experimental Details and Additional Results

• The experiments use 10,000 Monte Carlo repetitions per setting and report fixed-instance success probabilities with pointwise 95% Wilson intervals.They compare HTG, uniform sampling, and posterior-based sequential halving under a Gaussian observation model and working prior.Source: K Experimental Details and Additional… · p. 38

K.1 Full parameter sweeps

• With well-separated negative competitors, HTG has a substantial advantage, consistent with screening them and concentrating observations on the positive arm.Increasing b increases separation without changing the positive mean or H_pos.Source: §K.1 · p. 38, Figure 2 · p. 39
• When b is small, posterior success can include a certificate for a truly negative recommendation, so success curves do not measure positive-arm certification alone.The objective retains both positive- and negative-recommendation success terms.Source: §K.1 · p. 38
• Additional positive arms provide more certification opportunities; uniform sampling benefits substantially, while HTG’s advantage over SH narrows from m=4 to m=16.The full sweep extends this comparison across the tested positive-arm counts.Source: §K.1 · p. 40, Figure 3 · p. 41

K.2 Scaling with the number of arms

• HTG has the smallest 90%-success threshold budget at every tested K, followed by SH and then uniform sampling.Normalized thresholds vary relatively little over tested K, consistent with predicted K^2, K^2 log K, and K^3 dependencies, respectively.Source: §K.2 · p. 40, Figure 4 · p. 42

K.3 Allocation behavior

• At T=2,048, HTG allocates 51.5% to the positive arm when b=1, versus 15.4% when b=0.02.Uniform sampling allocates 3.125% in either setting.Source: Figure 6 · p. 43, §K.3 · p. 43
• At m=16 and T=2,048, SH allocates 90.2% to positive arms versus HTG’s 83.6%, but HTG’s largest individual share is 48.4% versus SH’s 21.2%.Thus, collective positive-arm allocation alone does not explain terminal success; how observations are distributed among those arms also matters.Source: §K.3 · p. 43, Figure 7 · p. 44, Figure 8 · p. 45