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

# 1Introduction
Source: [https://arxiv.org/html/2610.20997](https://arxiv.org/html/2610.20997)
Halve\-Then\-Greedy: Adaptive Sampling for Posterior Success with Near\-Optimal Instance Dependence

Yinan LiKwang\-Sung JunKapilan Balagopalan†\\dagger

University of ArizonaPOSTECH CSE/GSAIUniversity of Arizona

Tuan Nguyen†\\daggerYao Zhao†\\daggerAbbas ZaidiHoussam Nassif

University of ArizonaUniversity of ArizonaMeta Inc\.Meta Inc\.

†Authors 3–5 are listed in alphabetical order\.

Corresponding author: Yinan Li \(yinanli@arizona\.edu\)\.

###### Abstract

We study fixed\-budget adaptive experimentation aimed at maximizing the probability of obtaining sufficient posterior evidence that a recommended design’s mean performance exceeds a target\. Unlike best\-arm identification, this objective does not require finding the best design\. For Gaussian bandits with a Gaussian prior, we propose*Halve\-Then\-Greedy*\(HTG\), which combines a large initial balanced allocation, successive halving, and posterior\-greedy sampling\. We prove instance\-dependent, finite\-budget exponential bounds on posterior\-failure probability that capture both separation from unfavorable arms and the presence of multiple favorable arms\. On one\-positive\-arm families, we establish an asymptotic sample\-complexity lower bound that HTG matches up to a logarithmic factor\. We further analyze uniform sampling and sequential halving, revealing regimes where they require more samples than HTG by linear and logarithmic factors, respectively\. Simulations illustrate HTG’s sample\-efficiency advantages and their dependence on instance structure\.

### 1Introduction

We consider an experiment comparing several candidate designs under a limited sampling budget\. Instead of identifying the design with the largest mean performance, the objective is to identify a design for which there is sufficient evidence that its mean performance exceeds a prespecified target\. Posterior\-probability criteria provide a natural way to formalize this evidence requirement, and Bayesian experimental design often evaluates how likely such criteria are to be satisfied across repeated experiments\([Hagar and Stevens, 2025](https://arxiv.org/html/2610.20997#bib.bib14)\)\. We say that*posterior success*occurs if, at the end of the fixed budget, the posterior probability that the recommended design’s mean performance exceeds the target is at least a prescribed credibility level\. Our goal is to allocate observations adaptively to make posterior success likely\. We model this problem as a Gaussian multi\-armed bandit with a Gaussian prior; the formal setup is given in Section[2](https://arxiv.org/html/2610.20997#S2)\.

This objective differs from several standard frequentist bandit pure\-exploration objectives\. Best\-arm identification \(BAI\) seeks to identify an arm with the largest true mean under a fixed sampling budget \(*fixed\-budget*setting\) or a prescribed identification\-error tolerance \(*fixed\-confidence*setting\)\([Audibert et al\., 2010](https://arxiv.org/html/2610.20997#bib.bib2);[Karnin et al\., 2013](https://arxiv.org/html/2610.20997#bib.bib5);[Garivier and Kaufmann, 2016](https://arxiv.org/html/2610.20997#bib.bib8);[Kaufmann et al\., 2016](https://arxiv.org/html/2610.20997#bib.bib11)\)\. Thresholding bandits aim to classify arms according to their means relative to a prescribed threshold\([Locatelli et al\., 2016](https://arxiv.org/html/2610.20997#bib.bib7)\)\. Good\-arm identification seeks to identify one or more arms whose true means meet a prescribed performance threshold, without requiring them to be optimal\([Kano et al\., 2019](https://arxiv.org/html/2610.20997#bib.bib15);[Katz\-Samuels and Jamieson, 2020](https://arxiv.org/html/2610.20997#bib.bib10);[Jourdan et al\., 2026](https://arxiv.org/html/2610.20997#bib.bib16)\)\. Among these, good\-arm identification is the closest frequentist formulation to our problem\. The key difference is the success criterion: good\-arm identification defines correctness in terms of the identified arms’ true means, whereas posterior success requires the terminal posterior probability that the recommended arm’s mean exceeds the target to be at least a prescribed credibility level\.

Bayesian best\-arm identification has been studied from several perspectives\.[Russo \(2020\)](https://arxiv.org/html/2610.20997#bib.bib17)analyzes the asymptotic rate at which the posterior becomes confident about the identity of the true best arm, while[Shang et al\. \(2020\)](https://arxiv.org/html/2610.20997#bib.bib4)develop fixed\-confidence stopping and sample\-complexity guarantees for Bayesian sampling rules\. In the fixed\-budget setting, prior work studies the probability of misidentifying the best arm after a prescribed number of samples, with performance averaged over the prior distribution on bandit instances\([Atsidakou et al\., 2022](https://arxiv.org/html/2610.20997#bib.bib18);[Nguyen et al\., 2025](https://arxiv.org/html/2610.20997#bib.bib19)\)\.

More closely related to our threshold\-based objective is the Bayesian satisficing formulation of[Reverdy et al\. \(2016\)](https://arxiv.org/html/2610.20997#bib.bib20), which considers whether the current belief assigns sufficiently high probability to an arm’s mean exceeding a prescribed threshold, but evaluates performance through cumulative expected satisficing regret\. A related exploration–validation approach uses adaptive sampling to select a treatment and then conducts a separate A/B test to validate the selected treatment\([Zhang et al\., 2026](https://arxiv.org/html/2610.20997#bib.bib21)\)\. Our objective instead concerns the probability of obtaining a posterior certificate at the end of a fixed budget, with all collected observations contributing to the terminal posterior and no separate validation test\.

Our posterior success problem has two complementary sources of favorable instance structure\. Strongly unfavorable arms can be screened with relatively few observations, allowing sampling to concentrate on more promising candidates, and the presence of multiple favorable arms provides multiple opportunities to obtain the required certificate\. Motivated by these two features, we propose*Halve\-Then\-Greedy*\(HTG\), which combines a large initial balanced allocation with successive halving and a final posterior\-greedy phase\.

We establish instance\-dependent, finite\-budget exponential bounds on HTG’s posterior\-failure probability that capture both sources of favorable instance structure \(Section[4](https://arxiv.org/html/2610.20997#S4)\)\. For every fixed profile of one\-positive\-arm instances, we derive an asymptotic sample\-complexity lower bound and show that HTG matches it up to a logarithmic factor in the number of arms \(Section[5](https://arxiv.org/html/2610.20997#S5)\)\. Finally, we compare HTG theoretically and empirically with uniform sampling and sequential halving \(Sections[6](https://arxiv.org/html/2610.20997#S6)–[7](https://arxiv.org/html/2610.20997#S7)\)\.

### 2Problem Formulation

We considerKKarms with unknown meansμ=\(μ1,…,μK\)∈ℝK\\mu=\(\\mu\_\{1\},\\ldots,\\mu\_\{K\}\)\\in\\mathbb\{R\}^\{K\}\. Before observing any data, the algorithm has the prior belief that the arm meansμ1,…,μK\\mu\_\{1\},\\ldots,\\mu\_\{K\}are independently drawn from a common Gaussian distribution,

μi∼𝒩⁡\(μ0,σ02\),i∈\[K\]\.\\mu\_\{i\}\\sim\\mathcal\{N\}\(\\mu\_\{0\},\\sigma\_\{0\}^\{2\}\),\\qquad i\\in\[K\]\.\(1\)Conditional on the true mean vectorμ\\mu, observations are independent across arms and samples, with

Xi,s∼𝒩⁡\(μi,σ2\),i∈\[K\],s≥1,X\_\{i,s\}\\sim\\mathcal\{N\}\(\\mu\_\{i\},\\sigma^\{2\}\),\\qquad i\\in\[K\],\\ s\\geq 1,\(2\)where the common varianceσ2\>0\\sigma^\{2\}\>0is known\. Although the algorithm uses the Gaussian prior to form its posterior beliefs, our performance guarantees treat the true mean vectorμ\\muas fixed and evaluate probability only over the observation noise and any randomization of the algorithm\.

We take the target threshold to be zero without loss of generality\. A general thresholdτ\\taucan be reduced to this setting by replacingXi,sX\_\{i,s\},μi\\mu\_\{i\}, andμ0\\mu\_\{0\}withXi,s−τX\_\{i,s\}\-\\tau,μi−τ\\mu\_\{i\}\-\\tau, andμ0−τ\\mu\_\{0\}\-\\tau, respectively\.

An algorithm𝒜\\mathcal\{A\}sequentially allocates a fixed budget ofTTobservations across theKKarms and, after the final observation, outputs an armJT∈\[K\]J\_\{T\}\\in\[K\]\. LetℱT\\mathcal\{F\}\_\{T\}denote the information available at timeTT\. For a prescribed posterior credibility toleranceδ∈\(0,1/2\)\\delta\\in\(0,1/2\), we define the posterior\-success event as

SuccT:=\{ℙ\(μJT\>0\|ℱT\)≥1−δ\},\\mathrm\{Succ\}\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\left\\\{\\mathbb\{P\}\\\!\\left\(\\mu\_\{J\_\{T\}\}\>0\\,\\middle\|\\,\\mathcal\{F\}\_\{T\}\\right\)\\geq 1\-\\delta\\right\\\},\(3\)where the conditional probability is the posterior probability induced by the Gaussian prior and observation model\. Thus, success means that the posterior probability that the output arm has mean above the target threshold is at least1−δ1\-\\delta; it does not necessarily require that its true mean be positive\.

For a fixed mean vectorμ\\mu, we evaluate an algorithm𝒜\\mathcal\{A\}through its finite\-budget failure probability

ℙμ𝒜​\(SuccTc\),\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\),whereℙμ𝒜\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\}denotes probability under the fixed instanceμ\\mu, accounting for both observation noise and any randomization of the algorithm\. Our goal is to design adaptive allocation strategies for which this failure probability decreases rapidly with the budgetTT, with rates that adapt to the difficulty of the underlying instance\.

### 3Halve\-Then\-Greedy

We first introduce the posterior quantities used by HTG\. LetΦ\\Phidenote the standard normal cumulative distribution function, and defineλ:=σ2/σ02\\lambda\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sigma^\{2\}/\\sigma\_\{0\}^\{2\}andz:=Φ−1​\(1−δ\)z\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\Phi^\{\-1\}\(1\-\\delta\)\. WriteX¯i,n:=n−1​∑s=1nXi,s\\overline\{X\}\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=n^\{\-1\}\\sum\_\{s=1\}^\{n\}X\_\{i,s\}\. By Gaussian conjugacy, afternnobservations from armii,

μi∣Xi,1:n∼𝒩\(μ^i,n,σ^n2\),\\mu\_\{i\}\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\\sim\\mathcal\{N\}\(\\widehat\{\\mu\}\_\{i,n\},\\widehat\{\\sigma\}\_\{n\}^\{2\}\),where

μ^i,n=λ​μ0\+n​X¯i,nn\+λ,σ^n=σn\+λ\.\\widehat\{\\mu\}\_\{i,n\}=\\frac\{\\lambda\\mu\_\{0\}\+n\\overline\{X\}\_\{i,n\}\}\{n\+\\lambda\},\\qquad\\widehat\{\\sigma\}\_\{n\}=\\frac\{\\sigma\}\{\\sqrt\{n\+\\lambda\}\}\.The corresponding posteriorZZ\-score is

Zi,n:=μ^i,nσ^n=λ​μ0\+n​X¯i,nσ​n\+λ,Z\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{\\widehat\{\\mu\}\_\{i,n\}\}\{\\widehat\{\\sigma\}\_\{n\}\}=\\frac\{\\lambda\\mu\_\{0\}\+n\\overline\{X\}\_\{i,n\}\}\{\\sigma\\sqrt\{n\+\\lambda\}\},so thatℙ\(μi\>0∣Xi,1:n\)=Φ\(Zi,n\)\\PP\(\\mu\_\{i\}\>0\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)=\\Phi\(Z\_\{i,n\}\)\. A derivation of these posterior quantities is given in Appendix[B](https://arxiv.org/html/2610.20997#A2)\.

LetNi​\(t\)N\_\{i\}\(t\)denote the number of observations collected from armiiaftertttotal observations\. DefineQ:=1\+⌈log2⁡K⌉Q\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=1\+\\mathinner\{\\\!\\left\\lceil\\log\_\{2\}K\\right\\rceil\},nλ:=max⁡\{1,⌈λ⌉\}n\_\{\\lambda\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\\\{1,\\mathinner\{\\\!\\left\\lceil\\lambda\\right\\rceil\}\\\}, andTcut:=3​K​max⁡\{nλ,Q\}T\_\{\\mathrm\{cut\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=3K\\max\\\{n\_\{\\lambda\},Q\\\}\. HTG is given in Algorithm[1](https://arxiv.org/html/2610.20997#alg1)\. We use an arbitrary fixed deterministic rule to break ties\.

Algorithm 1Halve\-Then\-Greedy \(HTG\)0:Budget

T≥KT\\geq K
1:if

T<TcutT<T\_\{\\mathrm\{cut\}\}then

2:Sample arms round\-robin until

TTobservations are collected\.

3:else

4:Set

S1=\[K\]S\_\{1\}=\[K\]and

t=0t=0\.

5:for

r=1,…,Qr=1,\\ldots,Qdo

6:Set

kr=\|Sr\|k\_\{r\}=\|S\_\{r\}\|and

qr=\{⌊T/\(3​K\)⌋,r=1,⌊T/\(3​Q​kr\)⌋,r≥2\.q\_\{r\}=\\begin\{cases\}\\mathinner\{\\\!\\left\\lfloor T/\(3K\)\\right\\rfloor\},&r=1,\\\\ \\mathinner\{\\\!\\left\\lfloor T/\(3Qk\_\{r\}\)\\right\\rfloor\},&r\\geq 2\.\\end\{cases\}
7:Sample each

i∈Sri\\in S\_\{r\}an additional

qrq\_\{r\}times\.

8:Update

t←t\+kr​qrt\\leftarrow t\+k\_\{r\}q\_\{r\}\.

9:if

r<Qr<Qthen

10:Retain the

⌈kr/2⌉\\mathinner\{\\\!\\left\\lceil k\_\{r\}/2\\right\\rceil\}arms in

SrS\_\{r\}with largest

Zi,Ni​\(t\)Z\_\{i,N\_\{i\}\(t\)\}; call the set

Sr\+1S\_\{r\+1\}\.

11:endif

12:endfor

13:while

t<Tt<Tdo

14:Choose

At\+1∈arg~maxi∈\[K\]Zi,Ni​\(t\)A\_\{t\+1\}\\in\\argmax\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(t\)\}\.

15:Observe arm

At\+1A\_\{t\+1\}and set

t←t\+1t\\leftarrow t\+1\.

16:endwhile

17:endif

18:Output

JT∈arg~maxi∈\[K\]Zi,Ni​\(T\)J\_\{T\}\\in\\argmax\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\.

HTG consists of two allocation phases\. The first phase uses successive halving to progressively screen out less promising arms, with a deliberately large initial batch\. The second phase allocates the remaining budget greedily according to each arm’s current posterior probability of having positive mean\. Throughout both phases, the posterior distribution of each arm mean is updated using all observations collected from that arm\.

The active setsSrS\_\{r\}are used only during the halving phase\. An arm removed from an active set remains eligible for both the subsequent greedy phase and the final recommendation, and all observations previously collected from that arm continue to be used in its posterior\. At the end of the budget, HTG recommends the arm with the largest posteriorZZ\-score \(line[18](https://arxiv.org/html/2610.20997#alg1.l18)of Algorithm[1](https://arxiv.org/html/2610.20997#alg1)\)\.

Sinceℙ\(μi\>0∣Xi,1:n\)=Φ\(Zi,n\)\\PP\(\\mu\_\{i\}\>0\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)=\\Phi\(Z\_\{i,n\}\)andΦ\\Phiis increasing, this recommendation maximizes the posterior probability that the selected arm has positive mean\. Moreover, sincez=Φ−1​\(1−δ\)z=\\Phi^\{\-1\}\(1\-\\delta\), the success event in \([3](https://arxiv.org/html/2610.20997#S2.E3)\) can be written as

SuccT=\{ZJT,NJT​\(T\)≥z\}=\{maxi∈\[K\]Zi,Ni​\(T\)≥z\}\.\\mathrm\{Succ\}\_\{T\}=\\left\\\{Z\_\{J\_\{T\},N\_\{J\_\{T\}\}\(T\)\}\\geq z\\right\\\}=\\left\\\{\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\\geq z\\right\\\}\.\(4\)
Why this structure?HTG combines three complementary design choices\. First, the initial halving stage samples every armq1=⌊T3​K⌋q\_\{1\}=\\left\\lfloor\\frac\{T\}\{3K\}\\right\\rfloortimes\. This substantial balanced allocation provides broad coverage of the arms and ensures that potentially favorable arms receive a nontrivial amount of evidence before the adaptive allocation begins\. As we show in Section[4](https://arxiv.org/html/2610.20997#S4), this feature allows HTG to benefit when several arms have positive means\.

Second, the subsequent halving stages direct observations toward increasingly promising arms instead of continuing to allocate uniformly to clearly unfavorable competitors\. At the end of each halving stage, all arms in the active set have the same total number of observations\. Since the prior parameters are common across arms, ranking these arms by their posteriorZZ\-scores is therefore equivalent to ranking them by their empirical means\. Thus, no separate statistics or posterior states are required for the halving phase\.

Finally, HTG reserves a constant fraction of the budget for posterior\-greedy sampling\. The first halving batch uses at mostT/3T/3observations, while each of the remainingQ−1Q\-1stages uses at mostT/\(3​Q\)T/\(3Q\)\. Hence the total number of observations used by the halving phase is at mostT3\+Q−13​Q​T<2​T3\\frac\{T\}\{3\}\+\\frac\{Q\-1\}\{3Q\}T<\\frac\{2T\}\{3\}, so at leastT/3T/3observations remain for the greedy phase\. These observations are allocated to the arm with the largest current posterior probability of having positive mean, and allKKoriginal arms are eligible\. This allows the procedure to concentrate evidence after the initial screening phase rather than spending the entire budget across elimination stages\.

These three components play complementary roles: the initial balanced allocation allows HTG to exploit the presence of multiple positive arms, halving progressively removes clearly unfavorable arms from the active set, and greedy sampling concentrates evidence on promising arms\. Together, they allow HTG to adapt both to instances with many positive arms and to instances where unfavorable arms can be separated quickly\. The next section quantifies this adaptivity through instance\-dependent finite\-budget guarantees\.

### 4Instance\-Dependent Guarantees

We now establish finite\-budget guarantees for HTG\. Throughout this paper, assume that

μ⋆:=maxi∈\[K\]⁡μi\>0\.\\mu\_\{\\star\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\_\{i\\in\[K\]\}\\mu\_\{i\}\>0\.The bounds reveal two complementary ways in which an instance can be favorable\. First, arms with means far below the best positive mean require relatively few samples to reveal that they are substantially suboptimal, allowing the algorithm to shift its sampling effort elsewhere\. Second, when several arms have positive means, there are several candidates that can yield the required posterior certificate, since posterior success requires sufficient evidence for only one of them\. We first introduce complexities that capture these two forms of favorable instance structure and then relate them to the quantity appearing in the HTG guarantee\.

#### 4\.1Certification complexities

Forx∈ℝx\\in\\mathbb\{R\}, writex\+:=max⁡\{x,0\}x\_\{\+\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\\\{x,0\\\}\. We begin with two interpretable instance\-dependent quantities\. Define the*capped\-gap complexity*

Hcap​\(μ\):=∑i=1Kσ2max⁡\{μ⋆,μ⋆−μi\}2,H\_\{\\mathrm\{cap\}\}\(\\mu\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{i\}\\\}^\{2\}\},\(5\)and the*positive\-arm complexity*

Hpos​\(μ\):=K​σ2∑i=1K\(μi\)\+2\.H\_\{\\mathrm\{pos\}\}\(\\mu\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{K\\sigma^\{2\}\}\{\\sum\_\{i=1\}^\{K\}\(\\mu\_\{i\}\)\_\{\+\}^\{2\}\}\.\(6\)
To see the meaning of the capped\-gap complexity, letΔi:=μ⋆−μi\\Delta\_\{i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mu\_\{\\star\}\-\\mu\_\{i\}denote the usual gap between armiiand the best mean\. ThenHcap​\(μ\)=∑i=1Kσ2max⁡\{μ⋆,Δi\}2H\_\{\\mathrm\{cap\}\}\(\\mu\)=\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\Delta\_\{i\}\\\}^\{2\}\}\. Thus, the effective gap associated with armiiisγi:=max⁡\{μ⋆,Δi\}\\gamma\_\{i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\\\{\\mu\_\{\\star\},\\Delta\_\{i\}\\\}, meaning that the usual best\-arm gap is capped from below byμ⋆\\mu\_\{\\star\}\. This is the reason for the name*capped\-gap complexity*\.

We use these to define the*certification complexity*

Hcert​\(μ\):=min⁡\{Hcap​\(μ\),Hpos​\(μ\)\}\.H\_\{\\mathrm\{cert\}\}\(\\mu\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\min\\bigl\\\{H\_\{\\mathrm\{cap\}\}\(\\mu\),H\_\{\\mathrm\{pos\}\}\(\\mu\)\\bigr\\\}\.\(7\)
The two quantities capture different sources of favorable instance structure\. For an arm withμi≥0\\mu\_\{i\}\\geq 0, we haveΔi≤μ⋆\\Delta\_\{i\}\\leq\\mu\_\{\\star\}, so its contribution toHcapH\_\{\\mathrm\{cap\}\}isσ2/μ⋆2\\sigma^\{2\}/\\mu\_\{\\star\}^\{2\}\. For a negative arm,Δi=μ⋆\+\|μi\|\>μ⋆\\Delta\_\{i\}=\\mu\_\{\\star\}\+\|\\mu\_\{i\}\|\>\\mu\_\{\\star\}, and its contribution isσ2\(μ⋆\+\|μi\|\)2\\frac\{\\sigma^\{2\}\}\{\(\\mu\_\{\\star\}\+\|\\mu\_\{i\}\|\)^\{2\}\}\. Thus, arms far below the best positive mean incur a smaller cost: relatively few samples are needed to reveal that they are substantially suboptimal\. In particular, an arm lying close to the target threshold does not incur the potentially much larger costσ2/μi2\\sigma^\{2\}/\\mu\_\{i\}^\{2\}\. In this sense,HcapH\_\{\\mathrm\{cap\}\}captures the difficulty of distinguishing promising arms from suboptimal ones\.

In contrast,HposH\_\{\\mathrm\{pos\}\}captures the benefit of having multiple positive arms\. Since posterior success requires sufficient posterior evidence for only one arm, having several positive arms provides several candidates that can yield the required posterior certificate\. For example, if exactlymmarms have common positive meanΔ\\Deltaand the remaining arms are nonpositive, thenHpos=K​σ2m​Δ2H\_\{\\mathrm\{pos\}\}=\\frac\{K\\sigma^\{2\}\}\{m\\Delta^\{2\}\}\. Hence, in this special case,HposH\_\{\\mathrm\{pos\}\}decreases as the number of positive arms increases\.

NeitherHcapH\_\{\\mathrm\{cap\}\}norHposH\_\{\\mathrm\{pos\}\}uniformly dominates the other\. Their minimum in \([7](https://arxiv.org/html/2610.20997#S4.E7)\) captures the two distinct sources of favorable instance structure described above\. Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3)illustrates how these affect the finite\-budget guarantee for HTG\.

The finite\-budget analysis of HTG involves a closely related complexity\. Let

μ\(1\)≥μ\(2\)≥⋯≥μ\(K\)\\mu\_\{\(1\)\}\\geq\\mu\_\{\(2\)\}\\geq\\cdots\\geq\\mu\_\{\(K\)\}denote the ordered arm means, and recallQ=1\+⌈log2⁡K⌉Q=1\+\\lceil\\log\_\{2\}K\\rceilfrom Section[3](https://arxiv.org/html/2610.20997#S3)\. Define

HHTG​\(μ\):=min⁡\{∑i=1Kσ2μi2,K​σ2∑i=1K\(μi\)\+2,Q​max1≤r≤K​r​σ2max⁡\{μ⋆,μ⋆−μ\(r\)\}2\}\.H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\min\\left\\\{\\begin\{aligned\} &\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\qquad\\frac\{K\\sigma^\{2\}\}\{\\sum\_\{i=1\}^\{K\}\(\\mu\_\{i\}\)\_\{\+\}^\{2\}\},\\\\ &Q\\max\_\{1\\leq r\\leq K\}\\frac\{r\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\\}^\{2\}\}\\end\{aligned\}\\right\\\}\.\(8\)Here and throughout, we use the conventionσ2/02:=\+∞\\sigma^\{2\}/0^\{2\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\+\\infty\. The three terms in \([8](https://arxiv.org/html/2610.20997#S4.E8)\) correspond to complementary guarantees provided by the three structural components of HTG\. The first is supplied by the final posterior\-greedy phase\. The second term is exactlyHposH\_\{\\mathrm\{pos\}\}and captures the benefit of having several positive arms, since HTG allocates a nontrivial number of samplesq1=⌊T3​K⌋q\_\{1\}=\\left\\lfloor\\frac\{T\}\{3K\}\\right\\rfloorto every arm before concentrating its sampling effort\. The third term comes from the successive\-halving phase and adapts to the gaps of unfavorable arms from the best positive mean\.

AlthoughHHTGH\_\{\\mathrm\{HTG\}\}is the quantity that appears directly in our finite\-budget theorem, it is within a factorQQof the simpler certification complexityHcertH\_\{\\mathrm\{cert\}\}\.

###### Lemma 1\(Comparison of complexities\)\.

For every mean vectorμ\\musatisfyingμ⋆\>0\\mu\_\{\\star\}\>0,

Hcert​\(μ\)≤HHTG​\(μ\)≤Q​Hcert​\(μ\)\.H\_\{\\mathrm\{cert\}\}\(\\mu\)\\leq H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\leq Q\\,H\_\{\\mathrm\{cert\}\}\(\\mu\)\.\(9\)

The proof is deferred to Appendix[C](https://arxiv.org/html/2610.20997#A3)\.

#### 4\.2Finite\-budget posterior certification

We now state the main finite\-budget guarantee for HTG\. Recall from Section[3](https://arxiv.org/html/2610.20997#S3)thatλ=σ2/σ02\\lambda=\\sigma^\{2\}/\\sigma\_\{0\}^\{2\},z=Φ−1​\(1−δ\)z=\\Phi^\{\-1\}\(1\-\\delta\), andTcut=3​K​max⁡\{nλ,Q\}T\_\{\\mathrm\{cut\}\}=3K\\max\\\{n\_\{\\lambda\},Q\\\}\. Let

m:=\|\{i∈\[K\]:μi\>0\}\|,c:=2z\+λ​\|μ0\|σ,m\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\bigl\|\\\{i\\in\[K\]\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\\\}\\bigr\|,\\qquad c\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sqrt\{2\}\\,z\+\\frac\{\\sqrt\{\\lambda\}\\,\|\\mu\_\{0\}\|\}\{\\sigma\},and define the instance\-dependent offset

T0:=Tcut\+96​m​c2​HHTG​\(μ\)\.T\_\{0\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=T\_\{\\mathrm\{cut\}\}\+96mc^\{2\}H\_\{\\mathrm\{HTG\}\}\(\\mu\)\.\(10\)The quantitiesmm,HHTG​\(μ\)H\_\{\\mathrm\{HTG\}\}\(\\mu\), andT0T\_\{0\}are used only in the analysis and are not inputs to HTG\.

###### Theorem 1\(Finite\-budget posterior certification\)\.

Under the Gaussian observation model \([2](https://arxiv.org/html/2610.20997#S2.E2)\) with the common Gaussian prior \([1](https://arxiv.org/html/2610.20997#S2.E1)\), for every fixed mean vectorμ\\muwithμ⋆\>0\\mu\_\{\\star\}\>0and integerT≥KT\\geq K, HTG satisfies

ℙμHTG​\(SuccTc\)≤min⁡\{1,2​K​T​exp⁡\(−\(T−T0\)\+192​HHTG​\(μ\)\)\}\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\min\\left\\\{1,\\;2KT\\exp\\left\(\-\\frac\{\(T\-T\_\{0\}\)\_\{\+\}\}\{192H\_\{\\mathrm\{HTG\}\}\(\\mu\)\}\\right\)\\right\\\}\.\(11\)

The proof is deferred to Appendix[D](https://arxiv.org/html/2610.20997#A4)\. Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)shows that, after the finite\-budget offsetT0T\_\{0\}, the failure probability decreases exponentially at a rate governed byHHTG​\(μ\)H\_\{\\mathrm\{HTG\}\}\(\\mu\)\. By Lemma[1](https://arxiv.org/html/2610.20997#Thmlemma1), this rate complexity is within a factorQ=O⁡\(log⁡K\)Q=O\(\\log K\)of the certification complexityHcert​\(μ\)H\_\{\\mathrm\{cert\}\}\(\\mu\)\. The offsetT0T\_\{0\}accounts for the budget required by the initial allocation throughTcutT\_\{\\mathrm\{cut\}\}, as well as the effect of the prior mean and the additional samples needed to reach the prescribed posterior credibility level\.

As an immediate consequence, for any target failure probabilityη∈\(0,1\)\\eta\\in\(0,1\),

T≥T0\+192​HHTG​\(μ\)​log⁡2​K​Tη⟹ℙμHTG​\(SuccTc\)≤η\.T\\geq T\_\{0\}\+192H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\log\\frac\{2KT\}\{\\eta\}\\quad\\Longrightarrow\\quad\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\eta\.\(12\)Hereδ\\deltadetermines the posterior credibility required for success, whereasη\\etais the desired probability of failing to obtain such a certificate under the fixed instanceμ\\mu\. A fully explicit sufficient budget with no occurrence ofTTinside the logarithm is given in Appendix[E](https://arxiv.org/html/2610.20997#A5)\.

#### 4\.3Interpretation and proof ideas

We illustrate how the two sources of favorable instance structure translate into the guarantee of Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1), and then summarize the main proof ideas\. Detailed calculations for these examples, together with an additional example involving a competing arm whose mean is close to zero, are given in Appendix[F](https://arxiv.org/html/2610.20997#A6)\.

One positive arm with other arms strongly negative\.Consider an instance withμ1=a\>0\\mu\_\{1\}=a\>0andμ2=⋯=μK=−b\\mu\_\{2\}=\\cdots=\\mu\_\{K\}=\-b, whereb≥a​Kb\\geq a\\sqrt\{K\}\. Then

Hcert​\(μ\)≍HHTG​\(μ\)≍σ2a2,Hpos​\(μ\)=K​σ2a2\.H\_\{\\mathrm\{cert\}\}\(\\mu\)\\asymp H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\asymp\\frac\{\\sigma^\{2\}\}\{a^\{2\}\},\\qquad H\_\{\\mathrm\{pos\}\}\(\\mu\)=\\frac\{K\\sigma^\{2\}\}\{a^\{2\}\}\.More precisely, bothHcert​\(μ\)H\_\{\\mathrm\{cert\}\}\(\\mu\)andHHTG​\(μ\)H\_\{\\mathrm\{HTG\}\}\(\\mu\)lie betweenσ2/a2\\sigma^\{2\}/a^\{2\}and2​σ2/a22\\sigma^\{2\}/a^\{2\}\. Thus, the complexityHHTGH\_\{\\mathrm\{HTG\}\}appearing in Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)can be a factor of orderKKsmaller thanHposH\_\{\\mathrm\{pos\}\}on this family\. Moreover, the first term in \([8](https://arxiv.org/html/2610.20997#S4.E8)\), which arises from the final posterior\-greedy phase, is at most2​σ2/a22\\sigma^\{2\}/a^\{2\}, whereas the third term, which arises from the successive\-halving phase, isQ​σ2/a2Q\\sigma^\{2\}/a^\{2\}\. Hence the final posterior\-greedy phase removes the additional factorQQthat would arise from the halving\-based term alone\.

Many positive arms\.At the other extreme, supposeμ1=⋯=μK=a\>0\\mu\_\{1\}=\\cdots=\\mu\_\{K\}=a\>0\. Then

Hcap​\(μ\)=K​σ2a2,HHTG​\(μ\)=Hpos​\(μ\)=σ2a2\.H\_\{\\mathrm\{cap\}\}\(\\mu\)=\\frac\{K\\sigma^\{2\}\}\{a^\{2\}\},\\qquad H\_\{\\mathrm\{HTG\}\}\(\\mu\)=H\_\{\\mathrm\{pos\}\}\(\\mu\)=\\frac\{\\sigma^\{2\}\}\{a^\{2\}\}\.Thus, the complexityHHTGH\_\{\\mathrm\{HTG\}\}appearing in Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)is a factorKKsmaller thanHcapH\_\{\\mathrm\{cap\}\}on this family\. This reflects the fact that when many arms are positive, any of them can provide the posterior certificate required for success\. AlthoughHHTGH\_\{\\mathrm\{HTG\}\}itself is independent ofKKin this example, the total sufficient budget is not: herem=Km=K, so the offset isT0=Tcut\+96​K​c2​σ2/a2T\_\{0\}=T\_\{\\mathrm\{cut\}\}\+96Kc^\{2\}\\sigma^\{2\}/a^\{2\}\.

Proof ideas\.The proof, given in Appendix[D](https://arxiv.org/html/2610.20997#A4), begins with a concentration event that holds simultaneously over all arms and sample counts, and hence also at the adaptive sample counts generated by HTG\. Failure at the end of the budget means that no arm is certified, that is,Zi,Ni​\(T\)<zZ\_\{i,N\_\{i\}\(T\)\}<zfor everyi∈\[K\]i\\in\[K\]\. On the concentration event, this imposes an upper bound on the total number of samples collected from each positive arm\. The final posterior\-greedy phase and the successive\-halving phase then give separate budget\-counting arguments, yielding the first and third terms in \([8](https://arxiv.org/html/2610.20997#S4.E8)\), respectively\.

The second term follows from a separate argument\. The initial allocation ensures that every arm receives at leastq1=⌊T/\(3​K\)⌋q\_\{1\}=\\lfloor T/\(3K\)\\rfloorsamples\. Hence, if the algorithm fails, then for every positive armiithere must exist somen≥q1n\\geq q\_\{1\}such thatZi,n<zZ\_\{i,n\}<z—namely,n=Ni​\(T\)n=N\_\{i\}\(T\)\. We bound the probability of this event uniformly over alln≥q1n\\geq q\_\{1\}for each positive arm\. Since these events depend only on the independent observation sequences of the individual arms, their probabilities can be multiplied across positive arms\. The resulting exponent involves∑i:μi\>0μi2/σ2=K/Hpos\(μ\)\\sum\_\{i\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\}\\mu\_\{i\}^\{2\}/\\sigma^\{2\}=K/H\_\{\\mathrm\{pos\}\}\(\\mu\), which yields the second term in \([8](https://arxiv.org/html/2610.20997#S4.E8)\)\. Combining the three bounds gives Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)\.

### 5Lower Bounds and Near\-Optimality

We next establish lower bounds on the probability of posterior failure and compare them with the guarantee of Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)\. We consider families of instances with exactly one positive arm, whose location is unknown, while allowing the negative means to differ across arms\. As we will show, on each such family, the lower\-bound complexity agrees withHcertH\_\{\\mathrm\{cert\}\}up to universal constants\. By Lemma[1](https://arxiv.org/html/2610.20997#Thmlemma1),HHTGH\_\{\\mathrm\{HTG\}\}is within a factorQ=O⁡\(log⁡K\)Q=O\(\\log K\)ofHcertH\_\{\\mathrm\{cert\}\}\. Thus, HTG’s asymptotic sample complexity is within anO⁡\(log⁡K\)O\(\\log K\)factor of the lower bound on these one\-positive\-arm families\.

#### 5\.1Families with one positive arm

FixΔ\>0\\Delta\>0andε=\(ε1,…,εK\)∈\(0,∞\)K\\varepsilon=\(\\varepsilon\_\{1\},\\ldots,\\varepsilon\_\{K\}\)\\in\(0,\\infty\)^\{K\}\. For eacha∈\[K\]a\\in\[K\], define the mean vectorμ\(a\)\\mu^\{\(a\)\}by

μi\(a\):=\{Δ,i=a,−εi,i≠a,i∈\[K\]\.\\mu\_\{i\}^\{\(a\)\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\begin\{cases\}\\Delta,&i=a,\\\\ \-\\varepsilon\_\{i\},&i\\neq a,\\end\{cases\}\\qquad i\\in\[K\]\.\(13\)Every instance in this family has one positive arm with meanΔ\\Delta\. The family varies its locationaa, while each remaining armiihas mean−εi\-\\varepsilon\_\{i\}\. The negative means need not be equal\.

Two quantities will govern the lower bound:

h:=σ2Δ2,S:=∑i=1Kσ2\(Δ\+εi\)2\.h\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{\\sigma^\{2\}\}\{\\Delta^\{2\}\},\\qquad S\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{i\}\)^\{2\}\}\.\(14\)Herehhis the single\-arm inverse\-square term, corresponding to the complexity of obtaining evidence that a meanΔ\\Deltaexceeds zero, even when the positive arm’s location is known\. The quantitySSis the sum of inverse\-square terms over all possible locations of the positive arm\. Each term uses the differenceΔ\+εi\\Delta\+\\varepsilon\_\{i\}between the two possible meansΔ\\Deltaand−εi\-\\varepsilon\_\{i\}for armii\. In this sense,SSreflects the complexity associated with uncertainty about which arm is positive\.

For each budgetT≥KT\\geq K, we consider adaptive algorithms that collect exactlyTTobservations and sample every arm at least once\. The algorithms may be randomized and may depend onTT\. At each round, an algorithm selects an arm using only previously collected observations and its internal randomization\. All algorithms use the Gaussian prior \([1](https://arxiv.org/html/2610.20997#S2.E1)\), the prescribed credibility toleranceδ\\delta, and all observations collected from each arm when forming its posterior\.

We use the posterior\-maximizing terminal recommendation from Section[3](https://arxiv.org/html/2610.20997#S3)\(line[18](https://arxiv.org/html/2610.20997#alg1.l18)of Algorithm[1](https://arxiv.org/html/2610.20997#alg1)\),

JT∈arg⁡maxi∈\[K\]⁡Zi,Ni​\(T\)\.J\_\{T\}\\in\\arg\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\.This recommendation entails no loss for the posterior\-success objective\. Indeed, since the posterior probability that armiihas positive mean isΦ⁡\(Zi,Ni​\(T\)\)\\Phi\(Z\_\{i,N\_\{i\}\(T\)\}\)andΦ\\Phiis increasing, for any realized observation history this recommendation maximizes the posterior probability that the selected arm has positive mean\. In particular, it succeeds whenever any terminal recommendation could succeed, as characterized by \([4](https://arxiv.org/html/2610.20997#S3.E4)\)\.

We call any algorithm satisfying the sampling, posterior, and terminal\-recommendation conditions described above an*admissible algorithm*\. An admissible algorithm does not know the true mean vectorμ\\muand its sampling decisions may depend only on the observations collected so far, the known problem parameters, and its internal randomization\.

Define the minimax failure probability over this family,

rT⋆​\(Δ,ε\):=inf𝒜maxa∈\[K\]⁡ℙμ\(a\)𝒜​\(SuccTc\),r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\inf\_\{\\mathcal\{A\}\}\\max\_\{a\\in\[K\]\}\\mathbb\{P\}\_\{\\mu^\{\(a\)\}\}^\{\\mathcal\{A\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\),\(15\)where the infimum is over admissible algorithms\. In words,rT⋆​\(Δ,ε\)r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)is the smallest achievable worst\-case failure probability over theKKpossible locations of the positive arm, for the fixed profile\(Δ,ε\)\(\\Delta,\\varepsilon\)\.

Throughout this section, the family parametersKK,Δ\\Delta, andε\\varepsilon, the observation varianceσ2\\sigma^\{2\}, the prior parameters\(μ0,σ02\)\(\\mu\_\{0\},\\sigma\_\{0\}^\{2\}\), and the posterior credibility toleranceδ\\deltaare fixed asT→∞T\\to\\infty\.

#### 5\.2An asymptotic lower bound

We now show that bothhhandSSimpose necessary sample\-complexity scales for posterior success\.

###### Theorem 2\(Search and certification lower bound\)\.

For everyΔ\>0\\Delta\>0andε∈\(0,∞\)K\\varepsilon\\in\(0,\\infty\)^\{K\}, consider the family \([13](https://arxiv.org/html/2610.20997#S5.E13)\) and the admissible algorithms described in Section[5\.1](https://arxiv.org/html/2610.20997#S5.SS1)\. WithhhandSSdefined in \([14](https://arxiv.org/html/2610.20997#S5.E14)\), the minimax failure probability in \([15](https://arxiv.org/html/2610.20997#S5.E15)\) satisfies

lim supT→∞−1TlogrT⋆\(Δ,ε\)≤12​max⁡\{h,S\}\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\frac\{1\}\{2\\max\\\{h,S\\\}\}\.\(16\)

The proof, including finite\-budget lower bounds from which \([16](https://arxiv.org/html/2610.20997#S5.E16)\) follows, is deferred to Appendix[G](https://arxiv.org/html/2610.20997#A7)\.

Theorem[2](https://arxiv.org/html/2610.20997#Thmtheorem2)applies to every fixed profile\(Δ,ε\)\(\\Delta,\\varepsilon\)\. Here, failure refers to the eventSuccTc\\mathrm\{Succ\}\_\{T\}^\{c\}\. For any admissible algorithm, the asymptotic exponent of its worst\-case failure probability over the family cannot exceed the bound in \([16](https://arxiv.org/html/2610.20997#S5.E16)\)\. At each budgetTT, the instance attaining the worst\-case failure probability may depend on both the algorithm andTT\.

In sample\-complexity terms, achieving failure probability at mostη\\etaon every instance in the family requires

T≥\(2−oη​\(1\)\)​max⁡\{h,S\}​log​1η,η↓0,T\\geq\\bigl\(2\-o\_\{\\eta\}\(1\)\\bigr\)\\max\\\{h,S\\\}\\log\\frac\{1\}\{\\eta\},\\qquad\\eta\\downarrow 0,\(17\)whereoη​\(1\)→0o\_\{\\eta\}\(1\)\\to 0asη↓0\\eta\\downarrow 0, with all family, observation, and prior parameters, as well asδ\\delta, held fixed\. The derivation of \([17](https://arxiv.org/html/2610.20997#S5.E17)\) from Theorem[2](https://arxiv.org/html/2610.20997#Thmtheorem2)is given in Appendix[G\.3](https://arxiv.org/html/2610.20997#A7.SS3)\.

Proof idea\.Fix an admissible algorithm\. Under any auxiliary instance whose means are all negative, we construct an eventEEon whichZi,n<zZ\_\{i,n\}<zfor every armiiand everyn≥1n\\geq 1\. Its probability is positive and does not depend on the budget or algorithm\. Since every arm is sampled at least once, \([4](https://arxiv.org/html/2610.20997#S3.E4)\) implies thatEEguarantees posterior failure\.

For the termSS, takeν=\(−ε1,…,−εK\)\\nu=\(\-\\varepsilon\_\{1\},\\ldots,\-\\varepsilon\_\{K\}\)and consider the observed history underν\\nuconditional onEE\. Since the algorithm still collects exactlyTTobservations, the conditional expected sample counts sum toTT\. A weighted averaging argument shows that there existsa∈\[K\]a\\in\[K\]satisfying

𝔼ν​\[Na​\(T\)∣E\]≤TS​σ2\(Δ\+εa\)2\.\\mathbb\{E\}\_\{\\nu\}\[N\_\{a\}\(T\)\\mid E\]\\leq\\frac\{T\}\{S\}\\,\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{a\}\)^\{2\}\}\.Passing fromν\\nutoμ\(a\)\\mu^\{\(a\)\}changes only the mean of armaa, from−εa\-\\varepsilon\_\{a\}toΔ\\Delta\. A subsequent change\-of\-measure argument gives the upper bound1/\(2​S\)1/\(2S\)on the asymptotic exponent of the worst\-case posterior\-failure probability over the family\.

For the termhh, fix a locationaaand replace its positive meanΔ\\Deltaby−β\-\\beta, whereβ\>0\\beta\>0, leaving the other means unchanged\. For each fixedβ\\beta, a similar change\-of\-measure argument usingNa​\(T\)≤TN\_\{a\}\(T\)\\leq Tgives, asT→∞T\\to\\infty, the upper bound\(Δ\+β\)2/\(2​σ2\)\(\\Delta\+\\beta\)^\{2\}/\(2\\sigma^\{2\}\)on the failure exponent\. Lettingβ↓0\\beta\\downarrow 0afterwards yields1/\(2​h\)1/\(2h\)\. Combining the bounds1/\(2​S\)1/\(2S\)and1/\(2​h\)1/\(2h\)gives \([16](https://arxiv.org/html/2610.20997#S5.E16)\)\.

#### 5\.3Comparison with the upper bound

We now compare the lower\-bound complexitymax⁡\{h,S\}\\max\\\{h,S\\\}withHcertH\_\{\\mathrm\{cert\}\}on one\-positive\-arm families\.

###### Lemma 2\(Certification complexity on one\-positive\-arm families\)\.

For the family \([13](https://arxiv.org/html/2610.20997#S5.E13)\) and everya∈\[K\]a\\in\[K\],

max⁡\{h,S\}≤Hcert​\(μ\(a\)\)≤h\+S≤2​max⁡\{h,S\}\.\\max\\\{h,S\\\}\\leq H\_\{\\mathrm\{cert\}\}\(\\mu^\{\(a\)\}\)\\leq h\+S\\leq 2\\max\\\{h,S\\\}\.\(18\)

The proof is deferred to Appendix[G\.4](https://arxiv.org/html/2610.20997#A7.SS4)\. Lemma[2](https://arxiv.org/html/2610.20997#Thmlemma2)shows that, on these one\-positive\-arm families, the lower\-bound complexitymax⁡\{h,S\}\\max\\\{h,S\\\}and the certification complexityHcertH\_\{\\mathrm\{cert\}\}agree up to universal constants\. By Lemma[1](https://arxiv.org/html/2610.20997#Thmlemma1),HHTGH\_\{\\mathrm\{HTG\}\}is within a factorQ=O⁡\(log⁡K\)Q=O\(\\log K\)ofHcertH\_\{\\mathrm\{cert\}\}\. Together with Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1), this shows that HTG’s asymptotic sample complexity is within anO⁡\(log⁡K\)O\(\\log K\)factor of the lower bound on these one\-positive\-arm families\. In this sense, HTG is near\-optimal up to a logarithmic factor in its sample complexity on this class of instances\.

The one\-positive\-arm families considered above include the “one positive arm with other arms strongly negative” example from Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3)as a special case, while also allowing arbitrary negative means\. As a complement, Appendix[H](https://arxiv.org/html/2610.20997#A8)analyzes the “many positive arms” example\. When all arms have the same positive mean, every admissible algorithm has the exact asymptotic posterior\-failure exponent1/\(2​Hpos​\(μ\)\)1/\(2H\_\{\\mathrm\{pos\}\}\(\\mu\)\), withKKand all model parameters held fixed\.

### 6Connections and Comparisons

We first compare HTG with two standard fixed\-budget sampling strategies, uniform sampling and sequential halving, and then discuss a frequentist interpretation of the posterior quantities used by HTG\.

#### 6\.1Uniform sampling and sequential halving

We compare HTG with uniform sampling and sequential halving \(SH\)\([Karnin et al\., 2013](https://arxiv.org/html/2610.20997#bib.bib5)\), changing only the sampling rule\. All methods use the same posterior updates from Section[3](https://arxiv.org/html/2610.20997#S3), with all observations collected from an arm used to update its posterior\. At the end of the budget, every method recommendsJT∈arg⁡maxi∈\[K\]⁡Zi,Ni​\(T\)J\_\{T\}\\in\\arg\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\. As discussed in Section[5\.1](https://arxiv.org/html/2610.20997#S5.SS1), this recommendation is optimal for the posterior\-success objective: whenever any arm satisfies the posterior\-success criterion \([3](https://arxiv.org/html/2610.20997#S2.E3)\), the recommended arm does as well\. For elimination\-based sampling rules, eliminated arms remain eligible for the final recommendation\.

Uniform sampling\.Uniform sampling allocates the budget round\-robin, so each arm receives eithern=⌊T/K⌋n=\\lfloor T/K\\rfloororn\+1n\+1observations\. Recallc=2​z\+λ​\|μ0\|/σc=\\sqrt\{2\}\\,z\+\\sqrt\{\\lambda\}\|\\mu\_\{0\}\|/\\sigma\. Ifn≥λn\\geq\\lambda, then

ℙμUniform​\(SuccTc\)≤exp⁡\[−12​\(μ⋆σ​n−c\)\+2\]\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\exp\\left\[\-\\frac\{1\}\{2\}\\left\(\\frac\{\\mu\_\{\\star\}\}\{\\sigma\}\\sqrt\{n\}\-c\\right\)\_\{\+\}^\{2\}\\right\]\.\(19\)Moreover, uniform sampling has the exact asymptotic failure exponent

limT→∞−1TlogℙμUniform\(SuccTc\)=12​Hpos​\(μ\)\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)=\\frac\{1\}\{2H\_\{\\mathrm\{pos\}\}\(\\mu\)\}\.\(20\)\([20](https://arxiv.org/html/2610.20997#S6.E20)\) shows that uniform sampling exploits the presence of multiple positive arms throughHposH\_\{\\mathrm\{pos\}\}, but cannot redirect observations away from unfavorable arms\. Exact formulas and proofs are given in Appendix[I\.1](https://arxiv.org/html/2610.20997#A9.SS1)\.

Sequential halving\.SH divides the budget approximately equally acrossQ−1=⌈log2⁡K⌉Q\-1=\\lceil\\log\_\{2\}K\\rceilelimination stages\([Karnin et al\., 2013](https://arxiv.org/html/2610.20997#bib.bib5)\)\. Starting with allKKarms, each stage samples the active arms equally and retains the upper half according to their posteriorZZ\-scores\. Since the active arms have the same cumulative sample count at each elimination, this ranking is equivalent to ranking them by their empirical means\.

For the posterior\-success objective in \([3](https://arxiv.org/html/2610.20997#S2.E3)\), SH satisfies a finite\-budget guarantee whose leading instance\-dependent complexity is

HSH​\(μ\):=\(Q−1\)​min⁡\{∑i=1Kσ2μi2,K​σ2μ⋆2\}\.H\_\{\\mathrm\{SH\}\}\(\\mu\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\(Q\-1\)\\min\\left\\\{\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\frac\{K\\sigma^\{2\}\}\{\\mu\_\{\\star\}^\{2\}\}\\right\\\}\.\(21\)The precise finite\-budget guarantee, algorithm specification, and proof are given in Appendix[I\.2](https://arxiv.org/html/2610.20997#A9.SS2)\.

The leading complexities of the three methods can now be compared directly\. Uniform sampling has complexityHpos​\(μ\)H\_\{\\mathrm\{pos\}\}\(\\mu\)by \([20](https://arxiv.org/html/2610.20997#S6.E20)\), and SH has complexityHSH​\(μ\)H\_\{\\mathrm\{SH\}\}\(\\mu\)\. By the definition ofHHTGH\_\{\\mathrm\{HTG\}\}in \([8](https://arxiv.org/html/2610.20997#S4.E8)\), we have,

HHTG​\(μ\)≤Hpos​\(μ\),HHTG​\(μ\)≤HSH​\(μ\)Q−1,K≥2\.H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\leq H\_\{\\mathrm\{pos\}\}\(\\mu\),\\qquad H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\leq\\frac\{H\_\{\\mathrm\{SH\}\}\(\\mu\)\}\{Q\-1\},\\quad K\\geq 2\.\(22\)
\([22](https://arxiv.org/html/2610.20997#S6.E22)\) shows that, at the level of the leading instance\-dependent complexities appearing in our guarantees, HTG is no larger than either baseline and can be strictly smaller by adapting its allocation to favorable instance structure\. Instance families on which HTG has strictly smaller sample complexity than uniform sampling and SH are given in Appendix[I\.3](https://arxiv.org/html/2610.20997#A9.SS3), and we compare the three methods empirically in Section[7](https://arxiv.org/html/2610.20997#S7)\.

#### 6\.2Frequentist interpretation

The posterior\-based rules have a frequentist interpretation in terms of one\-sided Gaussian tests\. Consider the flat\-prior limitσ02→∞\\sigma\_\{0\}^\{2\}\\to\\inftywithμ0\\mu\_\{0\}fixed, so thatλ→0\\lambda\\to 0\. In this limit,

Zi,n=n​X¯i,nσ,pi,n:=1−Φ⁡\(Zi,n\)\.Z\_\{i,n\}=\\frac\{\\sqrt\{n\}\\,\\overline\{X\}\_\{i,n\}\}\{\\sigma\},\\qquad p\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=1\-\\Phi\(Z\_\{i,n\}\)\.For a fixed arm and deterministic sample count,pi,np\_\{i,n\}is the usual one\-sided Gaussianpp\-value for testingH0,i:μi≤0H\_\{0,i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\\leq 0againstH1,i:μi\>0H\_\{1,i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\. Moreover, in the flat\-prior limit, the posterior probability of positivity satisfiesℙ\(μi\>0∣Xi,1:n\)=1−pi,n\\mathbb\{P\}\(\\mu\_\{i\}\>0\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)=1\-p\_\{i,n\}\.

Under this interpretation, HTG’s halving phase retains the active arms with the smallest currentpp\-values, its greedy phase samples an arm with the smallest currentpp\-value, and its terminal recommendation selects an arm with the smallest terminalpp\-value\. The posterior\-success criterion becomes

SuccT=\{mini∈\[K\]pi,Ni​\(T\)≤δ\}\.\\mathrm\{Succ\}\_\{T\}=\\left\\\{\\min\_\{i\\in\[K\]\}p\_\{i,N\_\{i\}\(T\)\}\\leq\\delta\\right\\\}\.Equivalently, at least one one\-sided Gaussian lower confidence boundX¯i,Ni​\(T\)−z​σ/Ni​\(T\)\\overline\{X\}\_\{i,N\_\{i\}\(T\)\}\-z\\sigma/\\sqrt\{N\_\{i\}\(T\)\}is nonnegative\. A derivation of these identities under a flat prior is given in Appendix[J](https://arxiv.org/html/2610.20997#A10)\.

### 7Experiments and Discussion

Setup\.We compare HTG, uniform sampling, and posterior\-based sequential halving \(SH\), discussed in Section[6\.1](https://arxiv.org/html/2610.20997#S6.SS1)\. All methods use the same posterior, incorporating all collected observations, and recommend the arm with the largest terminal posteriorZZ\-score over allKKarms\. We setK=32K=32,σ2=1\\sigma^\{2\}=1, the working prior to𝒩⁡\(0,1\)\\mathcal\{N\}\(0,1\), andδ=0\.01\\delta=0\.01\. We estimateℙμ𝒜​\(SuccT\)\\mathbb\{P\}^\{\\mathcal\{A\}\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}\)using10,00010\{,\}000repetitions per instance and budget\. Within each repetition, thennth pull of armiiyields the same simulated observation for every method\. Success is evaluated after exactlyTTsamples\. We use1616approximately logarithmically spaced budgets from576576to65,53665\{,\}536, rounded to multiples ofKK\.

Figure 1:Posterior success probability versus budget\. Left column: one arm has mean0\.10\.1, and the remaining arms have mean−b\-b, withb=0\.02b=0\.02\(top\) andb=1b=1\(bottom\)\. Right column:mmarms have mean0\.10\.1, and the remaining arms have mean−1\-1, withm=4m=4\(top\) andm=16m=16\(bottom\)\. Error bars show pointwise95%95\\%Wilson Monte Carlo confidence intervals based on10,00010\{,\}000repetitions\.Negative competitors\.The left column of Figure[1](https://arxiv.org/html/2610.20997#S7.F1)examines the separation effect illustrated by the single\-positive\-arm example in Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3)\. IncreasingbbreducesHcapH\_\{\\mathrm\{cap\}\}while leavingHposH\_\{\\mathrm\{pos\}\}unchanged\. HTG benefits substantially from easier negative competitors, and its advantage over both baselines is more pronounced in the well\-separated setting\.

Multiple positive arms\.The right column examines the multiple\-opportunity effect illustrated by the many\-positive\-arm example in Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3)\. This behavior is consistent with the role ofHposH\_\{\\mathrm\{pos\}\}, which decreases in proportion to1/m1/mwhen the positive means are equal and fixed: additional favorable arms provide more opportunities to obtain a certificate\.

Appendix[K](https://arxiv.org/html/2610.20997#A11)extends both comparisons over a broader range of instance parameters\. It also reports sample allocation trajectories and comparisons across the number of arms\. The latter use the same instance family as Appendix[I\.3](https://arxiv.org/html/2610.20997#A9.SS3), where uniform sampling and SH requireΩ⁡\(K\)\\Omega\(K\)andΩ⁡\(log⁡K\)\\Omega\(\\log K\)times as many samples as HTG, respectively\. Empirical scalings withKKare consistent with the theoretical rates established on this family\.

Conclusion\.We proposed HTG for fixed\-budget posterior success, exploiting the two sources of favorable instance structure summarized byHcert=min⁡\{Hcap,Hpos\}H\_\{\\mathrm\{cert\}\}=\\min\\\{H\_\{\\mathrm\{cap\}\},H\_\{\\mathrm\{pos\}\}\\\}\. Its finite\-budget exponential failure bound is governed by a complexity withinO⁡\(log⁡K\)O\(\\log K\)ofHcertH\_\{\\mathrm\{cert\}\}, and our lower bounds establish near\-optimal asymptotic sample complexity on one\-positive\-arm families\. An interesting extension, motivated by experiments that compare multiple candidate treatments against a shared control\([Villar et al\., 2015](https://arxiv.org/html/2610.20997#bib.bib28)\), is posterior certification relative to an unknown control mean, for example requiringℙ⁡\(μJT−μc\>τ∣ℱT\)≥1−δ\\mathbb\{P\}\(\\mu\_\{J\_\{T\}\}\-\\mu\_\{c\}\>\\tau\\mid\\mathcal\{F\}\_\{T\}\)\\geq 1\-\\delta\. This introduces a new allocation tradeoff between learning the common control meanμc\\mu\_\{c\}and gathering evidence for promising candidate arms\.

### References

- S\. Agrawal and N\. GoyalAnalysis of Thompson Sampling for the Multi\-armed Bandit Problem\.\.InProceedings of the Conference on Learning Theory \(COLT\),Vol\.23,pp\. 39\.1–39\.26\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1)\.
- Atsidakouet al\.\(2022\)A\. Atsidakou, S\. Katariya, S\. Sanghavi, and B\. KvetonBayesian fixed\-budget best\-arm identification\.arXiv preprint arXiv:2211\.08572\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1),[§1](https://arxiv.org/html/2610.20997#S1.p3.1)\.
- Audibertet al\.\(2010\)J\. Audibert, S\. Bubeck, and R\. MunosBest Arm Identification in Multi\-Armed Bandits\.InProceedings of the Conference on Learning Theory \(COLT\),Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p1.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Carpentier and Locatelli \(2016\)A\. Carpentier and A\. LocatelliTight \(lower\) bounds for the fixed budget best arm identification bandit problem\.InProceedings of the Conference on Learning Theory \(COLT\),Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p1.1)\.
- Chaloner and Verdinelli \(1995\)K\. Chaloner and I\. VerdinelliBayesian experimental design: a review\.Statistical science,pp\. 273–304\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p6.1)\.
- Degenne and Koolen \(2019\)R\. Degenne and W\. M\. KoolenPure Exploration with Multiple Correct Answers\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1)\.
- Garivier and Kaufmann \(2016\)A\. Garivier and E\. KaufmannOptimal best arm identification with fixed confidence\.InProceedings of the Conference on Learning Theory \(COLT\),pp\. 998–1027\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p1.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Hagar and Stevens \(2025\)L\. Hagar and N\. T\. StevensAn economical approach to design posterior analyses\.Journal of the American Statistical Association120\(552\),pp\. 2559–2568\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p6.1),[§1](https://arxiv.org/html/2610.20997#S1.p1.1)\.
- Huanget al\.\(2026\)Y\. Huang, Y\. Hou, and V\. Y\. TanBayesian best\-arm identification with abstention: a polynomial\-to\-exponential phase transition\.arXiv preprint arXiv:2606\.29203\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1)\.
- Janget al\.\(2024\)K\. Jang, J\. Komiyama, and K\. YamazakiFixed confidence best arm identification in the bayesian setting\.Advances in Neural Information Processing Systems37,pp\. 17789–17829\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1)\.
- Jourdanet al\.\(2026\)M\. Jourdan, A\. Delahaye\-Duriez, and C\. RédaAn anytime algorithm for good arm identification\.Journal of Machine Learning Research27\(19\),pp\. 1–90\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1),[Appendix A](https://arxiv.org/html/2610.20997#A1.p3.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Kanoet al\.\(2019\)H\. Kano, J\. Honda, K\. Sakamaki, K\. Matsuura, A\. Nakamura, and M\. SugiyamaGood arm identification via bandit feedback\.Machine Learning108\(5\),pp\. 721–745\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Karninet al\.\(2013\)Z\. Karnin, T\. Koren, and O\. SomekhAlmost Optimal Exploration in Multi\-Armed Bandits\.InProceedings of the International Conference on Machine Learning \(ICML\),pp\. 1238–1246\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p1.1),[§I\.2](https://arxiv.org/html/2610.20997#A9.SS2.p1.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1),[§6\.1](https://arxiv.org/html/2610.20997#S6.SS1.p1.1),[§6\.1](https://arxiv.org/html/2610.20997#S6.SS1.p3.1)\.
- Katz\-Samuels and Jamieson \(2020\)J\. Katz\-Samuels and K\. JamiesonThe True Sample Complexity of Identifying Good Arms\.InProceedings of the International Conference on Artificial Intelligence and Statistics \(AISTATS\),pp\. 1781–1791\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Kaufmannet al\.\(2016\)E\. Kaufmann, O\. Cappé, and A\. GarivierOn the complexity of best\-arm identification in multi\-armed bandit models\.Journal of Machine Learning Research17\(1\),pp\. 1–42\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p1.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Kaufmannet al\.\(2018\)E\. Kaufmann, W\. Koolen, and A\. GarivierSequential test for the lowest mean: from thompson to murphy sampling\.Advances in Neural Information Processing Systems31\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1)\.
- Locatelliet al\.\(2016\)A\. Locatelli, M\. Gutzeit, and A\. CarpentierAn optimal algorithm for the Thresholding Bandit Problem\.InProceedings of The International Conference on Machine Learning \(ICML\),pp\. 1690–1698\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1),[§1](https://arxiv.org/html/2610.20997#S1.p2.1)\.
- Nguyenet al\.\(2025\)N\. Nguyen, I\. Aouali, A\. György, and C\. VernadePrior\-dependent allocations for bayesian fixed\-budget best\-arm identification in structured bandits\.InProceedings of The 28th International Conference on Artificial Intelligence and Statistics,Y\. Li, S\. Mandt, S\. Agrawal, and E\. Khan \(Eds\.\),Proceedings of Machine Learning Research, Vol\.258,pp\. 379–387\.External Links:[Link](https://proceedings.mlr.press/v258/nguyen25a.html)Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1),[§1](https://arxiv.org/html/2610.20997#S1.p3.1)\.
- O’Haganet al\.\(2005\)A\. O’Hagan, J\. W\. Stevens, and M\. J\. CampbellAssurance in clinical trial design\.Pharmaceutical Statistics: The Journal of Applied Statistics in the Pharmaceutical Industry4\(3\),pp\. 187–201\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p6.1)\.
- Reverdyet al\.\(2016\)P\. Reverdy, V\. Srivastava, and N\. E\. LeonardSatisficing in multi\-armed bandit problems\.IEEE Transactions on Automatic Control62\(8\),pp\. 3788–3803\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p5.1),[§1](https://arxiv.org/html/2610.20997#S1.p4.1)\.
- Russo and Roy \(2014\)D\. Russo and B\. V\. RoyLearning to Optimize via Posterior Sampling\.Mathematics of Operations Research39\(4\),pp\. 1221–1243\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1)\.
- Russo \(2020\)D\. RussoSimple bayesian algorithms for best\-arm identification\.Operations Research68\(6\),pp\. 1625–1647\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1),[§1](https://arxiv.org/html/2610.20997#S1.p3.1)\.
- Shanget al\.\(2020\)X\. Shang, R\. de Heide, P\. Menard, E\. Kaufmann, and M\. ValkoFixed\-confidence guarantees for Bayesian best\-arm identification\.InProceedings of the International Conference on Artificial Intelligence and Statistics \(AISTATS\),pp\. 1823–1832\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1),[§1](https://arxiv.org/html/2610.20997#S1.p3.1)\.
- Tabataet al\.\(2020\)K\. Tabata, A\. Nakamura, J\. Honda, and T\. KomatsuzakiA bad arm existence checking problem: how to utilize asymmetric problem structure?\.Machine learning109\(2\),pp\. 327–372\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p2.1),[Appendix A](https://arxiv.org/html/2610.20997#A1.p3.1)\.
- Thompson \(1933\)W\. R\. ThompsonOn the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples\.Biometrika25\(3/4\),pp\. 285\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p4.1)\.
- Villaret al\.\(2015\)S\. S\. Villar, J\. Bowden, and J\. WasonMulti\-armed bandit models for the optimal design of clinical trials: benefits and challenges\.Statistical science: a review journal of the Institute of Mathematical Statistics30\(2\),pp\. 199\.Cited by:[§7](https://arxiv.org/html/2610.20997#S7.p5.1)\.
- Zhanget al\.\(2026\)Q\. Zhang, T\. Fiez, Y\. Liu, and W\. LiuMulti\-metric adaptive experimental design under a fixed budget with validation\.InProceedings of The 29th International Conference on Artificial Intelligence and Statistics,E\. Khan, Y\. Li, A\. Solin, and A\. Ramdas \(Eds\.\),Proceedings of Machine Learning Research, Vol\.300,pp\. 2107–2115\.External Links:[Link](https://proceedings.mlr.press/v300/zhang26c.html)Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p6.1),[§1](https://arxiv.org/html/2610.20997#S1.p4.1)\.
- Zhaoet al\.\(2023\)Y\. Zhao, C\. Stephens, C\. Szepesvári, and K\. JunRevisiting simple regret: fast rates for returning a good arm\.Proceedings of the International Conference on Machine Learning \(ICML\)\.Cited by:[Appendix A](https://arxiv.org/html/2610.20997#A1.p1.1)\.

Supplementary Materials

## APPENDIX

### Appendix ARelated Work

Best\-arm identification\.Frequentist best\-arm identification \(BAI\) seeks an arm with the largest true mean\. Fixed\-budget methods minimize identification error under a prescribed sampling budget\([Audibert et al\., 2010](https://arxiv.org/html/2610.20997#bib.bib2);[Karnin et al\., 2013](https://arxiv.org/html/2610.20997#bib.bib5);[Carpentier and Locatelli, 2016](https://arxiv.org/html/2610.20997#bib.bib1)\), whereas fixed\-confidence methods minimize expected sample size subject to an identification\-error tolerance\([Kaufmann et al\., 2016](https://arxiv.org/html/2610.20997#bib.bib11);[Garivier and Kaufmann, 2016](https://arxiv.org/html/2610.20997#bib.bib8)\)\. Approximate identification and simple regret relax exact optimality\.[Zhao et al\. \(2023\)](https://arxiv.org/html/2610.20997#bib.bib13)analyze Sequential Halving for returning approximately optimal arms and obtaining small simple regret\. Elimination methods are not restricted to exact BAI, and their performance need be analyzed under the objective of interest\. Our comparisons evaluate uniform sampling and Sequential Halving directly under posterior success, using the same posterior updates and terminal recommendation rule as HTG, instead of transferring exact\-BAI guarantees\.

Thresholding and good\-arm identification\.Thresholding bandits classify arms relative to a prescribed threshold, allowing a specified precision around it\([Locatelli et al\., 2016](https://arxiv.org/html/2610.20997#bib.bib7)\)\. Good\-arm identification seeks one or more acceptable arms without requiring optimality\([Kano et al\., 2019](https://arxiv.org/html/2610.20997#bib.bib15);[Katz\-Samuels and Jamieson, 2020](https://arxiv.org/html/2610.20997#bib.bib10);[Jourdan et al\., 2026](https://arxiv.org/html/2610.20997#bib.bib16)\)\. The benefit of multiple acceptable arms is studied by[Katz\-Samuels and Jamieson \(2020\)](https://arxiv.org/html/2610.20997#bib.bib10)and, more generally, in pure exploration with multiple correct answers\([Degenne and Koolen, 2019](https://arxiv.org/html/2610.20997#bib.bib3)\)\. Related sequential tests determine whether any arm lies on a specified side of a threshold\([Kaufmann et al\., 2018](https://arxiv.org/html/2610.20997#bib.bib23);[Tabata et al\., 2020](https://arxiv.org/html/2610.20997#bib.bib22)\)\. These problems define correctness through the true means\. Our success event instead concerns terminal posterior evidence: a truly favorable recommendation can fail the credibility criterion, and an unfavorable recommendation can satisfy it\.

The connection to APGAI\.APGAI is an anytime good\-arm identification algorithm with fixed\-budget and fixed\-confidence guarantees\([Jourdan et al\., 2026](https://arxiv.org/html/2610.20997#bib.bib16)\)\. Its sampling index isNi​\(t\)​\(X¯i,Ni​\(t\)−θ\)\\sqrt\{N\_\{i\}\(t\)\}\(\\overline\{X\}\_\{i,N\_\{i\}\(t\)\}\-\\theta\), whereθ\\thetais the target threshold; the authors attribute this index to theAPTP\\mathrm\{APT\}\_\{\\mathrm\{P\}\}rule of[Tabata et al\. \(2020\)](https://arxiv.org/html/2610.20997#bib.bib22)\. At threshold zero, HTG’s flat\-prior score isZi,Ni​\(t\)=Ni​\(t\)​X¯i,Ni​\(t\)/σZ\_\{i,N\_\{i\}\(t\)\}=\\sqrt\{N\_\{i\}\(t\)\}\\,\\overline\{X\}\_\{i,N\_\{i\}\(t\)\}/\\sigma\. With common observation variance, these indices have the same maximizers for a given history\. The complete algorithms nevertheless differ: HTG uses a horizon\-dependent balanced allocation and halving phase before posterior\-greedy sampling, and evaluates a posterior certificate after exactly the prescribed budget\. All original arms remain eligible during its greedy phase and final recommendation\. Our contribution is HTG sampling strategy that combines balanced allocation, successive halving, and posterior\-greedy sampling, together with its guarantees for terminal posterior success\.

Bayesian bandits and best\-arm identification\.Posterior sampling originates with[Thompson \(1933\)](https://arxiv.org/html/2610.20997#bib.bib6)and has been extensively analyzed for cumulative regret\([Agrawal and Goyal, 2012](https://arxiv.org/html/2610.20997#bib.bib9);[Russo and Roy, 2014](https://arxiv.org/html/2610.20997#bib.bib12)\)\. For Bayesian BAI,[Russo \(2020\)](https://arxiv.org/html/2610.20997#bib.bib17)studies the asymptotic decay of posterior probability assigned to incorrect best\-arm identities, holding the true instance fixed\.[Shang et al\. \(2020\)](https://arxiv.org/html/2610.20997#bib.bib4)develop fixed\-confidence stopping and sample\-complexity guarantees for Bayesian sampling rules\. Bayesian fixed\-budget BAI instead evaluates best\-arm misidentification probability averaged over a prior on instances\([Atsidakou et al\., 2022](https://arxiv.org/html/2610.20997#bib.bib18);[Nguyen et al\., 2025](https://arxiv.org/html/2610.20997#bib.bib19)\); prior\-averaged fixed\-confidence guarantees are studied by[Jang et al\. \(2024\)](https://arxiv.org/html/2610.20997#bib.bib24)\. Recent work also permits abstention and controls incorrect non\-abstaining recommendations under an abstention budget\([Huang et al\., 2026](https://arxiv.org/html/2610.20997#bib.bib25)\)\. These criteria should be distinguished from our sampling probability of terminal posterior failure: we neither require identifying the best arm nor treat abstention as a separately budgeted outcome\.

Bayesian satisficing\.The\(M,δ\)\(M,\\delta\)\-satisficing formulation of[Reverdy et al\. \(2016\)](https://arxiv.org/html/2610.20997#bib.bib20)is a conceptual predecessor\. An arm is satisfactory if its mean exceeds a thresholdMM, and is regarded as sufficiently satisfactory when the current belief assigns probability at least1−δ1\-\\deltato this event\. The posterior criterion is related to ours\. The difference is the objective: their performance measure is cumulative satisficing regret over the sequence of decisions, whereas we ask only whether the recommended arm satisfies the posterior criterion at the end of a fixed sampling budget\.

Bayesian experimental design and probability of success\.Bayesian experimental design selects experiments by maximizing expected utility\([Chaloner and Verdinelli, 1995](https://arxiv.org/html/2610.20997#bib.bib26)\)\. If the utility is the indicator that a prescribed posterior criterion is satisfied, its expected utility is the prior\-averaged probability that the experiment achieves posterior success\. Related notions of assurance similarly evaluate, before an experiment, the probability that a specified success criterion will ultimately be met\([O’Hagan et al\., 2005](https://arxiv.org/html/2610.20997#bib.bib27)\)\.[Hagar and Stevens \(2025\)](https://arxiv.org/html/2610.20997#bib.bib14)study how posterior probabilities vary across repeated sampling under the assumed data\-generating model and use these sampling distributions to choose sample sizes and posterior decision thresholds\. Our contribution is not only the use of posterior\-probability success criteria, but the adaptive allocation of a fixed budget across multiple arms and instance\-dependent guarantees for achieving terminal posterior success\. A related fixed\-budget exploration–validation design adaptively selects a treatment and then uses a separate A/B test for validation\([Zhang et al\., 2026](https://arxiv.org/html/2610.20997#bib.bib21)\)\. In contrast, all observations collected by HTG contribute to the terminal posterior used to determine posterior success\.

### Appendix BGaussian posterior calculations

We derive the posterior quantities used in Section[3](https://arxiv.org/html/2610.20997#S3)\. Recall that

μi∼𝒩\(μ0,σ02\),Xi,s∣μi∼𝒩\(μi,σ2\),\\mu\_\{i\}\\sim\\mathcal\{N\}\(\\mu\_\{0\},\\sigma\_\{0\}^\{2\}\),\\qquad X\_\{i,s\}\\mid\\mu\_\{i\}\\sim\\mathcal\{N\}\(\\mu\_\{i\},\\sigma^\{2\}\),and defineλ:=σ2/σ02\\lambda\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sigma^\{2\}/\\sigma\_\{0\}^\{2\}\.

Consider any realized history in which armiihas been observednntimes, with observationsXi,1,…,Xi,nX\_\{i,1\},\\ldots,X\_\{i,n\}\. Since the sampling decisions depend only on previously observed data and internal randomization, the posterior update forμi\\mu\_\{i\}is proportional to its prior density times the likelihood of its observed rewards\. By Bayes’ rule,

p\(μi∣Xi,1:n\)∝exp\{−\(μi−μ0\)22​σ02−12​σ2∑s=1n\(Xi,s−μi\)2\}\.p\(\\mu\_\{i\}\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)\\propto\\exp\\left\\\{\-\\frac\{\(\\mu\_\{i\}\-\\mu\_\{0\}\)^\{2\}\}\{2\\sigma\_\{0\}^\{2\}\}\-\\frac\{1\}\{2\\sigma^\{2\}\}\\sum\_\{s=1\}^\{n\}\(X\_\{i,s\}\-\\mu\_\{i\}\)^\{2\}\\right\\\}\.Collecting the terms that depend onμi\\mu\_\{i\}gives

p\(μi∣Xi,1:n\)∝exp\{−n\+λ2​σ2\(μi−μ^i,n\)2\}\.p\(\\mu\_\{i\}\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)\\propto\\exp\\left\\\{\-\\frac\{n\+\\lambda\}\{2\\sigma^\{2\}\}\\left\(\\mu\_\{i\}\-\\widehat\{\\mu\}\_\{i,n\}\\right\)^\{2\}\\right\\\}\.Therefore,

μi∣Xi,1:n∼𝒩\(μ^i,n,σ2n\+λ\)\.\\mu\_\{i\}\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\\sim\\mathcal\{N\}\\left\(\\widehat\{\\mu\}\_\{i,n\},\\frac\{\\sigma^\{2\}\}\{n\+\\lambda\}\\right\)\.Writingσ^n:=σ/n\+λ\\widehat\{\\sigma\}\_\{n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sigma/\\sqrt\{n\+\\lambda\}, the posteriorZZ\-score is

Zi,n:=μ^i,nσ^n=λ​μ0\+n​X¯i,nσ​n\+λ\.Z\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{\\widehat\{\\mu\}\_\{i,n\}\}\{\\widehat\{\\sigma\}\_\{n\}\}=\\frac\{\\lambda\\mu\_\{0\}\+n\\overline\{X\}\_\{i,n\}\}\{\\sigma\\sqrt\{n\+\\lambda\}\}\.Hence,

ℙ\(μi\>0∣Xi,1:n\)=Φ\(Zi,n\)\.\\PP\(\\mu\_\{i\}\>0\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)=\\Phi\(Z\_\{i,n\}\)\.

### Appendix CProof of the Complexity Comparison

###### Proof of Lemma[1](https://arxiv.org/html/2610.20997#Thmlemma1)\.

For convenience, define

Hthr:=∑i=1Kσ2μi2,H2,cap:=max1≤r≤Kr​σ2max⁡\{μ⋆,μ⋆−μ\(r\)\}2,H\_\{\\mathrm\{thr\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\qquad H\_\{2,\\mathrm\{cap\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\_\{1\\leq r\\leq K\}\\frac\{r\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\\}^\{2\}\},so that

HHTG=min⁡\{Hthr,Hpos,Q​H2,cap\}\.H\_\{\\mathrm\{HTG\}\}=\\min\\\{H\_\{\\mathrm\{thr\}\},H\_\{\\mathrm\{pos\}\},QH\_\{2,\\mathrm\{cap\}\}\\\}\.
We first compareHcapH\_\{\\mathrm\{cap\}\}with the first and third terms above\. Since

max⁡\{μ⋆,μ⋆−μi\}≥\|μi\|\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{i\}\\\}\\geq\|\\mu\_\{i\}\|for everyii, with the conventionσ2/02=\+∞\\sigma^\{2\}/0^\{2\}=\+\\infty, we have

Hcap≤Hthr\.H\_\{\\mathrm\{cap\}\}\\leq H\_\{\\mathrm\{thr\}\}\.\(23\)
Next, let

ar:=σ2max⁡\{μ⋆,μ⋆−μ\(r\)\}2,r∈\[K\]\.a\_\{r\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\\}^\{2\}\},\\qquad r\\in\[K\]\.Sinceμ\(1\)≥⋯≥μ\(K\)\\mu\_\{\(1\)\}\\geq\\cdots\\geq\\mu\_\{\(K\)\}, the sequence\(ar\)r=1K\(a\_\{r\}\)\_\{r=1\}^\{K\}is nonincreasing\. Therefore,

H2,cap=max1≤r≤K⁡r​ar≤∑r=1Kar=Hcap\.H\_\{2,\\mathrm\{cap\}\}=\\max\_\{1\\leq r\\leq K\}ra\_\{r\}\\leq\\sum\_\{r=1\}^\{K\}a\_\{r\}=H\_\{\\mathrm\{cap\}\}\.Conversely,ar≤H2,cap/ra\_\{r\}\\leq H\_\{2,\\mathrm\{cap\}\}/rfor everyrr, and hence

Hcap=∑r=1Kar≤H2,cap​∑r=1K1r\.H\_\{\\mathrm\{cap\}\}=\\sum\_\{r=1\}^\{K\}a\_\{r\}\\leq H\_\{2,\\mathrm\{cap\}\}\\sum\_\{r=1\}^\{K\}\\frac\{1\}\{r\}\.Using

∑r=1K1r≤1\+log⁡K≤1\+log2⁡K≤Q,\\sum\_\{r=1\}^\{K\}\\frac\{1\}\{r\}\\leq 1\+\\log K\\leq 1\+\\log\_\{2\}K\\leq Q,whereQ=1\+⌈log2⁡K⌉Q=1\+\\lceil\\log\_\{2\}K\\rceil, we obtain

Hcap≤Q​H2,cap\.H\_\{\\mathrm\{cap\}\}\\leq QH\_\{2,\\mathrm\{cap\}\}\.\(24\)
Now,

Hcert=min⁡\{Hcap,Hpos\}\.H\_\{\\mathrm\{cert\}\}=\\min\\\{H\_\{\\mathrm\{cap\}\},H\_\{\\mathrm\{pos\}\}\\\}\.By \([23](https://arxiv.org/html/2610.20997#A3.E23)\) and \([24](https://arxiv.org/html/2610.20997#A3.E24)\),

Hcert≤Hthr,Hcert≤Hpos,Hcert≤Q​H2,cap\.H\_\{\\mathrm\{cert\}\}\\leq H\_\{\\mathrm\{thr\}\},\\qquad H\_\{\\mathrm\{cert\}\}\\leq H\_\{\\mathrm\{pos\}\},\\qquad H\_\{\\mathrm\{cert\}\}\\leq QH\_\{2,\\mathrm\{cap\}\}\.Therefore,

Hcert≤min⁡\{Hthr,Hpos,Q​H2,cap\}=HHTG\.H\_\{\\mathrm\{cert\}\}\\leq\\min\\\{H\_\{\\mathrm\{thr\}\},H\_\{\\mathrm\{pos\}\},QH\_\{2,\\mathrm\{cap\}\}\\\}=H\_\{\\mathrm\{HTG\}\}\.
For the reverse inequality, sinceH2,cap≤HcapH\_\{2,\\mathrm\{cap\}\}\\leq H\_\{\\mathrm\{cap\}\}andQ≥1Q\\geq 1,

HHTG≤Q​H2,cap≤Q​Hcap,H\_\{\\mathrm\{HTG\}\}\\leq QH\_\{2,\\mathrm\{cap\}\}\\leq QH\_\{\\mathrm\{cap\}\},while also

HHTG≤Hpos≤Q​Hpos\.H\_\{\\mathrm\{HTG\}\}\\leq H\_\{\\mathrm\{pos\}\}\\leq QH\_\{\\mathrm\{pos\}\}\.Hence

HHTG≤min⁡\{Q​Hcap,Q​Hpos\}=Q​Hcert\.H\_\{\\mathrm\{HTG\}\}\\leq\\min\\\{QH\_\{\\mathrm\{cap\}\},QH\_\{\\mathrm\{pos\}\}\\\}=QH\_\{\\mathrm\{cert\}\}\.
Combining the two bounds gives

Hcert≤HHTG≤Q​Hcert\.H\_\{\\mathrm\{cert\}\}\\leq H\_\{\\mathrm\{HTG\}\}\\leq QH\_\{\\mathrm\{cert\}\}\.∎

### Appendix DProof of the Finite\-Budget Guarantee for HTG

###### Proof of Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)\.

Fix a mean vectorμ\\muwithμ⋆\>0\\mu\_\{\\star\}\>0\. Throughout the proof, all complexities are evaluated at this fixed instance, and we abbreviateℙμHTG\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}byℙμ\\mathbb\{P\}\_\{\\mu\}\. We work with the independent potential\-observation sequences\(Xi,s\)s≥1\(X\_\{i,s\}\)\_\{s\\geq 1\}fori∈\[K\]i\\in\[K\], of which HTG reveals prefixes through its adaptive allocation\.

Let

𝒫:=\{i∈\[K\]:μi\>0\},𝒩:=\{i∈\[K\]:μi<0\},\\mathcal\{P\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\\{i\\in\[K\]\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\\\},\\qquad\\mathcal\{N\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\\{i\\in\[K\]\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}<0\\\},and recall that

m=\|𝒫\|,b0:=λ​\|μ0\|σ,c=2​z\+b0\.m=\|\\mathcal\{P\}\|,\\qquad b\_\{0\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{\\sqrt\{\\lambda\}\\,\|\\mu\_\{0\}\|\}\{\\sigma\},\\qquad c=\\sqrt\{2\}\\,z\+b\_\{0\}\.For convenience, define

Hthr:=∑i=1Kσ2μi2,H2,cap:=max1≤r≤Kr​σ2max⁡\{μ⋆,μ⋆−μ\(r\)\}2,H\_\{\\mathrm\{thr\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\qquad H\_\{2,\\mathrm\{cap\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\_\{1\\leq r\\leq K\}\\frac\{r\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\\}^\{2\}\},with the conventionσ2/02=\+∞\\sigma^\{2\}/0^\{2\}=\+\\infty, and write

h:=HHTG​\(μ\)=min⁡\{Hthr,Hpos,Q​H2,cap\}\.h\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=H\_\{\\mathrm\{HTG\}\}\(\\mu\)=\\min\\\{H\_\{\\mathrm\{thr\}\},H\_\{\\mathrm\{pos\}\},QH\_\{2,\\mathrm\{cap\}\}\\\}\.Sinceμ⋆\>0\\mu\_\{\\star\}\>0, we havem≥1m\\geq 1and0<h<∞0<h<\\infty\. The offset in \([10](https://arxiv.org/html/2610.20997#S4.E10)\) isT0=Tcut\+96​m​c2​hT\_\{0\}=T\_\{\\mathrm\{cut\}\}\+96mc^\{2\}h\.

IfT≤T0T\\leq T\_\{0\}, the right\-hand side of \([11](https://arxiv.org/html/2610.20997#S4.E11)\) equals one, so the claim is immediate\. We therefore assumeT\>T0≥TcutT\>T\_\{0\}\\geq T\_\{\\mathrm\{cut\}\}throughout the remainder of the proof\.

Step 1: Allocation bounds and a common concentration event\.

Letkℓ=\|Sℓ\|k\_\{\\ell\}=\|S\_\{\\ell\}\|andqℓq\_\{\\ell\}be the active\-set size and the additional per\-arm sample count at halving stageℓ\\ell\. SinceT≥Tcut=3​K​max⁡\{nλ,Q\}T\\geq T\_\{\\mathrm\{cut\}\}=3K\\max\\\{n\_\{\\lambda\},Q\\\}, the first\-stage count satisfies

n0:=q1=⌊T3​K⌋≥nλ=max⁡\{1,⌈λ⌉\}\.n\_\{0\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=q\_\{1\}=\\left\\lfloor\\frac\{T\}\{3K\}\\right\\rfloor\\geq n\_\{\\lambda\}=\\max\\\{1,\\lceil\\lambda\\rceil\\\}\.\(25\)Consequently, every arm has at leastn0≥λn\_\{0\}\\geq\\lambdaobservations after the first stage, and in particularNi​\(T\)≥n0N\_\{i\}\(T\)\\geq n\_\{0\}for everyii\.

The quantities inside the floors definingqℓq\_\{\\ell\}are at least one\. Using⌊x⌋≥x/2\\lfloor x\\rfloor\\geq x/2forx≥1x\\geq 1, we obtain

qℓ≥T6​Q​kℓ,ℓ=1,…,Q\.q\_\{\\ell\}\\geq\\frac\{T\}\{6Qk\_\{\\ell\}\},\\qquad\\ell=1,\\ldots,Q\.\(26\)Forℓ=1\\ell=1, this follows from the stronger inequalityq1≥T/\(6​K\)q\_\{1\}\\geq T/\(6K\)\.

The halving phase uses at mostT/3\+\(Q−1\)​T/\(3​Q\)<2​T/3T/3\+\(Q\-1\)T/\(3Q\)<2T/3observations\. Hence, ifGGdenotes the number of observations allocated during the final greedy phase, then

G≥T3\.G\\geq\\frac\{T\}\{3\}\.\(27\)
For each arm and deterministic sample count, define

Wi,n:=1σ​∑s=1n\(Xi,s−μi\),n≥1,W\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{1\}\{\\sigma\}\\sum\_\{s=1\}^\{n\}\(X\_\{i,s\}\-\\mu\_\{i\}\),\\qquad n\\geq 1,and setWi,0=0W\_\{i,0\}=0\. Underℙμ\\mathbb\{P\}\_\{\\mu\}, each\(Wi,n\)n≥0\(W\_\{i,n\}\)\_\{n\\geq 0\}is a standard Gaussian random walk, and these walks are independent across arms\. ForR\>0R\>0, let

ℰT\(R\):=⋂i=1K⋂n=1T\{\|Wi,n\|≤Rn\}\.\\mathcal\{E\}\_\{T\}\(R\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\bigcap\_\{i=1\}^\{K\}\\bigcap\_\{n=1\}^\{T\}\\bigl\\\{\|W\_\{i,n\}\|\\leq R\\sqrt\{n\}\\bigr\\\}\.SinceWi,n/nW\_\{i,n\}/\\sqrt\{n\}is standard normal for each deterministic pair\(i,n\)\(i,n\), a Gaussian tail bound and a union bound give

ℙμ\(ℰT\(R\)c\)≤2KTexp\(−R2/2\)\.\\mathbb\{P\}\_\{\\mu\}\\bigl\(\\mathcal\{E\}\_\{T\}\(R\)^\{c\}\\bigr\)\\leq 2KT\\exp\(\-R^\{2\}/2\)\.\(28\)
Write

ai​\(n\):=n​μi\+λ​μ0σ​n\+λ,Zi,n=ai​\(n\)\+Wi,nn\+λ\.a\_\{i\}\(n\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{n\\mu\_\{i\}\+\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\+\\lambda\}\},\\qquad Z\_\{i,n\}=a\_\{i\}\(n\)\+\\frac\{W\_\{i,n\}\}\{\\sqrt\{n\+\\lambda\}\}\.OnℰT​\(R\)\\mathcal\{E\}\_\{T\}\(R\), simultaneously for alli∈\[K\]i\\in\[K\]and1≤n≤T1\\leq n\\leq T,

\|X¯i,n−μi\|≤σ​Rn,\|Zi,n−ai​\(n\)\|≤R\.\|\\overline\{X\}\_\{i,n\}\-\\mu\_\{i\}\|\\leq\\frac\{\\sigma R\}\{\\sqrt\{n\}\},\\qquad\|Z\_\{i,n\}\-a\_\{i\}\(n\)\|\\leq R\.\(29\)Because these inequalities hold at every deterministic count, they also hold at every adaptive count encountered by HTG\. No conditioning on an adaptive sample count is needed\.

Step 2: Terminal failure bounds positive\-arm sample counts\.

FixR\>0R\>0and work onℰT​\(R\)∩SuccTc\\mathcal\{E\}\_\{T\}\(R\)\\cap\\mathrm\{Succ\}\_\{T\}^\{c\}for this step and the next two steps\. By the terminal recommendation rule,

SuccTc=\{maxi∈\[K\]Zi,Ni​\(T\)<z\}\.\\mathrm\{Succ\}\_\{T\}^\{c\}=\\left\\\{\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}<z\\right\\\}\.Leti∈𝒫i\\in\\mathcal\{P\}and putn=Ni​\(T\)n=N\_\{i\}\(T\)\. Thenn≥n0≥λn\\geq n\_\{0\}\\geq\\lambdaandZi,n<zZ\_\{i,n\}<z\. UsingWi,n≥−R​nW\_\{i,n\}\\geq\-R\\sqrt\{n\}gives

μiσ​n<R\+z​1\+λn−λ​μ0σ​n\.\\frac\{\\mu\_\{i\}\}\{\\sigma\}\\sqrt\{n\}<R\+z\\sqrt\{1\+\\frac\{\\lambda\}\{n\}\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\}\}\.Sincen≥λn\\geq\\lambda,

z​1\+λn≤2​z,\|λ​μ0σ​n\|≤b0\.z\\sqrt\{1\+\\frac\{\\lambda\}\{n\}\}\\leq\\sqrt\{2\}\\,z,\\qquad\\left\|\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\}\}\\right\|\\leq b\_\{0\}\.Therefore,

Ni​\(T\)≤σ2​\(R\+c\)2μi2,i∈𝒫\.N\_\{i\}\(T\)\\leq\\frac\{\\sigma^\{2\}\(R\+c\)^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\qquad i\\in\\mathcal\{P\}\.\(30\)This implication uses failure at the terminal time\. It does not assume that a certificate obtained earlier remains valid after further observations\.

Step 3: The greedy\-phase bound\.

For this step, supposeHthr<∞H\_\{\\mathrm\{thr\}\}<\\infty, so that no arm has zero mean\. LetGiG\_\{i\}denote the number of observations allocated to armiiduring the final greedy phase\. Thus,G=∑i=1KGiG=\\sum\_\{i=1\}^\{K\}G\_\{i\}\. For each positive arm,

Gi≤Ni​\(T\)≤σ2​\(R\+c\)2μi2,i∈𝒫\.G\_\{i\}\\leq N\_\{i\}\(T\)\\leq\\frac\{\\sigma^\{2\}\(R\+c\)^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\qquad i\\in\\mathcal\{P\}\.\(31\)
To bound the greedy selections of negative arms, choose any fixedp∈𝒫p\\in\\mathcal\{P\}\. For everyn≥1n\\geq 1,

ap​\(n\)=n​μp\+λ​μ0σ​n\+λ≥−b0\.a\_\{p\}\(n\)=\\frac\{n\\mu\_\{p\}\+\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\+\\lambda\}\}\\geq\-b\_\{0\}\.It follows from \([29](https://arxiv.org/html/2610.20997#A4.E29)\) that at every greedy decision timett,

Zp,Np​\(t\)≥−b0−R\.Z\_\{p,N\_\{p\}\(t\)\}\\geq\-b\_\{0\}\-R\.
Suppose that a negative armjjis selected at such a time, and writen=Nj​\(t\)n=N\_\{j\}\(t\)for its count before the observation\. Since the greedy rule maximizes the posteriorZZ\-score over allKKarms,

aj​\(n\)\+R≥Zj,n≥Zp,Np​\(t\)≥−b0−R\.a\_\{j\}\(n\)\+R\\geq Z\_\{j,n\}\\geq Z\_\{p,N\_\{p\}\(t\)\}\\geq\-b\_\{0\}\-R\.Henceaj​\(n\)≥−b0−2​Ra\_\{j\}\(n\)\\geq\-b\_\{0\}\-2R\. On the other hand,n≥n0≥λn\\geq n\_\{0\}\\geq\\lambdaandμj<0\\mu\_\{j\}<0imply

aj​\(n\)≤−\|μj\|σ​n2\+b0\.a\_\{j\}\(n\)\\leq\-\\frac\{\|\\mu\_\{j\}\|\}\{\\sigma\}\\sqrt\{\\frac\{n\}\{2\}\}\+b\_\{0\}\.Combining these inequalities yields

n≤8​σ2​\(R\+b0\)2μj2\.n\\leq\\frac\{8\\sigma^\{2\}\(R\+b\_\{0\}\)^\{2\}\}\{\\mu\_\{j\}^\{2\}\}\.
Before itsgg\-th greedy selection, armjjhas at leastn0\+g−1≥gn\_\{0\}\+g\-1\\geq gobservations\. Applying the preceding bound at its last greedy selection, and usingb0≤cb\_\{0\}\\leq c, gives

Gj≤8​σ2​\(R\+c\)2μj2,j∈𝒩\.G\_\{j\}\\leq\\frac\{8\\sigma^\{2\}\(R\+c\)^\{2\}\}\{\\mu\_\{j\}^\{2\}\},\\qquad j\\in\\mathcal\{N\}\.\(32\)The same inequality holds trivially whenGj=0G\_\{j\}=0\.

Summing \([31](https://arxiv.org/html/2610.20997#A4.E31)\) and \([32](https://arxiv.org/html/2610.20997#A4.E32)\), we obtain

G≤8​Hthr​\(R\+c\)2\.G\\leq 8H\_\{\\mathrm\{thr\}\}\(R\+c\)^\{2\}\.Together with \([27](https://arxiv.org/html/2610.20997#A4.E27)\), this proves

ℰT​\(R\)∩SuccTc\\displaystyle\\mathcal\{E\}\_\{T\}\(R\)\\cap\\mathrm\{Succ\}\_\{T\}^\{c\}\(33\)⟹T≤24​Hthr​\(R\+c\)2\.\\displaystyle\\Longrightarrow\\quad T\\leq 24H\_\{\\mathrm\{thr\}\}\(R\+c\)^\{2\}\.When some arm has zero mean,Hthr=\+∞H\_\{\\mathrm\{thr\}\}=\+\\infty, and this branch is not needed\.

Step 4: The halving\-phase bound\.

Fix a best armi⋆i\_\{\\star\}withμi⋆=μ⋆\\mu\_\{i\_\{\\star\}\}=\\mu\_\{\\star\}, assigning it rank one when ordering arms with equal means\. At the end of each halving stage, all active arms have the same total sample count\. Since the prior parameters are common across arms, their ordering by posteriorZZ\-score is therefore the same as their ordering by empirical mean\.

First suppose thati⋆i\_\{\\star\}is removed at some halving stageℓ\\ell\. Writes=kℓs=k\_\{\\ell\}for the number of active arms, and let

k:=⌈s/2⌉,r:=k\+1\.k\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\lceil s/2\\rceil,\\qquad r\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=k\+1\.Letnnbe the common sample count of the active arms at the end of that stage\. By \([26](https://arxiv.org/html/2610.20997#A4.E26)\),

n≥qℓ≥T6​Q​s\.n\\geq q\_\{\\ell\}\\geq\\frac\{T\}\{6Qs\}\.\(34\)
Thekkretained arms all have empirical means at least as large as that ofi⋆i\_\{\\star\}\. Since none of them isi⋆i\_\{\\star\}, at least one retained armjjhas global rank at leastrr\. In particular,μj≤μ\(r\)\\mu\_\{j\}\\leq\\mu\_\{\(r\)\}andX¯j,n≥X¯i⋆,n\\overline\{X\}\_\{j,n\}\\geq\\overline\{X\}\_\{i\_\{\\star\},n\}\. By \([29](https://arxiv.org/html/2610.20997#A4.E29)\),

μ⋆−μ\(r\)≤μ⋆−μj≤2​σ​Rn\.\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\leq\\mu\_\{\\star\}\-\\mu\_\{j\}\\leq\\frac\{2\\sigma R\}\{\\sqrt\{n\}\}\.Consequently,

n​\(μ⋆−μ\(r\)\)2≤4​σ2​R2\.n\(\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\)^\{2\}\\leq 4\\sigma^\{2\}R^\{2\}\.Also,n≤Ni⋆​\(T\)n\\leq N\_\{i\_\{\\star\}\}\(T\), so \([30](https://arxiv.org/html/2610.20997#A4.E30)\) gives

n​μ⋆2≤σ2​\(R\+c\)2\.n\\mu\_\{\\star\}^\{2\}\\leq\\sigma^\{2\}\(R\+c\)^\{2\}\.Writingγ\(r\):=max⁡\{μ⋆,μ⋆−μ\(r\)\}\\gamma\_\{\(r\)\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\\}, we conclude that

n​γ\(r\)2≤4​σ2​\(R\+c\)2\.n\\gamma\_\{\(r\)\}^\{2\}\\leq 4\\sigma^\{2\}\(R\+c\)^\{2\}\.Combining this with \([34](https://arxiv.org/html/2610.20997#A4.E34)\) ands≤2​rs\\leq 2ryields

T\\displaystyle T≤24​Q​s​σ2γ\(r\)2​\(R\+c\)2\\displaystyle\\leq 24Qs\\frac\{\\sigma^\{2\}\}\{\\gamma\_\{\(r\)\}^\{2\}\}\(R\+c\)^\{2\}≤48​Q​r​σ2γ\(r\)2​\(R\+c\)2\\displaystyle\\leq 48Q\\frac\{r\\sigma^\{2\}\}\{\\gamma\_\{\(r\)\}^\{2\}\}\(R\+c\)^\{2\}≤48​Q​H2,cap​\(R\+c\)2\.\\displaystyle\\leq 48QH\_\{2,\\mathrm\{cap\}\}\(R\+c\)^\{2\}\.
Next suppose thati⋆i\_\{\\star\}is never removed\. AfterQ−1Q\-1halvings the active set is a singleton, soi⋆i\_\{\\star\}receives the final\-stage samples\. By \([26](https://arxiv.org/html/2610.20997#A4.E26)\),

Ni⋆​\(T\)≥qQ≥T6​Q\.N\_\{i\_\{\\star\}\}\(T\)\\geq q\_\{Q\}\\geq\\frac\{T\}\{6Q\}\.This also holds whenK=1K=1, in which caseQ=1Q=1and the first stage is already a singleton stage\. Applying \([30](https://arxiv.org/html/2610.20997#A4.E30)\) gives

T≤6​Q​σ2μ⋆2​\(R\+c\)2≤6​Q​H2,cap​\(R\+c\)2\.T\\leq 6Q\\frac\{\\sigma^\{2\}\}\{\\mu\_\{\\star\}^\{2\}\}\(R\+c\)^\{2\}\\leq 6QH\_\{2,\\mathrm\{cap\}\}\(R\+c\)^\{2\}\.
Thus, in both cases,

ℰT​\(R\)∩SuccTc\\displaystyle\\mathcal\{E\}\_\{T\}\(R\)\\cap\\mathrm\{Succ\}\_\{T\}^\{c\}\(35\)⟹T≤48​Q​H2,cap​\(R\+c\)2\.\\displaystyle\\Longrightarrow\\quad T\\leq 48QH\_\{2,\\mathrm\{cap\}\}\(R\+c\)^\{2\}\.This argument allows zero means among the competing arms\.

Step 5: The positive\-arm bound\.

This step does not condition onℰT​\(R\)\\mathcal\{E\}\_\{T\}\(R\)\. Instead, we use the deterministic lower boundNi​\(T\)≥n0N\_\{i\}\(T\)\\geq n\_\{0\}from \([25](https://arxiv.org/html/2610.20997#A4.E25)\) and an armwise crossing argument\.

Fixi∈𝒫i\\in\\mathcal\{P\}and writeui:=μi/σ\>0u\_\{i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mu\_\{i\}/\\sigma\>0\. For everyn≥n0≥λn\\geq n\_\{0\}\\geq\\lambda,

Zi,n<z\\displaystyle Z\_\{i,n\}<z⟹Wi,n<z​n\+λ−ui​n−λ​μ0σ\\displaystyle\\Longrightarrow W\_\{i,n\}<z\\sqrt\{n\+\\lambda\}\-u\_\{i\}n\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\}⟹Wi,n<c​n−ui​n\.\\displaystyle\\Longrightarrow W\_\{i,n\}<c\\sqrt\{n\}\-u\_\{i\}n\.Define

Mi,n:=exp⁡\(−ui2​Wi,n−ui2​n8\),n≥0\.M\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\exp\\left\(\-\\frac\{u\_\{i\}\}\{2\}W\_\{i,n\}\-\\frac\{u\_\{i\}^\{2\}n\}\{8\}\\right\),\\qquad n\\geq 0\.The Gaussian increments ofWi,nW\_\{i,n\}imply that\(Mi,n\)n≥0\(M\_\{i,n\}\)\_\{n\\geq 0\}is a nonnegative mean\-one martingale with respect to the armwise observation filtration, withMi,0=1M\_\{i,0\}=1\.

Whenevern≥n0n\\geq n\_\{0\}andZi,n<zZ\_\{i,n\}<z, we have

log⁡Mi,n\\displaystyle\\log M\_\{i,n\}\>3​ui2​n8−ui​c​n2\\displaystyle\>\\frac\{3u\_\{i\}^\{2\}n\}\{8\}\-\\frac\{u\_\{i\}c\\sqrt\{n\}\}\{2\}≥ui2​n4−c22\\displaystyle\\geq\\frac\{u\_\{i\}^\{2\}n\}\{4\}\-\\frac\{c^\{2\}\}\{2\}≥ui2​n04−c22\.\\displaystyle\\geq\\frac\{u\_\{i\}^\{2\}n\_\{0\}\}\{4\}\-\\frac\{c^\{2\}\}\{2\}\.The middle inequality follows from\(ui​n−2​c\)2≥0\(u\_\{i\}\\sqrt\{n\}\-2c\)^\{2\}\\geq 0\.

For completeness, the maximal inequality used here follows by stoppingMi,nM\_\{i,n\}atτa:=inf\{n≥0:Mi,n≥a\}\\tau\_\{a\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\inf\\\{n\\geq 0\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}M\_\{i,n\}\\geq a\\\}, wherea\>0a\>0\. For every deterministic integerL≥0L\\geq 0, bounded stopping and nonnegativity give

a​ℙμ​\(τa≤L\)≤𝔼μ​\[Mi,τa∧L\]=1\.a\\,\\mathbb\{P\}\_\{\\mu\}\(\\tau\_\{a\}\\leq L\)\\leq\\mathbb\{E\}\_\{\\mu\}\[M\_\{i,\\tau\_\{a\}\\wedge L\}\]=1\.LettingL→∞L\\to\\inftyyieldsℙμ​\(τa<∞\)≤min⁡\{1,a−1\}\\mathbb\{P\}\_\{\\mu\}\(\\tau\_\{a\}<\\infty\)\\leq\\min\\\{1,a^\{\-1\}\\\}\. Applying this witha=exp⁡\(ui2​n0/4−c2/2\)a=\\exp\(u\_\{i\}^\{2\}n\_\{0\}/4\-c^\{2\}/2\)gives

ℙμ​\(∃n≥n0:Zi,n<z\)\\displaystyle\\mathbb\{P\}\_\{\\mu\}\\bigl\(\\exists n\\geq n\_\{0\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}Z\_\{i,n\}<z\\bigr\)\(36\)≤min⁡\{1,exp⁡\(c22−ui2​n04\)\}\.\\displaystyle\\leq\\min\\left\\\{1,\\,\\exp\\left\(\\frac\{c^\{2\}\}\{2\}\-\\frac\{u\_\{i\}^\{2\}n\_\{0\}\}\{4\}\\right\)\\right\\\}\.
For eachi∈𝒫i\\in\\mathcal\{P\}, letBi:=\{∃n≥n0:Zi,n<z\}B\_\{i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\\{\\exists n\\geq n\_\{0\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}Z\_\{i,n\}<z\\\}\. SinceNi​\(T\)≥n0N\_\{i\}\(T\)\\geq n\_\{0\}, terminal failure implies

SuccTc⊆⋂i∈𝒫Bi\.\\mathrm\{Succ\}\_\{T\}^\{c\}\\subseteq\\bigcap\_\{i\\in\\mathcal\{P\}\}B\_\{i\}\.Each eventBiB\_\{i\}depends only on armii’s potential\-observation sequence\. These events are therefore independent across arms, even though the terminal countsNi​\(T\)N\_\{i\}\(T\)need not be independent\. Using \([36](https://arxiv.org/html/2610.20997#A4.E36)\), we obtain

ℙμ​\(SuccTc\)\\displaystyle\\mathbb\{P\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)≤∏i∈𝒫ℙμ​\(Bi\)\\displaystyle\\leq\\prod\_\{i\\in\\mathcal\{P\}\}\\mathbb\{P\}\_\{\\mu\}\(B\_\{i\}\)≤exp⁡\(m​c22−n04​∑i∈𝒫μi2σ2\)\.\\displaystyle\\leq\\exp\\left\(\\frac\{mc^\{2\}\}\{2\}\-\\frac\{n\_\{0\}\}\{4\}\\sum\_\{i\\in\\mathcal\{P\}\}\\frac\{\\mu\_\{i\}^\{2\}\}\{\\sigma^\{2\}\}\\right\)\.By the definition ofHposH\_\{\\mathrm\{pos\}\},

∑i∈𝒫μi2σ2=KHpos\.\\sum\_\{i\\in\\mathcal\{P\}\}\\frac\{\\mu\_\{i\}^\{2\}\}\{\\sigma^\{2\}\}=\\frac\{K\}\{H\_\{\\mathrm\{pos\}\}\}\.Sincen0=⌊T/\(3​K\)⌋≥T/\(3​K\)−1n\_\{0\}=\\lfloor T/\(3K\)\\rfloor\\geq T/\(3K\)\-1, it follows that

ℙμ​\(SuccTc\)\\displaystyle\\mathbb\{P\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\(37\)≤min⁡\{1,exp⁡\(m​c22−T−3​K12​Hpos\)\}\.\\displaystyle\\leq\\min\\left\\\{1,\\,\\exp\\left\(\\frac\{mc^\{2\}\}\{2\}\-\\frac\{T\-3K\}\{12H\_\{\\mathrm\{pos\}\}\}\\right\)\\right\\\}\.
Step 6: Combining the three bounds\.

Recall thath=min⁡\{Hthr,Hpos,Q​H2,cap\}h=\\min\\\{H\_\{\\mathrm\{thr\}\},H\_\{\\mathrm\{pos\}\},QH\_\{2,\\mathrm\{cap\}\}\\\}and that we are consideringT\>T0T\>T\_\{0\}\.

First suppose thath=Hthrh=H\_\{\\mathrm\{thr\}\}orh=Q​H2,caph=QH\_\{2,\\mathrm\{cap\}\}\. In the former caseHthr<∞H\_\{\\mathrm\{thr\}\}<\\infty, so the greedy\-phase argument applies\. By \([33](https://arxiv.org/html/2610.20997#A4.E33)\) or \([35](https://arxiv.org/html/2610.20997#A4.E35)\), respectively,

ℰT​\(R\)∩SuccTc⟹T≤48​h​\(R\+c\)2\.\\mathcal\{E\}\_\{T\}\(R\)\\cap\\mathrm\{Succ\}\_\{T\}^\{c\}\\quad\\Longrightarrow\\quad T\\leq 48h\(R\+c\)^\{2\}\.Using\(R\+c\)2≤2​R2\+2​c2\(R\+c\)^\{2\}\\leq 2R^\{2\}\+2c^\{2\}andm≥1m\\geq 1gives

T≤96​h​R2\+96​h​c2≤96​h​R2\+T0\.T\\leq 96hR^\{2\}\+96hc^\{2\}\\leq 96hR^\{2\}\+T\_\{0\}\.Therefore, for every radius satisfying

0<R<T−T096​h,0<R<\\sqrt\{\\frac\{T\-T\_\{0\}\}\{96h\}\},the eventℰT​\(R\)∩SuccTc\\mathcal\{E\}\_\{T\}\(R\)\\cap\\mathrm\{Succ\}\_\{T\}^\{c\}is empty\. By \([28](https://arxiv.org/html/2610.20997#A4.E28)\),

ℙμ\(SuccTc\)≤2KTexp\(−R2/2\)\.\\mathbb\{P\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\leq 2KT\\exp\(\-R^\{2\}/2\)\.Taking the infimum over these radii yields

ℙμ​\(SuccTc\)≤2​K​T​exp⁡\(−T−T0192​h\)\.\\mathbb\{P\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\leq 2KT\\exp\\left\(\-\\frac\{T\-T\_\{0\}\}\{192h\}\\right\)\.\(38\)
It remains to considerh=Hposh=H\_\{\\mathrm\{pos\}\}\. SinceTcut≥3​KT\_\{\\mathrm\{cut\}\}\\geq 3K,

T0=Tcut\+96​m​c2​h≥3​K\+6​m​c2​h\.T\_\{0\}=T\_\{\\mathrm\{cut\}\}\+96mc^\{2\}h\\geq 3K\+6mc^\{2\}h\.Consequently, \([37](https://arxiv.org/html/2610.20997#A4.E37)\) gives

ℙμ​\(SuccTc\)\\displaystyle\\mathbb\{P\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)≤exp⁡\(m​c22−T−3​K12​h\)\\displaystyle\\leq\\exp\\left\(\\frac\{mc^\{2\}\}\{2\}\-\\frac\{T\-3K\}\{12h\}\\right\)=exp⁡\(−T−\(3​K\+6​m​c2​h\)12​h\)\\displaystyle=\\exp\\left\(\-\\frac\{T\-\(3K\+6mc^\{2\}h\)\}\{12h\}\\right\)≤exp⁡\(−T−T012​h\)\\displaystyle\\leq\\exp\\left\(\-\\frac\{T\-T\_\{0\}\}\{12h\}\\right\)≤2​K​T​exp⁡\(−T−T0192​h\)\.\\displaystyle\\leq 2KT\\exp\\left\(\-\\frac\{T\-T\_\{0\}\}\{192h\}\\right\)\.Thus \([38](https://arxiv.org/html/2610.20997#A4.E38)\) holds regardless of which term attains the minimum defininghh\.

Finally, combining this bound with the trivial bound by one and the caseT≤T0T\\leq T\_\{0\}treated at the start, we obtain

ℙμHTG​\(SuccTc\)≤min⁡\{1,2​K​T​exp⁡\(−\(T−T0\)\+192​HHTG​\(μ\)\)\},\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\leq\\min\\left\\\{1,\\,2KT\\exp\\left\(\-\\frac\{\(T\-T\_\{0\}\)\_\{\+\}\}\{192H\_\{\\mathrm\{HTG\}\}\(\\mu\)\}\\right\)\\right\\\},as claimed\. ∎

### Appendix EAn Explicit Sufficient Budget

The sufficient\-budget condition in \([12](https://arxiv.org/html/2610.20997#S4.E12)\) containsTTinside the logarithm\. The following consequence of Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)gives an explicit sufficient budget without this dependence\.

###### Corollary 1\(Explicit sufficient budget\)\.

Under the assumptions of Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1), fix a target failure probabilityη∈\(0,1\)\\eta\\in\(0,1\)and writeh:=HHTG​\(μ\)h\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=H\_\{\\mathrm\{HTG\}\}\(\\mu\)\. Define

Lη\\displaystyle L\_\{\\eta\}:=log\(max\{e,768​K​hη\}\),\\displaystyle\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\log\\left\(\\max\\left\\\{e,\\frac\{768Kh\}\{\\eta\}\\right\\\}\\right\),\(39\)Tη\\displaystyle T\_\{\\eta\}:=⌈max\{2T0,768hLη\}⌉,\\displaystyle\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\left\\lceil\\max\\left\\\{2T\_\{0\},\\;768hL\_\{\\eta\}\\right\\\}\\right\\rceil,whereT0T\_\{0\}is defined in \([10](https://arxiv.org/html/2610.20997#S4.E10)\) andlog\\logdenotes the natural logarithm\. Then, for every integerT≥TηT\\geq T\_\{\\eta\},

ℙμHTG​\(SuccTc\)≤η\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\eta\.

###### Proof\.

Sinceμ⋆\>0\\mu\_\{\\star\}\>0, we have0<h<∞0<h<\\infty\. Moreover,T0≥Tcut≥3​KT\_\{0\}\\geq T\_\{\\mathrm\{cut\}\}\\geq 3K, soT≥TηT\\geq T\_\{\\eta\}impliesT≥2​T0≥KT\\geq 2T\_\{0\}\\geq K\. In particular,T−T0≥T/2T\-T\_\{0\}\\geq T/2, and Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)gives

ℙμHTG​\(SuccTc\)≤2​K​T​exp⁡\(−T384​h\)\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq 2KT\\exp\\left\(\-\\frac\{T\}\{384h\}\\right\)\.\(40\)
Setx:=T/\(384​h\)x\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=T/\(384h\)\. The second condition in the definition ofTηT\_\{\\eta\}ensures that

x≥2​Lη≥2\.x\\geq 2L\_\{\\eta\}\\geq 2\.Forx≥2x\\geq 2, the elementary inequalitylog⁡x≤x/2\\log x\\leq x/2holds\. Also, by the definition ofLηL\_\{\\eta\},log⁡\(768​K​h/η\)≤Lη\\log\(768Kh/\\eta\)\\leq L\_\{\\eta\}\. Consequently,

log⁡2​K​Tη\\displaystyle\\log\\frac\{2KT\}\{\\eta\}=log⁡768​K​hη\+log⁡x\\displaystyle=\\log\\frac\{768Kh\}\{\\eta\}\+\\log x≤Lη\+x2\\displaystyle\\leq L\_\{\\eta\}\+\\frac\{x\}\{2\}≤x\.\\displaystyle\\leq x\.It follows that

2​K​T​exp⁡\(−T384​h\)=2​K​T​e−x≤η\.2KT\\exp\\left\(\-\\frac\{T\}\{384h\}\\right\)=2KTe^\{\-x\}\\leq\\eta\.Combining this inequality with \([40](https://arxiv.org/html/2610.20997#A5.E40)\) proves the claim\. ∎

### Appendix FIllustrative Instance Calculations

We give the calculations underlying the examples in Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3), followed by an additional example illustrating the effect of a competing arm whose mean is close to zero\. Throughout this appendix, the best mean isa\>0a\>0, and we writeh:=σ2/a2h\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sigma^\{2\}/a^\{2\}\. We suppress the instance argumentμ\\muin the complexities when there is no ambiguity\.

For convenience, define

Hthr:=∑i=1Kσ2μi2,H2,cap:=max1≤r≤Kr​σ2max⁡\{μ⋆,μ⋆−μ\(r\)\}2\.H\_\{\\mathrm\{thr\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\qquad H\_\{2,\\mathrm\{cap\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\max\_\{1\\leq r\\leq K\}\\frac\{r\\sigma^\{2\}\}\{\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{\(r\)\}\\\}^\{2\}\}\.Thus,

HHTG=min⁡\{Hthr,Hpos,Q​H2,cap\},H\_\{\\mathrm\{HTG\}\}=\\min\\\{H\_\{\\mathrm\{thr\}\},H\_\{\\mathrm\{pos\}\},QH\_\{2,\\mathrm\{cap\}\}\\\},whereQ=1\+⌈log2⁡K⌉Q=1\+\\lceil\\log\_\{2\}K\\rceilandσ2/02:=\+∞\\sigma^\{2\}/0^\{2\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\+\\infty\.

#### F\.1One positive arm with other arms strongly negative

LetK≥2K\\geq 2and considerμ1=a\>0\\mu\_\{1\}=a\>0andμ2=⋯=μK=−b\\mu\_\{2\}=\\cdots=\\mu\_\{K\}=\-b, whereb≥a​Kb\\geq a\\sqrt\{K\}\. Directly from the definitions,

Hcap=h\+\(K−1\)​σ2\(a\+b\)2,Hpos=K​h\.H\_\{\\mathrm\{cap\}\}=h\+\\frac\{\(K\-1\)\\sigma^\{2\}\}\{\(a\+b\)^\{2\}\},\\qquad H\_\{\\mathrm\{pos\}\}=Kh\.Every summand ofHcapH\_\{\\mathrm\{cap\}\}is at mosthh, soHcap≤K​h=HposH\_\{\\mathrm\{cap\}\}\\leq Kh=H\_\{\\mathrm\{pos\}\}\. Therefore,

Hcert=Hcap=h\+\(K−1\)​σ2\(a\+b\)2\.H\_\{\\mathrm\{cert\}\}=H\_\{\\mathrm\{cap\}\}=h\+\\frac\{\(K\-1\)\\sigma^\{2\}\}\{\(a\+b\)^\{2\}\}\.\(41\)
To evaluateHHTGH\_\{\\mathrm\{HTG\}\}, first note that

Hthr=h\+\(K−1\)​σ2b2≤\(2−1K\)​h<2​h\.H\_\{\\mathrm\{thr\}\}=h\+\\frac\{\(K\-1\)\\sigma^\{2\}\}\{b^\{2\}\}\\leq\\left\(2\-\\frac\{1\}\{K\}\\right\)h<2h\.\(42\)The inequality usesb2≥K​a2b^\{2\}\\geq Ka^\{2\}\.

The best arm contributeshhto the rank\-weighted maximum definingH2,capH\_\{2,\\mathrm\{cap\}\}\. All other arms have the same denominator\(a\+b\)2\(a\+b\)^\{2\}, so their largest rank\-weighted contribution occurs at rankKK\. Hence

H2,cap=max⁡\{h,K​σ2\(a\+b\)2\}=h,H\_\{2,\\mathrm\{cap\}\}=\\max\\left\\\{h,\\frac\{K\\sigma^\{2\}\}\{\(a\+b\)^\{2\}\}\\right\\\}=h,where the last equality follows from\(a\+b\)2≥K​a2\(a\+b\)^\{2\}\\geq Ka^\{2\}\.

SinceK≥2K\\geq 2andQ≥2Q\\geq 2, we haveHpos=K​h≥2​hH\_\{\\mathrm\{pos\}\}=Kh\\geq 2handQ​H2,cap=Q​h≥2​hQH\_\{2,\\mathrm\{cap\}\}=Qh\\geq 2h\. Combining this with \([42](https://arxiv.org/html/2610.20997#A6.E42)\) shows that the first term attains the minimum definingHHTGH\_\{\\mathrm\{HTG\}\}:

HHTG=Hthr=h\+\(K−1\)​σ2b2\.H\_\{\\mathrm\{HTG\}\}=H\_\{\\mathrm\{thr\}\}=h\+\\frac\{\(K\-1\)\\sigma^\{2\}\}\{b^\{2\}\}\.\(43\)In particular,

h≤Hcert≤HHTG<2​h,Hpos=K​h\.h\\leq H\_\{\\mathrm\{cert\}\}\\leq H\_\{\\mathrm\{HTG\}\}<2h,\\qquad H\_\{\\mathrm\{pos\}\}=Kh\.\(44\)Thus bothHcertH\_\{\\mathrm\{cert\}\}andHHTGH\_\{\\mathrm\{HTG\}\}are within a factor of two ofσ2/a2\\sigma^\{2\}/a^\{2\}, while

K2≤HposHHTG≤K\.\\frac\{K\}\{2\}\\leq\\frac\{H\_\{\\mathrm\{pos\}\}\}\{H\_\{\\mathrm\{HTG\}\}\}\\leq K\.
This calculation also identifies the role of the final posterior\-greedy phase\. Its analysis supplies the termHthr<2​hH\_\{\\mathrm\{thr\}\}<2h, whereas the term supplied by the halving analysis isQ​hQh\. Including the posterior\-greedy phase therefore avoids the additional factorQQin the halving term on this family\.

#### F\.2Many positive arms

Supposeμ1=⋯=μK=a\>0\\mu\_\{1\}=\\cdots=\\mu\_\{K\}=a\>0\. Every best\-arm gap is zero, so each denominator inHcapH\_\{\\mathrm\{cap\}\}equalsa2a^\{2\}\. Also,∑i=1K\(μi\)\+2=K​a2\\sum\_\{i=1\}^\{K\}\(\\mu\_\{i\}\)\_\{\+\}^\{2\}=Ka^\{2\}\. Consequently,

Hcap=K​h,Hpos=h,Hcert=h\.H\_\{\\mathrm\{cap\}\}=Kh,\\qquad H\_\{\\mathrm\{pos\}\}=h,\\qquad H\_\{\\mathrm\{cert\}\}=h\.The other two terms inHHTGH\_\{\\mathrm\{HTG\}\}satisfy

Hthr=K​h,H2,cap=max1≤r≤K⁡r​h=K​h\.H\_\{\\mathrm\{thr\}\}=Kh,\\qquad H\_\{2,\\mathrm\{cap\}\}=\\max\_\{1\\leq r\\leq K\}rh=Kh\.It follows that

HHTG=min⁡\{K​h,h,Q​K​h\}=h=σ2a2\.H\_\{\\mathrm\{HTG\}\}=\\min\\\{Kh,h,QKh\\\}=h=\\frac\{\\sigma^\{2\}\}\{a^\{2\}\}\.\(45\)Thus the positive\-arm term makesHHTGH\_\{\\mathrm\{HTG\}\}a factorKKsmaller thanHcapH\_\{\\mathrm\{cap\}\}on this family\.

This comparison concerns the complexity in the denominator of the exponential bound, rather than the entire sufficient budget\. Here,m=Km=K, so the offset in \([10](https://arxiv.org/html/2610.20997#S4.E10)\) is

T0=3​K​max⁡\{nλ,Q\}\+96​K​c2​h\.T\_\{0\}=3K\\max\\\{n\_\{\\lambda\},Q\\\}\+96Kc^\{2\}h\.\(46\)AlthoughHHTG=hH\_\{\\mathrm\{HTG\}\}=hdoes not depend onKKwhenaaandσ\\sigmaare fixed, the offset does\. Hence this example does not give a sufficient budget independent ofKK\.

#### F\.3A competing arm with mean close to zero

LetK≥3K\\geq 3and consider

μ1=a,μ2=−ε,μ3=⋯=μK=−b,\\mu\_\{1\}=a,\\qquad\\mu\_\{2\}=\-\\varepsilon,\\qquad\\mu\_\{3\}=\\cdots=\\mu\_\{K\}=\-b,where0≤ε≤a/K0\\leq\\varepsilon\\leq a/\\sqrt\{K\}andb≥a​Kb\\geq a\\sqrt\{K\}\. There is exactly one positive arm, soHpos=K​hH\_\{\\mathrm\{pos\}\}=KhandHcert=HcapH\_\{\\mathrm\{cert\}\}=H\_\{\\mathrm\{cap\}\}\. Moreover,

Hcap\\displaystyle H\_\{\\mathrm\{cap\}\}=h\+σ2\(a\+ε\)2\+\(K−2\)​σ2\(a\+b\)2\\displaystyle=h\+\\frac\{\\sigma^\{2\}\}\{\(a\+\\varepsilon\)^\{2\}\}\+\\frac\{\(K\-2\)\\sigma^\{2\}\}\{\(a\+b\)^\{2\}\}\(47\)≤h\+h\+K−2K​h<3​h\.\\displaystyle\\leq h\+h\+\\frac\{K\-2\}\{K\}h<3h\.ThusHcertH\_\{\\mathrm\{cert\}\}remains bounded asε\\varepsilonapproaches zero\.

In contrast,

Hthr=h\+σ2ε2\+\(K−2\)​σ2b2H\_\{\\mathrm\{thr\}\}=h\+\\frac\{\\sigma^\{2\}\}\{\\varepsilon^\{2\}\}\+\\frac\{\(K\-2\)\\sigma^\{2\}\}\{b^\{2\}\}diverges asε↓0\\varepsilon\\downarrow 0and equals\+∞\+\\inftywhenε=0\\varepsilon=0\. The assumptionε≤a/K\\varepsilon\\leq a/\\sqrt\{K\}givesHthr≥K​hH\_\{\\mathrm\{thr\}\}\\geq Kh, including atε=0\\varepsilon=0under our convention\. Therefore,

min⁡\{Hthr,Hpos\}=K​h\.\\min\\\{H\_\{\\mathrm\{thr\}\},H\_\{\\mathrm\{pos\}\}\\\}=Kh\.\(48\)
The halving term gives a smaller bound whenKKis sufficiently large\. Since the means are already ordered,

H2,cap\\displaystyle H\_\{2,\\mathrm\{cap\}\}=max⁡\{h,2​σ2\(a\+ε\)2,K​σ2\(a\+b\)2\}\\displaystyle=\\max\\left\\\{h,\\frac\{2\\sigma^\{2\}\}\{\(a\+\\varepsilon\)^\{2\}\},\\frac\{K\\sigma^\{2\}\}\{\(a\+b\)^\{2\}\}\\right\\\}=max⁡\{h,2​σ2\(a\+ε\)2\}\.\\displaystyle=\\max\\left\\\{h,\\frac\{2\\sigma^\{2\}\}\{\(a\+\\varepsilon\)^\{2\}\}\\right\\\}\.The second equality usesK​σ2/\(a\+b\)2≤hK\\sigma^\{2\}/\(a\+b\)^\{2\}\\leq h\. In particular,h≤H2,cap≤2​hh\\leq H\_\{2,\\mathrm\{cap\}\}\\leq 2h\. Combining this with \([48](https://arxiv.org/html/2610.20997#A6.E48)\) gives

HHTG=min⁡\{K​h,Q​H2,cap\}≤min⁡\{K,2​Q\}​h\.H\_\{\\mathrm\{HTG\}\}=\\min\\\{Kh,QH\_\{2,\\mathrm\{cap\}\}\\\}\\leq\\min\\\{K,2Q\\\}h\.\(49\)Atε=0\\varepsilon=0, the rank\-weighted maximum is exactly2​h2h, and hence

HHTG=min⁡\{K,2​Q\}​h\.H\_\{\\mathrm\{HTG\}\}=\\min\\\{K,2Q\\\}h\.
This example illustrates why the halving term is useful in addition to the first two terms in \([8](https://arxiv.org/html/2610.20997#S4.E8)\)\. A single negative mean close to zero makesHthrH\_\{\\mathrm\{thr\}\}arbitrarily large, whileHposH\_\{\\mathrm\{pos\}\}remainsK​hKh\. The halving term instead givesHHTG≤2​Q​hH\_\{\\mathrm\{HTG\}\}\\leq 2Qh, which remains bounded asε↓0\\varepsilon\\downarrow 0\. Sincem=1m=1, its offset also satisfies

T0≤Tcut\+192​Q​c2​h\.T\_\{0\}\\leq T\_\{\\mathrm\{cut\}\}\+192Qc^\{2\}h\.Thus neither the complexity nor the offset in the HTG guarantee diverges when this competing mean approaches zero\.

### Appendix GProof of the lower bound

We prove Theorem[2](https://arxiv.org/html/2610.20997#Thmtheorem2)and its sample\-complexity consequence \([17](https://arxiv.org/html/2610.20997#S5.E17)\)\. Throughout this appendix, we consider the algorithms described in Section[5\.1](https://arxiv.org/html/2610.20997#S5.SS1)\. Each algorithm collects exactlyTTobservations, samples every arm at least once, and uses the prescribed posterior and terminal recommendation\. The algorithm may be randomized and may depend onTT\.

At each round, the algorithm selects an arm using only previously collected observations and its internal randomization\. The same sampling rule is used under the original and auxiliary instances\.

Recall that

λ=σ2σ02,z=Φ−1​\(1−δ\)\>0\.\\lambda=\\frac\{\\sigma^\{2\}\}\{\\sigma\_\{0\}^\{2\}\},\\qquad z=\\Phi^\{\-1\}\(1\-\\delta\)\>0\.
#### G\.1Finite\-budget lower bounds

Define

bpr:=z​1\+λ−λ​μ0σ,b\_\{\\mathrm\{pr\}\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=z\\sqrt\{1\+\\lambda\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\},and, forx\>0x\>0, let

p⁡\(x\):=Φ⁡\(bpr−1\+xσ\)​\(1−exp⁡\(−2​xσ\)\)\.p\(x\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\Phi\\left\(b\_\{\\mathrm\{pr\}\}\-1\+\\frac\{x\}\{\\sigma\}\\right\)\\left\(1\-\\exp\\left\(\-\\frac\{2x\}\{\\sigma\}\\right\)\\right\)\.Sincep⁡\(x\)∈\(0,1\)p\(x\)\\in\(0,1\)for everyx\>0x\>0, the constants

C0:=∑i=1Klog⁡1p⁡\(εi\)C\_\{0\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{i=1\}^\{K\}\\log\\frac\{1\}\{p\(\\varepsilon\_\{i\}\)\}and

Ca,β:=log⁡1p⁡\(β\)\+∑i≠alog⁡1p⁡\(εi\),a∈\[K\],β\>0,C\_\{a,\\beta\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\log\\frac\{1\}\{p\(\\beta\)\}\+\\sum\_\{i\\neq a\}\\log\\frac\{1\}\{p\(\\varepsilon\_\{i\}\)\},\\qquad a\\in\[K\],\\ \\beta\>0,are finite\. They depend on the fixed parameters, but not onTTor the algorithm\. We do not requireCa,βC\_\{a,\\beta\}to remain bounded asβ↓0\\beta\\downarrow 0\.

###### Proposition 1\(Finite\-budget search and certification bounds\)\.

For every algorithm𝒜\\mathcal\{A\}described in Section[5\.1](https://arxiv.org/html/2610.20997#S5.SS1)and every integerT≥KT\\geq K,

maxa∈\[K\]⁡ℙμ\(a\)𝒜​\(SuccTc\)≥exp⁡\[−\(T2​S\+C0\)2\]\.\\max\_\{a\\in\[K\]\}\\mathbb\{P\}\_\{\\mu^\{\(a\)\}\}^\{\\mathcal\{A\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\geq\\exp\\left\[\-\\left\(\\sqrt\{\\frac\{T\}\{2S\}\}\+\\sqrt\{C\_\{0\}\}\\right\)^\{2\}\\right\]\.\(50\)Moreover, for everya∈\[K\]a\\in\[K\]and everyβ\>0\\beta\>0,

ℙμ\(a\)𝒜​\(SuccTc\)≥exp⁡\[−\(Δ\+βσ​T2\+Ca,β\)2\]\.\\mathbb\{P\}\_\{\\mu^\{\(a\)\}\}^\{\\mathcal\{A\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\geq\\exp\\left\[\-\\left\(\\frac\{\\Delta\+\\beta\}\{\\sigma\}\\sqrt\{\\frac\{T\}\{2\}\}\+\\sqrt\{C\_\{a,\\beta\}\}\\right\)^\{2\}\\right\]\.\(51\)

###### Proof\.

Fix an algorithm𝒜\\mathcal\{A\}and a budgetT≥KT\\geq K\. We represent the observations by independent infinite sequences\(Xi,n\)n≥1\(X\_\{i,n\}\)\_\{n\\geq 1\}, one for each arm\. Sampling armiireveals the next unused observation in its sequence\. The algorithm’s internal randomization is represented by a random seed independent of these sequences\.

We writeℙν\\mathbb\{P\}\_\{\\nu\}for the probability measure under mean vectorν\\nu, andPνTP\_\{\\nu\}^\{T\}for the distribution of the observed history up to timeTT, including the algorithm’s internal randomization\. We suppress the dependence on𝒜\\mathcal\{A\}in this notation\.

##### Step 1: An event that guarantees posterior failure\.

Consider an auxiliary instance

ν=\(−v1,…,−vK\),vi\>0\.\\nu=\(\-v\_\{1\},\\ldots,\-v\_\{K\}\),\\qquad v\_\{i\}\>0\.For each armii, define

Yi,m:=∑s=2m\+1Xi,sσ,m≥0,Y\_\{i,m\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{s=2\}^\{m\+1\}\\frac\{X\_\{i,s\}\}\{\\sigma\},\\qquad m\\geq 0,whereYi,0=0Y\_\{i,0\}=0\. Underℙν\\mathbb\{P\}\_\{\\nu\}, the increments ofYi,mY\_\{i,m\}are independent Gaussian variables with mean−vi/σ\-v\_\{i\}/\\sigmaand variance one\. Therefore,

\(exp⁡\(2​viσ​Yi,m\)\)m≥0\\left\(\\exp\\left\(\\frac\{2v\_\{i\}\}\{\\sigma\}Y\_\{i,m\}\\right\)\\right\)\_\{m\\geq 0\}is a nonnegative martingale with initial value one\. The maximal inequality for nonnegative martingales gives

ℙν​\(∃m≥0:Yi,m≥1\)≤exp⁡\(−2​viσ\)\.\\mathbb\{P\}\_\{\\nu\}\\left\(\\exists m\\geq 0\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\ Y\_\{i,m\}\\geq 1\\right\)\\leq\\exp\\left\(\-\\frac\{2v\_\{i\}\}\{\\sigma\}\\right\)\.To obtain the bound over allm≥0m\\geq 0, apply the inequality over each finite range and then take an increasing union\.

Define

E:=⋂i=1K\(\{Xi,1σ≤bpr−1\}∩⋂m≥0\{Yi,m<1\}\)\.E\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\bigcap\_\{i=1\}^\{K\}\\left\(\\left\\\{\\frac\{X\_\{i,1\}\}\{\\sigma\}\\leq b\_\{\\mathrm\{pr\}\}\-1\\right\\\}\\cap\\bigcap\_\{m\\geq 0\}\\\{Y\_\{i,m\}<1\\\}\\right\)\.The first observation of each arm is independent of its subsequent observations, and

ℙν​\(Xi,1σ≤bpr−1\)=Φ⁡\(bpr−1\+viσ\)\.\\mathbb\{P\}\_\{\\nu\}\\left\(\\frac\{X\_\{i,1\}\}\{\\sigma\}\\leq b\_\{\\mathrm\{pr\}\}\-1\\right\)=\\Phi\\left\(b\_\{\\mathrm\{pr\}\}\-1\+\\frac\{v\_\{i\}\}\{\\sigma\}\\right\)\.Combining the preceding bounds and using independence across arms, we obtain

ℙν​\(E\)≥∏i=1Kp⁡\(vi\)\>0\.\\mathbb\{P\}\_\{\\nu\}\(E\)\\geq\\prod\_\{i=1\}^\{K\}p\(v\_\{i\}\)\>0\.The eventEEis defined using the full observation sequences, without reference to the algorithm or the budget\. Its probability therefore does not depend on either\.

OnEE, for every armiiand everyn≥1n\\geq 1,

∑s=1nXi,sσ=Xi,1σ\+Yi,n−1<bpr≤z​n\+λ−λ​μ0σ\.\\sum\_\{s=1\}^\{n\}\\frac\{X\_\{i,s\}\}\{\\sigma\}=\\frac\{X\_\{i,1\}\}\{\\sigma\}\+Y\_\{i,n\-1\}<b\_\{\\mathrm\{pr\}\}\\leq z\\sqrt\{n\+\\lambda\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\}\.The last inequality follows fromz\>0z\>0andn≥1n\\geq 1\. HenceZi,n<zZ\_\{i,n\}<zfor everyiiand everyn≥1n\\geq 1\. Since the algorithm samples every arm at least once, \([4](https://arxiv.org/html/2610.20997#S3.E4)\) implies that posterior failure occurs onEE, regardless of how the algorithm allocates its observations\.

We now consider the distribution of the observed history underν\\nu, conditional onEE\. Specifically, for any eventBBdetermined by the observed history, define

𝖰T​\(B\):=ℙν​\(B∣E\)=ℙν​\(B∩E\)ℙν​\(E\)\.\\mathsf\{Q\}\_\{T\}\(B\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mathbb\{P\}\_\{\\nu\}\(B\\mid E\)=\\frac\{\\mathbb\{P\}\_\{\\nu\}\(B\\cap E\)\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}\.Thus,𝖰T\\mathsf\{Q\}\_\{T\}describes the observed history when we restrict attention to realizations in whichEEoccurs\. The sampling rule remains unchanged, and the algorithm is not given any information aboutEE\. AlthoughEEmay involve observations that the algorithm never collects, this conditional distribution is well defined becauseEEand the observed history are defined on the same probability space\.

Under this conditional distribution,

𝖰T​\(SuccTc\)=1\.\\mathsf\{Q\}\_\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)=1\.Moreover,

d​𝖰Td​PνT=ℙν​\(E∣ℱT\)ℙν​\(E\)≤1ℙν​\(E\)\.\\frac\{d\\mathsf\{Q\}\_\{T\}\}\{dP\_\{\\nu\}^\{T\}\}=\\frac\{\\mathbb\{P\}\_\{\\nu\}\(E\\mid\\mathcal\{F\}\_\{T\}\)\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}\\leq\\frac\{1\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}\.WritingKL\\operatorname\{KL\}for relative entropy, it follows that

DT:=KL\(𝖰T∥PνT\)≤log1ℙν​\(E\)≤∑i=1Klog1p⁡\(vi\)\.D\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\nu\}^\{T\}\)\\leq\\log\\frac\{1\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}\\leq\\sum\_\{i=1\}^\{K\}\\log\\frac\{1\}\{p\(v\_\{i\}\)\}\.\(52\)Although𝖰T\\mathsf\{Q\}\_\{T\}depends on the algorithm and the budget, the upper bound in \([52](https://arxiv.org/html/2610.20997#A7.E52)\) does not\.

##### Step 2: Changing the mean of one arm\.

Suppose thatν′\\nu^\{\\prime\}differs fromν\\nuonly at armaa, with

νa′−νa=g​σ,g\>0\.\\nu^\{\\prime\}\_\{a\}\-\\nu\_\{a\}=g\\sigma,\\qquad g\>0\.Define

Ma\(t\):=1σ∑s=1Na​\(t\)\(Xa,s−νa\),na:=𝔼𝖰T\[Na\(T\)\]\.M\_\{a\}\(t\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{1\}\{\\sigma\}\\sum\_\{s=1\}^\{N\_\{a\}\(t\)\}\(X\_\{a,s\}\-\\nu\_\{a\}\),\\qquad n\_\{a\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[N\_\{a\}\(T\)\]\.Because the same algorithm is used underν\\nuandν′\\nu^\{\\prime\}, the sampling probabilities cancel in the likelihood ratio\. The Gaussian observation densities therefore give

log⁡d​PνTd​Pν′T=g22​Na​\(T\)−g​Ma​\(T\)\.\\log\\frac\{dP\_\{\\nu\}^\{T\}\}\{dP\_\{\\nu^\{\\prime\}\}^\{T\}\}=\\frac\{g^\{2\}\}\{2\}N\_\{a\}\(T\)\-gM\_\{a\}\(T\)\.\(53\)
To control the expectation ofMa​\(T\)M\_\{a\}\(T\)under𝖰T\\mathsf\{Q\}\_\{T\}, first work under the original probability measureℙν\\mathbb\{P\}\_\{\\nu\}\. For everyθ\>0\\theta\>0, the process

\(exp⁡\(−θ​Ma​\(t\)−θ22​Na​\(t\)\)\)t=0T\\left\(\\exp\\left\(\-\\theta M\_\{a\}\(t\)\-\\frac\{\\theta^\{2\}\}\{2\}N\_\{a\}\(t\)\\right\)\\right\)\_\{t=0\}^\{T\}is a mean\-one martingale\. Indeed, when armaais selected, its next centered, standardized observation is conditionally standard Gaussian; otherwise, the process does not change\. Consequently,

𝔼PνT​\[exp⁡\(−θ​Ma​\(T\)−θ22​Na​\(T\)\)\]=1\.\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\\left\[\\exp\\left\(\-\\theta M\_\{a\}\(T\)\-\\frac\{\\theta^\{2\}\}\{2\}N\_\{a\}\(T\)\\right\)\\right\]=1\.This identity is used underPνTP\_\{\\nu\}^\{T\}, not under𝖰T\\mathsf\{Q\}\_\{T\}\. After conditioning onEE, the observations need not remain independent or Gaussian\.

The expectations used below are finite\. Indeed, underℙν\\mathbb\{P\}\_\{\\nu\}, the processesMa​\(t\)M\_\{a\}\(t\)andMa​\(t\)2−Na​\(t\)M\_\{a\}\(t\)^\{2\}\-N\_\{a\}\(t\)are martingales, so

𝔼PνT​\[Ma​\(T\)2\]=𝔼PνT​\[Na​\(T\)\]≤T\.\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\[M\_\{a\}\(T\)^\{2\}\]=\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\[N\_\{a\}\(T\)\]\\leq T\.Together with the density bound from Step 1, this gives

𝔼𝖰T​\[Ma​\(T\)2\]≤Tℙν​\(E\)<∞\.\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{a\}\(T\)^\{2\}\]\\leq\\frac\{T\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}<\\infty\.SinceNa​\(T\)≤TN\_\{a\}\(T\)\\leq T, all expectations in the following entropy calculations are therefore finite\.

The entropy inequality gives

𝔼𝖰T​\[W\]≤DT\+log⁡𝔼PνT​\[eW\]\.\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[W\]\\leq D\_\{T\}\+\\log\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\[e^\{W\}\]\.For completeness, this follows from nonnegativity of relative entropy with respect to the probability measure having densityeW/𝔼PνT​\[eW\]e^\{W\}/\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\[e^\{W\}\]relative toPνTP\_\{\\nu\}^\{T\}\. Applying the inequality with

W=−θ​Ma​\(T\)−θ22​Na​\(T\)W=\-\\theta M\_\{a\}\(T\)\-\\frac\{\\theta^\{2\}\}\{2\}N\_\{a\}\(T\)yields

−𝔼𝖰T​\[Ma​\(T\)\]≤DTθ\+θ​na2\.\-\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{a\}\(T\)\]\\leq\\frac\{D\_\{T\}\}\{\\theta\}\+\\frac\{\\theta n\_\{a\}\}\{2\}\.Optimizing overθ\>0\\theta\>0, we obtain

−𝔼𝖰T​\[Ma​\(T\)\]≤2​na​DT\.\-\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{a\}\(T\)\]\\leq\\sqrt\{2n\_\{a\}D\_\{T\}\}\.WhenDT=0D\_\{T\}=0, the same conclusion follows by lettingθ↓0\\theta\\downarrow 0\.

Combining this bound with \([53](https://arxiv.org/html/2610.20997#A7.E53)\), we have

KL\(𝖰T∥Pν′T\)\\displaystyle\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\nu^\{\\prime\}\}^\{T\}\)=DT\+𝔼𝖰T​\[log⁡d​PνTd​Pν′T\]\\displaystyle=D\_\{T\}\+\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\\left\[\\log\\frac\{dP\_\{\\nu\}^\{T\}\}\{dP\_\{\\nu^\{\\prime\}\}^\{T\}\}\\right\]=DT\+g2​na2−g​𝔼𝖰T​\[Ma​\(T\)\]\\displaystyle=D\_\{T\}\+\\frac\{g^\{2\}n\_\{a\}\}\{2\}\-g\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{a\}\(T\)\]≤DT\+g2​na2\+g​2​na​DT\\displaystyle\\leq D\_\{T\}\+\\frac\{g^\{2\}n\_\{a\}\}\{2\}\+g\\sqrt\{2n\_\{a\}D\_\{T\}\}=\(g​na2\+DT\)2\.\\displaystyle=\\left\(g\\sqrt\{\\frac\{n\_\{a\}\}\{2\}\}\+\\sqrt\{D\_\{T\}\}\\right\)^\{2\}\.
On the other hand,𝖰T​\(SuccTc\)=1\\mathsf\{Q\}\_\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)=1implies

KL\(𝖰T∥Pν′T\)≥log1Pν′T​\(SuccTc\)\.\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\nu^\{\\prime\}\}^\{T\}\)\\geq\\log\\frac\{1\}\{P\_\{\\nu^\{\\prime\}\}^\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\}\.To see this, note that the finite\-history distributionsPνTP\_\{\\nu\}^\{T\}andPν′TP\_\{\\nu^\{\\prime\}\}^\{T\}are mutually absolutely continuous, soPν′T​\(SuccTc\)\>0P\_\{\\nu^\{\\prime\}\}^\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\>0\. We can therefore write

KL\(𝖰T∥Pν′T\)\\displaystyle\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\nu^\{\\prime\}\}^\{T\}\)=KL\(𝖰T∥Pν′T\(⋅∣SuccTc\)\)\\displaystyle=\\operatorname\{KL\}\\left\(\\mathsf\{Q\}\_\{T\}\\,\\middle\\\|\\,P\_\{\\nu^\{\\prime\}\}^\{T\}\(\\,\\cdot\\,\\mid\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\right\)\+log⁡1Pν′T​\(SuccTc\),\\displaystyle\\quad\+\\log\\frac\{1\}\{P\_\{\\nu^\{\\prime\}\}^\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\},and the first term is nonnegative\.

Combining these inequalities gives

ℙν′𝒜​\(SuccTc\)≥exp⁡\[−\(g​na2\+DT\)2\]\.\\mathbb\{P\}\_\{\\nu^\{\\prime\}\}^\{\\mathcal\{A\}\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\geq\\exp\\left\[\-\\left\(g\\sqrt\{\\frac\{n\_\{a\}\}\{2\}\}\+\\sqrt\{D\_\{T\}\}\\right\)^\{2\}\\right\]\.\(54\)

##### Step 3: The search bound\.

Take

ν=\(−ε1,…,−εK\)\.\\nu=\(\-\\varepsilon\_\{1\},\\ldots,\-\\varepsilon\_\{K\}\)\.By \([52](https://arxiv.org/html/2610.20997#A7.E52)\), the distribution𝖰T\\mathsf\{Q\}\_\{T\}constructed in Step 1 satisfiesDT≤C0D\_\{T\}\\leq C\_\{0\}\. For eachi∈\[K\]i\\in\[K\], let

ni:=𝔼𝖰T\[Ni\(T\)\]=𝔼ν\[Ni\(T\)∣E\],wi:=σ2\(Δ\+εi\)2\.n\_\{i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[N\_\{i\}\(T\)\]=\\mathbb\{E\}\_\{\\nu\}\[N\_\{i\}\(T\)\\mid E\],\\qquad w\_\{i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{i\}\)^\{2\}\}\.The algorithm collects exactlyTTobservations on every realization, including those inEE\. Hence

∑i=1Kni=𝔼ν​\[∑i=1KNi​\(T\)\|E\]=T\.\\sum\_\{i=1\}^\{K\}n\_\{i\}=\\mathbb\{E\}\_\{\\nu\}\\left\[\\sum\_\{i=1\}^\{K\}N\_\{i\}\(T\)\\,\\middle\|\\,E\\right\]=T\.Since∑iwi=S\\sum\_\{i\}w\_\{i\}=S, we obtain

∑i=1KwiS​niwi=TS\.\\sum\_\{i=1\}^\{K\}\\frac\{w\_\{i\}\}\{S\}\\frac\{n\_\{i\}\}\{w\_\{i\}\}=\\frac\{T\}\{S\}\.Therefore, at least one locationa∈\[K\]a\\in\[K\]satisfies

nawa≤TS\.\\frac\{n\_\{a\}\}\{w\_\{a\}\}\\leq\\frac\{T\}\{S\}\.This location may depend on𝒜\\mathcal\{A\}andTT\.

Passing fromν\\nutoμ\(a\)\\mu^\{\(a\)\}changes only the mean of armaa, from−εa\-\\varepsilon\_\{a\}toΔ\\Delta\. Its standardized mean difference is

ga=Δ\+εaσ=1wa\.g\_\{a\}=\\frac\{\\Delta\+\\varepsilon\_\{a\}\}\{\\sigma\}=\\frac\{1\}\{\\sqrt\{w\_\{a\}\}\}\.Applying \([54](https://arxiv.org/html/2610.20997#A7.E54)\), we obtain

ℙμ\(a\)𝒜​\(SuccTc\)\\displaystyle\\mathbb\{P\}\_\{\\mu^\{\(a\)\}\}^\{\\mathcal\{A\}\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)≥exp⁡\[−\(na2​wa\+DT\)2\]\\displaystyle\\geq\\exp\\left\[\-\\left\(\\sqrt\{\\frac\{n\_\{a\}\}\{2w\_\{a\}\}\}\+\\sqrt\{D\_\{T\}\}\\right\)^\{2\}\\right\]≥exp⁡\[−\(T2​S\+C0\)2\]\.\\displaystyle\\geq\\exp\\left\[\-\\left\(\\sqrt\{\\frac\{T\}\{2S\}\}\+\\sqrt\{C\_\{0\}\}\\right\)^\{2\}\\right\]\.Taking the maximum over locations proves \([50](https://arxiv.org/html/2610.20997#A7.E50)\)\.

##### Step 4: The certification bound\.

Fix anya∈\[K\]a\\in\[K\]andβ\>0\\beta\>0, and consider the auxiliary instance

νi\(a,β\):=\{−β,i=a,−εi,i≠a\.\\nu\_\{i\}^\{\(a,\\beta\)\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\begin\{cases\}\-\\beta,&i=a,\\\\ \-\\varepsilon\_\{i\},&i\\neq a\.\\end\{cases\}All its means are negative\. The construction in Step 1 and \([52](https://arxiv.org/html/2610.20997#A7.E52)\) therefore give a conditional distribution𝖰T\\mathsf\{Q\}\_\{T\}satisfying

DT≤Ca,β\.D\_\{T\}\\leq C\_\{a,\\beta\}\.Passing fromν\(a,β\)\\nu^\{\(a,\\beta\)\}toμ\(a\)\\mu^\{\(a\)\}changes only the mean of armaa, from−β\-\\betatoΔ\\Delta\. Thus,

g=Δ\+βσ,na=𝔼𝖰T​\[Na​\(T\)\]≤T\.g=\\frac\{\\Delta\+\\beta\}\{\\sigma\},\\qquad n\_\{a\}=\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[N\_\{a\}\(T\)\]\\leq T\.Substituting these bounds into \([54](https://arxiv.org/html/2610.20997#A7.E54)\) proves \([51](https://arxiv.org/html/2610.20997#A7.E51)\)\. Unlike the search bound, this bound holds for every fixed locationaa\. ∎

#### G\.2Proof of the asymptotic lower bound

###### Proof of Theorem[2](https://arxiv.org/html/2610.20997#Thmtheorem2)\.

The constants in Proposition[1](https://arxiv.org/html/2610.20997#Thmproposition1)are independent of the algorithm and the budget\. We may therefore take the infimum over algorithms in the finite\-budget inequalities before taking any limit\. In particular, the argument allows the algorithm to depend onTT\.

The search bound \([50](https://arxiv.org/html/2610.20997#A7.E50)\) gives

rT⋆​\(Δ,ε\)≥exp⁡\[−\(T2​S\+C0\)2\]\.r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\geq\\exp\\left\[\-\\left\(\\sqrt\{\\frac\{T\}\{2S\}\}\+\\sqrt\{C\_\{0\}\}\\right\)^\{2\}\\right\]\.It follows that

−1T​log⁡rT⋆​\(Δ,ε\)≤\(12​S\+C0T\)2\.\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\left\(\\frac\{1\}\{\\sqrt\{2S\}\}\+\\sqrt\{\\frac\{C\_\{0\}\}\{T\}\}\\right\)^\{2\}\.SinceC0C\_\{0\}is fixed asT→∞T\\to\\infty,

lim supT→∞−1TlogrT⋆\(Δ,ε\)≤12​S\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\frac\{1\}\{2S\}\.
Next, fix anya∈\[K\]a\\in\[K\]andβ\>0\\beta\>0\. For every algorithm, its maximum failure probability over the family is at least its failure probability atμ\(a\)\\mu^\{\(a\)\}\. Taking the infimum over algorithms in \([51](https://arxiv.org/html/2610.20997#A7.E51)\) therefore yields

rT⋆​\(Δ,ε\)≥exp⁡\[−\(Δ\+βσ​T2\+Ca,β\)2\]\.r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\geq\\exp\\left\[\-\\left\(\\frac\{\\Delta\+\\beta\}\{\\sigma\}\\sqrt\{\\frac\{T\}\{2\}\}\+\\sqrt\{C\_\{a,\\beta\}\}\\right\)^\{2\}\\right\]\.For this fixedβ\\beta, the constantCa,βC\_\{a,\\beta\}is finite and independent ofTT\. Consequently,

lim supT→∞−1TlogrT⋆\(Δ,ε\)≤\(Δ\+β\)22​σ2\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\frac\{\(\\Delta\+\\beta\)^\{2\}\}\{2\\sigma^\{2\}\}\.This inequality holds for everyβ\>0\\beta\>0\. Lettingβ↓0\\beta\\downarrow 0after taking the limit inTTgives

lim supT→∞−1TlogrT⋆\(Δ,ε\)≤Δ22​σ2=12​h\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\frac\{\\Delta^\{2\}\}\{2\\sigma^\{2\}\}=\\frac\{1\}\{2h\}\.The order of limits ensures that no bound onCa,βC\_\{a,\\beta\}uniform inβ\\betais needed\.

Combining the search and certification bounds, we conclude that

lim supT→∞−1TlogrT⋆\(Δ,ε\)≤min\{12​S,12​h\}=12​max⁡\{h,S\}\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\min\\left\\\{\\frac\{1\}\{2S\},\\frac\{1\}\{2h\}\\right\\\}=\\frac\{1\}\{2\\max\\\{h,S\\\}\}\.This proves \([16](https://arxiv.org/html/2610.20997#S5.E16)\)\. ∎

#### G\.3Sample\-complexity consequence

We now prove \([17](https://arxiv.org/html/2610.20997#S5.E17)\)\. For each target failure probabilityη\\eta, suppose that an algorithm𝒜η\\mathcal\{A\}\_\{\\eta\}uses a budgetTη≥KT\_\{\\eta\}\\geq Kand satisfies

maxa∈\[K\]⁡ℙμ\(a\)𝒜η​\(SuccTηc\)≤η\.\\max\_\{a\\in\[K\]\}\\mathbb\{P\}\_\{\\mu^\{\(a\)\}\}^\{\\mathcal\{A\}\_\{\\eta\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\_\{\\eta\}\}^\{c\}\\bigr\)\\leq\\eta\.Both the algorithm and its budget may depend onη\\eta\. By the definition of the minimax failure probability,

rTη⋆​\(Δ,ε\)≤η\.r\_\{T\_\{\\eta\}\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\eta\.
First, this guarantee requiresTη→∞T\_\{\\eta\}\\to\\inftyasη↓0\\eta\\downarrow 0\. Indeed, for any fixed integerM≥KM\\geq K, \([50](https://arxiv.org/html/2610.20997#A7.E50)\) implies

rT⋆​\(Δ,ε\)≥exp⁡\[−\(M2​S\+C0\)2\]\>0,K≤T≤M\.r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\geq\\exp\\left\[\-\\left\(\\sqrt\{\\frac\{M\}\{2S\}\}\+\\sqrt\{C\_\{0\}\}\\right\)^\{2\}\\right\]\>0,\\qquad K\\leq T\\leq M\.Thus, for sufficiently smallη\\eta, no budget at mostMMcan achieve failure probability at mostη\\etaon every instance in the family\.

Fixξ\>0\\xi\>0\. Theorem[2](https://arxiv.org/html/2610.20997#Thmtheorem2)implies that, for all sufficiently largeTT,

−1T​log⁡rT⋆​\(Δ,ε\)≤1\+ξ2​max⁡\{h,S\}\.\-\\frac\{1\}\{T\}\\log r\_\{T\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\frac\{1\+\\xi\}\{2\\max\\\{h,S\\\}\}\.SinceTη→∞T\_\{\\eta\}\\to\\infty, for all sufficiently smallη\\etawe have

log⁡1η≤−log⁡rTη⋆​\(Δ,ε\)≤1\+ξ2​max⁡\{h,S\}​Tη\.\\log\\frac\{1\}\{\\eta\}\\leq\-\\log r\_\{T\_\{\\eta\}\}^\{\\star\}\(\\Delta,\\varepsilon\)\\leq\\frac\{1\+\\xi\}\{2\\max\\\{h,S\\\}\}\\,T\_\{\\eta\}\.Therefore,

lim infη↓0Tηlog⁡\(1/η\)≥2​max⁡\{h,S\}1\+ξ\.\\liminf\_\{\\eta\\downarrow 0\}\\frac\{T\_\{\\eta\}\}\{\\log\(1/\\eta\)\}\\geq\\frac\{2\\max\\\{h,S\\\}\}\{1\+\\xi\}\.Lettingξ↓0\\xi\\downarrow 0yields

lim infη↓0Tηlog⁡\(1/η\)≥2​max⁡\{h,S\}\.\\liminf\_\{\\eta\\downarrow 0\}\\frac\{T\_\{\\eta\}\}\{\\log\(1/\\eta\)\}\\geq 2\\max\\\{h,S\\\}\.Equivalently, any such budget satisfies

Tη≥\(2−oη​\(1\)\)​max⁡\{h,S\}​log​1η,η↓0\.T\_\{\\eta\}\\geq\\bigl\(2\-o\_\{\\eta\}\(1\)\\bigr\)\\max\\\{h,S\\\}\\log\\frac\{1\}\{\\eta\},\\qquad\\eta\\downarrow 0\.Hereoη​\(1\)→0o\_\{\\eta\}\(1\)\\to 0asη↓0\\eta\\downarrow 0, withKK,Δ\\Delta,ε\\varepsilon,σ2\\sigma^\{2\},\(μ0,σ02\)\(\\mu\_\{0\},\\sigma\_\{0\}^\{2\}\), andδ\\deltaheld fixed\. This proves \([17](https://arxiv.org/html/2610.20997#S5.E17)\)\.

#### G\.4Proof of Lemma[2](https://arxiv.org/html/2610.20997#Thmlemma2)

###### Proof\.

Fixa∈\[K\]a\\in\[K\]\. For the instanceμ\(a\)\\mu^\{\(a\)\}, we haveμ⋆=Δ\\mu\_\{\\star\}=\\Delta, and armaais the unique positive arm\. Therefore,

Hpos​\(μ\(a\)\)=K​σ2Δ2=K​h\.H\_\{\\mathrm\{pos\}\}\(\\mu^\{\(a\)\}\)=\\frac\{K\\sigma^\{2\}\}\{\\Delta^\{2\}\}=Kh\.
ForHcapH\_\{\\mathrm\{cap\}\}, the contribution of armaaisσ2/Δ2=h\\sigma^\{2\}/\\Delta^\{2\}=h\. For everyi≠ai\\neq a,

max⁡\{μ⋆,μ⋆−μi\(a\)\}=max⁡\{Δ,Δ\+εi\}=Δ\+εi\.\\max\\\{\\mu\_\{\\star\},\\mu\_\{\\star\}\-\\mu\_\{i\}^\{\(a\)\}\\\}=\\max\\\{\\Delta,\\Delta\+\\varepsilon\_\{i\}\\\}=\\Delta\+\\varepsilon\_\{i\}\.Hence

Hcap​\(μ\(a\)\)=h\+∑i≠aσ2\(Δ\+εi\)2=h\+S−σ2\(Δ\+εa\)2\.H\_\{\\mathrm\{cap\}\}\(\\mu^\{\(a\)\}\)=h\+\\sum\_\{i\\neq a\}\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{i\}\)^\{2\}\}=h\+S\-\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{a\}\)^\{2\}\}\.SinceΔ\+εi\>Δ\\Delta\+\\varepsilon\_\{i\}\>\\Deltafor everyii, each term inHcap​\(μ\(a\)\)H\_\{\\mathrm\{cap\}\}\(\\mu^\{\(a\)\}\)is at mosthh\. Thus

Hcap​\(μ\(a\)\)≤K​h=Hpos​\(μ\(a\)\),H\_\{\\mathrm\{cap\}\}\(\\mu^\{\(a\)\}\)\\leq Kh=H\_\{\\mathrm\{pos\}\}\(\\mu^\{\(a\)\}\),and therefore

Hcert​\(μ\(a\)\)=Hcap​\(μ\(a\)\)\.H\_\{\\mathrm\{cert\}\}\(\\mu^\{\(a\)\}\)=H\_\{\\mathrm\{cap\}\}\(\\mu^\{\(a\)\}\)\.
Now,

σ2\(Δ\+εa\)2≤handσ2\(Δ\+εa\)2≤S\.\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{a\}\)^\{2\}\}\\leq h\\qquad\\text\{and\}\\qquad\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{a\}\)^\{2\}\}\\leq S\.It follows that

Hcert​\(μ\(a\)\)=h\+S−σ2\(Δ\+εa\)2≥hH\_\{\\mathrm\{cert\}\}\(\\mu^\{\(a\)\}\)=h\+S\-\\frac\{\\sigma^\{2\}\}\{\(\\Delta\+\\varepsilon\_\{a\}\)^\{2\}\}\\geq hand

Hcert​\(μ\(a\)\)≥S\.H\_\{\\mathrm\{cert\}\}\(\\mu^\{\(a\)\}\)\\geq S\.Therefore,

Hcert​\(μ\(a\)\)≥max⁡\{h,S\}\.H\_\{\\mathrm\{cert\}\}\(\\mu^\{\(a\)\}\)\\geq\\max\\\{h,S\\\}\.The upper bound follows directly from

Hcert​\(μ\(a\)\)≤h\+S≤2​max⁡\{h,S\}\.H\_\{\\mathrm\{cert\}\}\(\\mu^\{\(a\)\}\)\\leq h\+S\\leq 2\\max\\\{h,S\\\}\.This proves \([18](https://arxiv.org/html/2610.20997#S5.E18)\)\. ∎

### Appendix HEqual positive means

We complement the lower bound for one\-positive\-arm families with a result for the “many positive arms” example from Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3), in which

μ=\(a,…,a\)∈ℝK,a\>0\.\\mu=\(a,\\ldots,a\)\\in\\mathbb\{R\}^\{K\},\\qquad a\>0\.We show that every admissible algorithm, as defined in Section[5\.1](https://arxiv.org/html/2610.20997#S5.SS1), has the same exact asymptotic posterior\-failure exponent on this instance\. This includes both HTG and uniform sampling\.

Throughout this appendix,KK,aa, the observation varianceσ2\\sigma^\{2\}, the prior parameters\(μ0,σ02\)\(\\mu\_\{0\},\\sigma\_\{0\}^\{2\}\), and the posterior credibility toleranceδ\\deltaare fixed\. Recall that

λ=σ2σ02,z=Φ−1​\(1−δ\)\>0\.\\lambda=\\frac\{\\sigma^\{2\}\}\{\\sigma\_\{0\}^\{2\}\},\\qquad z=\\Phi^\{\-1\}\(1\-\\delta\)\>0\.
###### Proposition 2\(Exact exponent for equal positive means\)\.

Letμ=\(a,…,a\)\\mu=\(a,\\ldots,a\)witha\>0a\>0\. For every sequence of admissible algorithms\(𝒜T\)T≥K\(\\mathcal\{A\}\_\{T\}\)\_\{T\\geq K\},

limT→∞−1Tlogℙμ𝒜T\(SuccTc\)=a22​σ2=12​Hpos​\(μ\)\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\_\{T\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)=\\frac\{a^\{2\}\}\{2\\sigma^\{2\}\}=\\frac\{1\}\{2H\_\{\\mathrm\{pos\}\}\(\\mu\)\}\.\(55\)The algorithms may be randomized and may depend onTT\.

###### Proof\.

Fix a budgetT≥KT\\geq Kand an admissible algorithm𝒜T\\mathcal\{A\}\_\{T\}\. Writeℙθ\\mathbb\{P\}\_\{\\theta\}for the probability measure under mean vectorθ\\theta, andPθTP\_\{\\theta\}^\{T\}for the distribution of the observed history up to timeTT, including the algorithm’s internal randomization\. We suppress the dependence on𝒜T\\mathcal\{A\}\_\{T\}in this notation\. LetYtY\_\{t\}denote the observation collected at roundtt\.

We establish finite\-budget lower and upper bounds that hold uniformly over the choice of𝒜T\\mathcal\{A\}\_\{T\}\.

##### Lower bound on the failure probability\.

Fixβ\>0\\beta\>0and consider the auxiliary instance

ν=\(−β,…,−β\)\.\\nu=\(\-\\beta,\\ldots,\-\\beta\)\.The same algorithm, with the same parameter settings, is used underν\\nuandμ\\mu\.

Apply the event construction from the proof of Proposition[1](https://arxiv.org/html/2610.20997#Thmproposition1)toν\\nu\. It gives an eventEE, defined using the full observation sequences, such that

ℙν​\(E\)≥p​\(β\)K\>0\\mathbb\{P\}\_\{\\nu\}\(E\)\\geq p\(\\beta\)^\{K\}\>0and, onEE,

Zi,n<zfor every​i∈\[K\]​and​n≥1\.Z\_\{i,n\}<z\\qquad\\text\{for every \}i\\in\[K\]\\text\{ and \}n\\geq 1\.Hereppis the function defined in Appendix[G\.1](https://arxiv.org/html/2610.20997#A7.SS1)\. The event and its probability do not depend onTTor the algorithm\. Since every arm is sampled at least once, \([4](https://arxiv.org/html/2610.20997#S3.E4)\) implies thatEEguarantees posterior failure\.

Let𝖰T\\mathsf\{Q\}\_\{T\}be the distribution of the observed history underν\\nu, conditional onEE\. Specifically, for any eventBBdetermined by the observed history, define

𝖰T​\(B\):=ℙν​\(B∣E\)\.\\mathsf\{Q\}\_\{T\}\(B\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mathbb\{P\}\_\{\\nu\}\(B\\mid E\)\.Thus, we restrict attention to realizations in whichEEoccurs, without changing the sampling rule\. The conditioning argument in Appendix[G\.1](https://arxiv.org/html/2610.20997#A7.SS1)gives

𝖰T\(SuccTc\)=1,DT:=KL\(𝖰T∥PνT\)≤Cβ,\\mathsf\{Q\}\_\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)=1,\\qquad D\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\nu\}^\{T\}\)\\leq C\_\{\\beta\},where

Cβ:=K​log⁡1p⁡\(β\)<∞\.C\_\{\\beta\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=K\\log\\frac\{1\}\{p\(\\beta\)\}<\\infty\.For each fixedβ\>0\\beta\>0, the constantCβC\_\{\\beta\}is independent ofTTand the algorithm\. We also have the density bound

d​𝖰Td​PνT≤1ℙν​\(E\)\.\\frac\{d\\mathsf\{Q\}\_\{T\}\}\{dP\_\{\\nu\}^\{T\}\}\\leq\\frac\{1\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}\.
Passing fromν\\nutoμ\\muchanges every arm mean by the same amounta\+βa\+\\beta\. Define

g:=a\+βσ,MT:=∑t=1TYt\+βσ\.g\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{a\+\\beta\}\{\\sigma\},\\qquad M\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{t=1\}^\{T\}\\frac\{Y\_\{t\}\+\\beta\}\{\\sigma\}\.Because the algorithm selects each arm using only previous observations and its internal randomization, its sampling probabilities cancel in the likelihood ratio\. The Gaussian observation densities give

log⁡d​PνTd​PμT=g2​T2−g​MT\.\\log\\frac\{dP\_\{\\nu\}^\{T\}\}\{dP\_\{\\mu\}^\{T\}\}=\\frac\{g^\{2\}T\}\{2\}\-gM\_\{T\}\.Unlike the one\-arm comparison in Appendix[G\.1](https://arxiv.org/html/2610.20997#A7.SS1), every observation contributes the same mean difference, regardless of which arm is selected\.

Underℙν\\mathbb\{P\}\_\{\\nu\}, conditional on the preceding history and the selected arm, each\(Yt\+β\)/σ\(Y\_\{t\}\+\\beta\)/\\sigmais standard Gaussian\. Consequently, for everyθ\>0\\theta\>0,

𝔼PνT​\[exp⁡\(−θ​MT−θ2​T2\)\]=1\.\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\\left\[\\exp\\left\(\-\\theta M\_\{T\}\-\\frac\{\\theta^\{2\}T\}\{2\}\\right\)\\right\]=1\.Also,𝔼PνT​\[MT2\]=T\\mathbb\{E\}\_\{P\_\{\\nu\}^\{T\}\}\[M\_\{T\}^\{2\}\]=T\. The density bound above therefore implies

𝔼𝖰T​\[MT2\]≤Tℙν​\(E\)<∞\.\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{T\}^\{2\}\]\\leq\\frac\{T\}\{\\mathbb\{P\}\_\{\\nu\}\(E\)\}<\\infty\.Thus, the expectations used below are finite\. The Gaussian identities are used underPνTP\_\{\\nu\}^\{T\}, not under the conditional distribution𝖰T\\mathsf\{Q\}\_\{T\}\.

Applying the entropy inequality from the proof of Proposition[1](https://arxiv.org/html/2610.20997#Thmproposition1)with

W=−θ​MT−θ2​T2W=\-\\theta M\_\{T\}\-\\frac\{\\theta^\{2\}T\}\{2\}gives

−𝔼𝖰T​\[MT\]≤DTθ\+θ​T2\.\-\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{T\}\]\\leq\\frac\{D\_\{T\}\}\{\\theta\}\+\\frac\{\\theta T\}\{2\}\.Optimizing overθ\>0\\theta\>0yields

−𝔼𝖰T​\[MT\]≤2​T​DT\.\-\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{T\}\]\\leq\\sqrt\{2TD\_\{T\}\}\.IfDT=0D\_\{T\}=0, the same conclusion follows by lettingθ↓0\\theta\\downarrow 0\.

It follows that

KL\(𝖰T∥PμT\)\\displaystyle\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\mu\}^\{T\}\)=DT\+𝔼𝖰T​\[log⁡d​PνTd​PμT\]\\displaystyle=D\_\{T\}\+\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\\left\[\\log\\frac\{dP\_\{\\nu\}^\{T\}\}\{dP\_\{\\mu\}^\{T\}\}\\right\]=DT\+g2​T2−g​𝔼𝖰T​\[MT\]\\displaystyle=D\_\{T\}\+\\frac\{g^\{2\}T\}\{2\}\-g\\mathbb\{E\}\_\{\\mathsf\{Q\}\_\{T\}\}\[M\_\{T\}\]≤DT\+g2​T2\+g​2​T​DT\\displaystyle\\leq D\_\{T\}\+\\frac\{g^\{2\}T\}\{2\}\+g\\sqrt\{2TD\_\{T\}\}=\(g​T2\+DT\)2\\displaystyle=\\left\(g\\sqrt\{\\frac\{T\}\{2\}\}\+\\sqrt\{D\_\{T\}\}\\right\)^\{2\}≤\(g​T2\+Cβ\)2\.\\displaystyle\\leq\\left\(g\\sqrt\{\\frac\{T\}\{2\}\}\+\\sqrt\{C\_\{\\beta\}\}\\right\)^\{2\}\.Since𝖰T​\(SuccTc\)=1\\mathsf\{Q\}\_\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)=1, the event inequality for relative entropy used in the preceding appendix gives

log1PμT​\(SuccTc\)≤KL\(𝖰T∥PμT\)\.\\log\\frac\{1\}\{P\_\{\\mu\}^\{T\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\}\\leq\\operatorname\{KL\}\(\\mathsf\{Q\}\_\{T\}\\\|P\_\{\\mu\}^\{T\}\)\.Therefore,

ℙμ𝒜T​\(SuccTc\)≥exp⁡\[−\(a\+βσ​T2\+Cβ\)2\]\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\_\{T\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\geq\\exp\\left\[\-\\left\(\\frac\{a\+\\beta\}\{\\sigma\}\\sqrt\{\\frac\{T\}\{2\}\}\+\\sqrt\{C\_\{\\beta\}\}\\right\)^\{2\}\\right\]\.\(56\)
For each fixedβ\>0\\beta\>0, dividing the negative logarithm byTTand taking the limit superior gives

lim supT→∞−1Tlogℙμ𝒜T\(SuccTc\)≤\(a\+β\)22​σ2\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\_\{T\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\frac\{\(a\+\\beta\)^\{2\}\}\{2\\sigma^\{2\}\}\.Lettingβ↓0\\beta\\downarrow 0afterwards yields

lim supT→∞−1Tlogℙμ𝒜T\(SuccTc\)≤a22​σ2\.\\limsup\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\_\{T\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\frac\{a^\{2\}\}\{2\\sigma^\{2\}\}\.No bound onCβC\_\{\\beta\}uniform inβ\\betais needed\.

##### Upper bound on the failure probability\.

Underμ=\(a,…,a\)\\mu=\(a,\\ldots,a\), the observations collected in chronological order satisfy

Y1,…,YT∼iid𝒩⁡\(a,σ2\)\.Y\_\{1\},\\ldots,Y\_\{T\}\\stackrel\{\{\\scriptstyle\\mathrm\{iid\}\}\}\{\{\\sim\}\}\\mathcal\{N\}\(a,\\sigma^\{2\}\)\.Indeed, conditional on the preceding history and the selected arm, the next observation always has distribution𝒩⁡\(a,σ2\)\\mathcal\{N\}\(a,\\sigma^\{2\}\)\. Thus, adaptive arm selection does not change the joint distribution of the observations in chronological order\.

OnSuccTc\\mathrm\{Succ\}\_\{T\}^\{c\}, equation \([4](https://arxiv.org/html/2610.20997#S3.E4)\) implies

λ​μ0\+∑s=1Ni​\(T\)Xi,s<z​σ​Ni​\(T\)\+λfor every​i∈\[K\]\.\\lambda\\mu\_\{0\}\+\\sum\_\{s=1\}^\{N\_\{i\}\(T\)\}X\_\{i,s\}<z\\sigma\\sqrt\{N\_\{i\}\(T\)\+\\lambda\}\\qquad\\text\{for every \}i\\in\[K\]\.Summing over arms gives

∑t=1TYt<z​σ​∑i=1KNi​\(T\)\+λ−K​λ​μ0\.\\sum\_\{t=1\}^\{T\}Y\_\{t\}<z\\sigma\\sum\_\{i=1\}^\{K\}\\sqrt\{N\_\{i\}\(T\)\+\\lambda\}\-K\\lambda\\mu\_\{0\}\.By the Cauchy–Schwarz inequality and∑iNi​\(T\)=T\\sum\_\{i\}N\_\{i\}\(T\)=T,

∑i=1KNi​\(T\)\+λ≤K​∑i=1K\(Ni​\(T\)\+λ\)=K⁡\(T\+K​λ\)\.\\sum\_\{i=1\}^\{K\}\\sqrt\{N\_\{i\}\(T\)\+\\lambda\}\\leq\\sqrt\{K\\sum\_\{i=1\}^\{K\}\(N\_\{i\}\(T\)\+\\lambda\)\}=\\sqrt\{K\(T\+K\\lambda\)\}\.Define

BT:=z​σ​K⁡\(T\+K​λ\)−K​λ​μ0\.B\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=z\\sigma\\sqrt\{K\(T\+K\\lambda\)\}\-K\\lambda\\mu\_\{0\}\.We have shown that

SuccTc⊆\{∑t=1TYt<BT\}\.\\mathrm\{Succ\}\_\{T\}^\{c\}\\subseteq\\left\\\{\\sum\_\{t=1\}^\{T\}Y\_\{t\}<B\_\{T\}\\right\\\}\.Since∑t=1TYt∼𝒩⁡\(a​T,σ2​T\)\\sum\_\{t=1\}^\{T\}Y\_\{t\}\\sim\\mathcal\{N\}\(aT,\\sigma^\{2\}T\),

ℙμ𝒜T​\(SuccTc\)≤Φ⁡\(BT−a​Tσ​T\)≤exp⁡\(−\(a​T−BT\)\+22​σ2​T\)\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\_\{T\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\Phi\\left\(\\frac\{B\_\{T\}\-aT\}\{\\sigma\\sqrt\{T\}\}\\right\)\\leq\\exp\\left\(\-\\frac\{\(aT\-B\_\{T\}\)\_\{\+\}^\{2\}\}\{2\\sigma^\{2\}T\}\\right\)\.\(57\)With all parameters fixed,BT/T→0B\_\{T\}/T\\to 0\. Therefore,

lim infT→∞−1Tlogℙμ𝒜T\(SuccTc\)≥a22​σ2\.\\liminf\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\_\{T\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\geq\\frac\{a^\{2\}\}\{2\\sigma^\{2\}\}\.Combining this with the preceding upper bound on the limit superior proves \([55](https://arxiv.org/html/2610.20997#A8.E55)\)\. ∎

### Appendix IUniform Sampling, Sequential Halving, and Separations

This appendix specifies the baseline algorithms and proves the guarantees in Section[6\.1](https://arxiv.org/html/2610.20997#S6.SS1)\. We then establish sample\-complexity separations from HTG on a family with one positive arm\.

Throughout, we use the Gaussian observation model and prior from Section[2](https://arxiv.org/html/2610.20997#S2), withσ,σ0\>0\\sigma,\\sigma\_\{0\}\>0andδ∈\(0,1/2\)\\delta\\in\(0,1/2\)\. Recallλ=σ2/σ02\\lambda=\\sigma^\{2\}/\\sigma\_\{0\}^\{2\},z=Φ−1​\(1−δ\)z=\\Phi^\{\-1\}\(1\-\\delta\), andc=2​z\+λ​\|μ0\|/σc=\\sqrt\{2\}\\,z\+\\sqrt\{\\lambda\}\|\\mu\_\{0\}\|/\\sigma\. Every algorithm uses all observations collected from each arm to update its posterior and makes the terminal recommendationJT∈arg⁡maxi∈\[K\]⁡Zi,Ni​\(T\)J\_\{T\}\\in\\arg\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\. Thus, by \([4](https://arxiv.org/html/2610.20997#S3.E4)\),

SuccTc=\{Zi,Ni​\(T\)<zfor everyi∈\[K\]\}\.\\mathrm\{Succ\}\_\{T\}^\{c\}=\\left\\\{Z\_\{i,N\_\{i\}\(T\)\}<z\\text\{ for every \}i\\in\[K\]\\right\\\}\.All ties are resolved by a fixed deterministic rule\. The guarantees below assumeμ⋆\>0\\mu\_\{\\star\}\>0, and we useσ2/02=\+∞\\sigma^\{2\}/0^\{2\}=\+\\infty\.

For the proofs, regard each arm as having an infinite sequence of potential observations, and define

Wi,n:=1σ​∑s=1n\(Xi,s−μi\)\.W\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\frac\{1\}\{\\sigma\}\\sum\_\{s=1\}^\{n\}\(X\_\{i,s\}\-\\mu\_\{i\}\)\.At every deterministicn≥1n\\geq 1,Wi,n∼𝒩⁡\(0,n\)W\_\{i,n\}\\sim\\mathcal\{N\}\(0,n\), independently across arms\. In particular,

Zi,n=n​μi/σ\+λ​μ0/σ\+Wi,nn\+λ\.Z\_\{i,n\}=\\frac\{n\\mu\_\{i\}/\\sigma\+\\lambda\\mu\_\{0\}/\\sigma\+W\_\{i,n\}\}\{\\sqrt\{n\+\\lambda\}\}\.\(58\)
#### I\.1Uniform sampling

Algorithm[2](https://arxiv.org/html/2610.20997#alg2)allocates observations round\-robin\. Its sample counts are deterministic: writingn=⌊T/K⌋n=\\lfloor T/K\\rfloor,

ni\(T\)=n\+𝟏\{i≤T−Kn\},i∈\[K\]\.n\_\{i\}\(T\)=n\+\\mathbf\{1\}\\\{i\\leq T\-Kn\\\},\\qquad i\\in\[K\]\.
Algorithm 2Uniform sampling with posterior\-based recommendation0:Integer budget

T≥KT\\geq K
1:Initialize the sample count of every arm to zero\.

2:for

t=0,…,T−1t=0,\\ldots,T\-1do

3:Select

At\+1=1\+\(tmodK\)A\_\{t\+1\}=1\+\(t\\bmod K\)\.

4:Sample arm

At\+1A\_\{t\+1\}and update its sample count and posterior using all its observations\.

5:endfor

6:Output

JT∈arg⁡maxi∈\[K\]⁡Zi,Ni​\(T\)J\_\{T\}\\in\\arg\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\.

###### Proposition 3\(Uniform\-sampling guarantees\)\.

Fix a mean vectorμ\\muwithμ⋆\>0\\mu\_\{\\star\}\>0\. For every integerT≥KT\\geq K,

ℙμUniform​\(SuccTc\)=∏i=1KΦ⁡\(z​1\+λni​\(T\)−μiσ​ni​\(T\)−λ​μ0σ​ni​\(T\)\)\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)=\\prod\_\{i=1\}^\{K\}\\Phi\\\!\\left\(z\\sqrt\{1\+\\frac\{\\lambda\}\{n\_\{i\}\(T\)\}\}\-\\frac\{\\mu\_\{i\}\}\{\\sigma\}\\sqrt\{n\_\{i\}\(T\)\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\_\{i\}\(T\)\}\}\\right\)\.\(59\)Ifn=⌊T/K⌋≥λn=\\lfloor T/K\\rfloor\\geq\\lambda, then

ℙμUniform​\(SuccTc\)≤exp⁡\[−12​\(μ⋆σ​n−c\)\+2\]\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\exp\\left\[\-\\frac\{1\}\{2\}\\left\(\\frac\{\\mu\_\{\\star\}\}\{\\sigma\}\\sqrt\{n\}\-c\\right\)\_\{\+\}^\{2\}\\right\]\.\(60\)Moreover, withKK,μ\\mu,σ2\\sigma^\{2\}, the prior parameters, andδ\\deltaheld fixed,

limT→∞−1TlogℙμUniform\(SuccTc\)=∑i=1K\(μi\)\+22​K​σ2=12​Hpos​\(μ\)\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)=\\frac\{\\sum\_\{i=1\}^\{K\}\(\\mu\_\{i\}\)\_\{\+\}^\{2\}\}\{2K\\sigma^\{2\}\}=\\frac\{1\}\{2H\_\{\\mathrm\{pos\}\}\(\\mu\)\}\.\(61\)

###### Proof\.

By \([58](https://arxiv.org/html/2610.20997#A9.E58)\), for every deterministic countni​\(T\)n\_\{i\}\(T\),

ℙμ​\(Zi,ni​\(T\)<z\)=Φ⁡\(z​1\+λni​\(T\)−μiσ​ni​\(T\)−λ​μ0σ​ni​\(T\)\)\.\\mathbb\{P\}\_\{\\mu\}\\\!\\left\(Z\_\{i,n\_\{i\}\(T\)\}<z\\right\)=\\Phi\\\!\\left\(z\\sqrt\{1\+\\frac\{\\lambda\}\{n\_\{i\}\(T\)\}\}\-\\frac\{\\mu\_\{i\}\}\{\\sigma\}\\sqrt\{n\_\{i\}\(T\)\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\_\{i\}\(T\)\}\}\\right\)\.The counts are deterministic and the observations are independent across arms\. Multiplying these probabilities proves \([59](https://arxiv.org/html/2610.20997#A9.E59)\)\.

For the finite\-budget bound, choose an armi⋆i\_\{\\star\}withμi⋆=μ⋆\\mu\_\{i\_\{\\star\}\}=\\mu\_\{\\star\}\. For everym≥λm\\geq\\lambda,

z​1\+λm−λ​μ0σ​m≤2​z\+λ​\|μ0\|σ=c\.z\\sqrt\{1\+\\frac\{\\lambda\}\{m\}\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{m\}\}\\leq\\sqrt\{2\}\\,z\+\\frac\{\\sqrt\{\\lambda\}\|\\mu\_\{0\}\|\}\{\\sigma\}=c\.Sinceni⋆​\(T\)≥n≥λn\_\{i\_\{\\star\}\}\(T\)\\geq n\\geq\\lambda, failure of every arm implies

ℙμUniform​\(SuccTc\)\\displaystyle\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)≤ℙμ​\(Zi⋆,ni⋆​\(T\)<z\)\\displaystyle\\leq\\mathbb\{P\}\_\{\\mu\}\\\!\\left\(Z\_\{i\_\{\\star\},n\_\{i\_\{\\star\}\}\(T\)\}<z\\right\)≤Φ⁡\(c−μ⋆σ​n\)\.\\displaystyle\\leq\\Phi\\\!\\left\(c\-\\frac\{\\mu\_\{\\star\}\}\{\\sigma\}\\sqrt\{n\}\\right\)\.The inequalityΦ\(−x\)≤exp\(−x\+2/2\)\\Phi\(\-x\)\\leq\\exp\(\-x\_\{\+\}^\{2\}/2\)gives \([60](https://arxiv.org/html/2610.20997#A9.E60)\)\.

For the asymptotic exponent, letai,Ta\_\{i,T\}denote the argument ofΦ\\Phiin theiith factor of \([59](https://arxiv.org/html/2610.20997#A9.E59)\)\. Sinceni​\(T\)/T→1/Kn\_\{i\}\(T\)/T\\to 1/K,

ai,T=−μiσ​ni​\(T\)\+z\+o⁡\(1\)\.a\_\{i,T\}=\-\\frac\{\\mu\_\{i\}\}\{\\sigma\}\\sqrt\{n\_\{i\}\(T\)\}\+z\+o\(1\)\.Ifμi\>0\\mu\_\{i\}\>0, Gaussian tail asymptotics give

−log⁡Φ⁡\(ai,T\)=μi22​σ2​ni​\(T\)\+o⁡\(T\)\.\-\\log\\Phi\(a\_\{i,T\}\)=\\frac\{\\mu\_\{i\}^\{2\}\}\{2\\sigma^\{2\}\}n\_\{i\}\(T\)\+o\(T\)\.Ifμi<0\\mu\_\{i\}<0, thenΦ⁡\(ai,T\)→1\\Phi\(a\_\{i,T\}\)\\to 1, whereas ifμi=0\\mu\_\{i\}=0, thenΦ⁡\(ai,T\)→Φ⁡\(z\)\>0\\Phi\(a\_\{i,T\}\)\\to\\Phi\(z\)\>0\. Hence the nonpositive arms contributeo⁡\(T\)o\(T\)to the negative logarithm of the product\. Summing over the positive arms and dividing byTTproves \([61](https://arxiv.org/html/2610.20997#A9.E61)\)\. ∎

In particular, for anyη∈\(0,1\)\\eta\\in\(0,1\), a sufficient budget forℙμUniform​\(SuccTc\)≤η\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\leq\\etais

T≥K⁡⌈max⁡\{1,λ,σ2μ⋆2​\(c\+2​log⁡1η\)2\}⌉\.T\\geq K\\left\\lceil\\max\\left\\\{1,\\lambda,\\frac\{\\sigma^\{2\}\}\{\\mu\_\{\\star\}^\{2\}\}\\left\(c\+\\sqrt\{2\\log\\frac\{1\}\{\\eta\}\}\\right\)^\{2\}\\right\\\}\\right\\rceil\.\(62\)This follows by substituting the resulting lower bound onn=⌊T/K⌋n=\\lfloor T/K\\rfloorinto \([60](https://arxiv.org/html/2610.20997#A9.E60)\)\.

#### I\.2Sequential halving

ForK≥2K\\geq 2, we use the equal\-stage\-budget SH allocation of[Karnin et al\. \(2013\)](https://arxiv.org/html/2610.20997#bib.bib5), with elimination based on cumulative posteriorZZ\-scores and the common all\-arm terminal recommendation\. Recall thatQ−1=⌈log2⁡K⌉Q\-1=\\lceil\\log\_\{2\}K\\rceil\. At each elimination stage, all active arms have equal cumulative sample counts, so ranking their posteriorZZ\-scores is equivalent to ranking their cumulative empirical means\.

Algorithm[3](https://arxiv.org/html/2610.20997#alg3)specifies the allocation, including rounding and leftover observations\. ForK≤T<K⁡\(Q−1\)K\\leq T<K\(Q\-1\), it uses round\-robin sampling to ensure that every arm is observed at least once\. An arm eliminated during SH receives no further observations but remains eligible for the terminal recommendation\.

Algorithm 3Sequential halving with posterior\-based elimination and recommendation0:Integers

K≥2K\\geq 2and

T≥KT\\geq K
1:Initialize the sample count of every arm to zero\.

2:if

T<K⁡\(Q−1\)T<K\(Q\-1\)then

3:Allocate all

TTobservations round\-robin, updating each sampled arm’s posterior using all its observations\.

4:else

5:Set

S1=\[K\]S\_\{1\}=\[K\]and

t=0t=0\.

6:for

r=1,…,Q−1r=1,\\ldots,Q\-1do

7:Set

kr=\|Sr\|k\_\{r\}=\|S\_\{r\}\|and

qr=⌊T/\(\(Q−1\)​kr\)⌋q\_\{r\}=\\left\\lfloor T/\(\(Q\-1\)k\_\{r\}\)\\right\\rfloor\.

8:Sample each arm in

SrS\_\{r\}an additional

qrq\_\{r\}times, in increasing arm order, updating its posterior after every observation\.

9:Set

t←t\+kr​qrt\\leftarrow t\+k\_\{r\}q\_\{r\}\.

10:Let

Sr\+1S\_\{r\+1\}contain the

⌈kr/2⌉\\lceil k\_\{r\}/2\\rceilarms in

SrS\_\{r\}with the largest

Zi,Ni​\(t\)Z\_\{i,N\_\{i\}\(t\)\}\.

11:endfor

12:Let

IIbe the unique arm in

SQS\_\{Q\}\.

13:Allocate the remaining

T−tT\-tobservations to

II, updating its posterior using all its observations\.

14:endif

15:Output

JT∈arg⁡maxi∈\[K\]⁡Zi,Ni​\(T\)J\_\{T\}\\in\\arg\\max\_\{i\\in\[K\]\}Z\_\{i,N\_\{i\}\(T\)\}\.

##### Budget accounting and possible sample counts\.

In the SH branch, the active\-set sizes are deterministic:kr=⌈K/2r−1⌉k\_\{r\}=\\lceil K/2^\{r\-1\}\\rceil\. In particular,kQ−1=2k\_\{Q\-1\}=2andkQ=1k\_\{Q\}=1\. Sincekr​qr≤T/\(Q−1\)k\_\{r\}q\_\{r\}\\leq T/\(Q\-1\), the elimination stages use at mostTTobservations\. Define

nr:=∑s=1rqs,D:=T−∑r=1Q−1krqr\.n\_\{r\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\sum\_\{s=1\}^\{r\}q\_\{s\},\\qquad D\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=T\-\\sum\_\{r=1\}^\{Q\-1\}k\_\{r\}q\_\{r\}\.\(63\)HereD≥0D\\geq 0is the deterministic leftover budget, andnrn\_\{r\}is the cumulative count of every arm active through stagerr\. Consequently, every terminal count belongs to the deterministic set

𝒞T:=\{n1,…,nQ−1,nQ−1\+D\},\|𝒞T\|≤Q\.\\mathcal\{C\}\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\\{n\_\{1\},\\ldots,n\_\{Q\-1\},n\_\{Q\-1\}\+D\\\},\\qquad\|\\mathcal\{C\}\_\{T\}\|\\leq Q\.\(64\)The identity of the final survivor is random, but its terminal count is alwaysnQ−1\+Dn\_\{Q\-1\}\+D\.

###### Theorem 3\(Finite\-budget guarantee for sequential halving\)\.

LetK≥2K\\geq 2andμ⋆\>0\\mu\_\{\\star\}\>0, and recallHSH​\(μ\)H\_\{\\mathrm\{SH\}\}\(\\mu\)from \([21](https://arxiv.org/html/2610.20997#S6.E21)\)\. Suppose the integer budget satisfies

T≥2​K​\(Q−1\)​max⁡\{1,λ\}\.T\\geq 2K\(Q\-1\)\\max\\\{1,\\lambda\\\}\.\(65\)For everyR\>0R\>0such that

T\>16​HSH​\(μ\)​\(c\+R\)2,T\>16H\_\{\\mathrm\{SH\}\}\(\\mu\)\(c\+R\)^\{2\},\(66\)Algorithm[3](https://arxiv.org/html/2610.20997#alg3)satisfies

ℙμSH\(SuccTc\)≤min\{1,6K\(Q−1\)e−R2/2\}\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{SH\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\min\\left\\\{1,\\,6K\(Q\-1\)e^\{\-R^\{2\}/2\}\\right\\\}\.\(67\)Consequently, forη∈\(0,1\)\\eta\\in\(0,1\), conditions \([65](https://arxiv.org/html/2610.20997#A9.E65)\) and

T\>16​HSH​\(μ\)​\(c\+2​log⁡6​K​\(Q−1\)η\)2T\>16H\_\{\\mathrm\{SH\}\}\(\\mu\)\\left\(c\+\\sqrt\{2\\log\\frac\{6K\(Q\-1\)\}\{\\eta\}\}\\right\)^\{2\}\(68\)implyℙμSH​\(SuccTc\)≤η\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{SH\}\}\(\\mathrm\{Succ\}\_\{T\}^\{c\}\)\\leq\\eta\.

###### Proof\.

Condition \([65](https://arxiv.org/html/2610.20997#A9.E65)\) ensures that the SH branch is used and that

qr≥T2​\(Q−1\)​kr,q1≥T2​K​\(Q−1\)≥max⁡\{1,λ\}\.q\_\{r\}\\geq\\frac\{T\}\{2\(Q\-1\)k\_\{r\}\},\\qquad q\_\{1\}\\geq\\frac\{T\}\{2K\(Q\-1\)\}\\geq\\max\\\{1,\\lambda\\\}\.\(69\)In particular, every count in𝒞T\\mathcal\{C\}\_\{T\}is at leastλ\\lambda\.

Consider the event

ℰR:=⋂i=1K⋂n∈𝒞T\{\|Wi,n\|≤Rn\}\.\\mathcal\{E\}\_\{R\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\bigcap\_\{i=1\}^\{K\}\\bigcap\_\{n\\in\\mathcal\{C\}\_\{T\}\}\\left\\\{\|W\_\{i,n\}\|\\leq R\\sqrt\{n\}\\right\\\}\.The set𝒞T\\mathcal\{C\}\_\{T\}is deterministic\. Gaussian tail bounds and a union bound therefore give

ℙμ\(ℰRc\)≤2KQe−R2/2≤6K\(Q−1\)e−R2/2\.\\mathbb\{P\}\_\{\\mu\}\(\\mathcal\{E\}\_\{R\}^\{c\}\)\\leq 2KQe^\{\-R^\{2\}/2\}\\leq 6K\(Q\-1\)e^\{\-R^\{2\}/2\}\.\(70\)The event is defined on the potential observation sequences, so this argument does not condition on an adaptively selected sample count\.

Work onℰR\\mathcal\{E\}\_\{R\}\. Forn∈𝒞Tn\\in\\mathcal\{C\}\_\{T\}, we haven≥λn\\geq\\lambdaand

z​1\+λn−λ​μ0σ​n≤c\.z\\sqrt\{1\+\\frac\{\\lambda\}\{n\}\}\-\\frac\{\\lambda\\mu\_\{0\}\}\{\\sigma\\sqrt\{n\}\}\\leq c\.Together with \([58](https://arxiv.org/html/2610.20997#A9.E58)\) andWi,n≥−R​nW\_\{i,n\}\\geq\-R\\sqrt\{n\}, this yields

μiσ​n≥c\+R⟹Zi,n≥z\.\\frac\{\\mu\_\{i\}\}\{\\sigma\}\\sqrt\{n\}\\geq c\+R\\quad\\Longrightarrow\\quad Z\_\{i,n\}\\geq z\.\(71\)We show that at least one arm satisfies this condition at its terminal count\.

*Case 1:*HSH​\(μ\)=\(Q−1\)​K​σ2/μ⋆2H\_\{\\mathrm\{SH\}\}\(\\mu\)=\(Q\-1\)K\\sigma^\{2\}/\\mu\_\{\\star\}^\{2\}\. Choosei⋆i\_\{\\star\}with meanμ⋆\\mu\_\{\\star\}\. Regardless of whether it is eliminated,Ni⋆​\(T\)≥q1N\_\{i\_\{\\star\}\}\(T\)\\geq q\_\{1\}\. By \([69](https://arxiv.org/html/2610.20997#A9.E69)\),

μ⋆σ​Ni⋆​\(T\)≥T​μ⋆22​K​\(Q−1\)​σ2=T2​HSH​\(μ\)\>c\+R\.\\frac\{\\mu\_\{\\star\}\}\{\\sigma\}\\sqrt\{N\_\{i\_\{\\star\}\}\(T\)\}\\geq\\sqrt\{\\frac\{T\\mu\_\{\\star\}^\{2\}\}\{2K\(Q\-1\)\\sigma^\{2\}\}\}=\\sqrt\{\\frac\{T\}\{2H\_\{\\mathrm\{SH\}\}\(\\mu\)\}\}\>c\+R\.Its terminal count belongs to𝒞T\\mathcal\{C\}\_\{T\}, so \([71](https://arxiv.org/html/2610.20997#A9.E71)\) proves posterior success\.

*Case 2:*HSH​\(μ\)=\(Q−1\)​∑i=1Kσ2/μi2<∞H\_\{\\mathrm\{SH\}\}\(\\mu\)=\(Q\-1\)\\sum\_\{i=1\}^\{K\}\\sigma^\{2\}/\\mu\_\{i\}^\{2\}<\\infty\. In this case, no arm has mean zero\. We first show that a positive arm survives every elimination stage\.

Suppose, to the contrary, that stagerreliminates all remaining positive arms\. Choose a positive armi∈Sri\\in S\_\{r\}\. Every retained armj∈Sr\+1j\\in S\_\{r\+1\}is negative and has posterior score at least that ofii\. Since both arms have countnrn\_\{r\},X¯j,nr≥X¯i,nr\\overline\{X\}\_\{j,n\_\{r\}\}\\geq\\overline\{X\}\_\{i,n\_\{r\}\}\. OnℰR\\mathcal\{E\}\_\{R\}, this implies

μj≥μi−2​σ​Rnr\>−2​σ​Rnr\.\\mu\_\{j\}\\geq\\mu\_\{i\}\-\\frac\{2\\sigma R\}\{\\sqrt\{n\_\{r\}\}\}\>\-\\frac\{2\\sigma R\}\{\\sqrt\{n\_\{r\}\}\}\.Thus each retained arm satisfiesσ2/μj2\>nr/\(4​R2\)≥qr/\(4​R2\)\\sigma^\{2\}/\\mu\_\{j\}^\{2\}\>n\_\{r\}/\(4R^\{2\}\)\\geq q\_\{r\}/\(4R^\{2\}\)\. There are at leastkr/2k\_\{r\}/2such arms\. Hence

∑j:μj<0σ2μj2\>kr​qr8​R2≥T16​\(Q−1\)​R2\.\\sum\_\{j\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{j\}<0\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{j\}^\{2\}\}\>\\frac\{k\_\{r\}q\_\{r\}\}\{8R^\{2\}\}\\geq\\frac\{T\}\{16\(Q\-1\)R^\{2\}\}\.It follows thatHSH​\(μ\)\>T/\(16​R2\)H\_\{\\mathrm\{SH\}\}\(\\mu\)\>T/\(16R^\{2\}\), contradicting \([66](https://arxiv.org/html/2610.20997#A9.E66)\)\. Therefore the final survivorIIhas positive mean\.

Since the last elimination stage has two active arms,

NI​\(T\)≥qQ−1≥T4​\(Q−1\)\.N\_\{I\}\(T\)\\geq q\_\{Q\-1\}\\geq\\frac\{T\}\{4\(Q\-1\)\}\.Moreover,σ2/μI2≤∑i=1Kσ2/μi2=HSH​\(μ\)/\(Q−1\)\\sigma^\{2\}/\\mu\_\{I\}^\{2\}\\leq\\sum\_\{i=1\}^\{K\}\\sigma^\{2\}/\\mu\_\{i\}^\{2\}=H\_\{\\mathrm\{SH\}\}\(\\mu\)/\(Q\-1\)\. Consequently,

μIσ​NI​\(T\)≥T4​HSH​\(μ\)\>c\+R\.\\frac\{\\mu\_\{I\}\}\{\\sigma\}\\sqrt\{N\_\{I\}\(T\)\}\\geq\\sqrt\{\\frac\{T\}\{4H\_\{\\mathrm\{SH\}\}\(\\mu\)\}\}\>c\+R\.Applying \([71](https://arxiv.org/html/2610.20997#A9.E71)\) atNI​\(T\)=nQ−1\+DN\_\{I\}\(T\)=n\_\{Q\-1\}\+Dproves posterior success\.

At least one of the two cases applies, becauseμ⋆\>0\\mu\_\{\\star\}\>0makesHSH​\(μ\)H\_\{\\mathrm\{SH\}\}\(\\mu\)finite\. We have therefore shownℰR⊆SuccT\\mathcal\{E\}\_\{R\}\\subseteq\\mathrm\{Succ\}\_\{T\}\. Combining this inclusion with \([70](https://arxiv.org/html/2610.20997#A9.E70)\) proves \([67](https://arxiv.org/html/2610.20997#A9.E67)\)\. SubstitutingR=2​log⁡\(6​K​\(Q−1\)/η\)R=\\sqrt\{2\\log\(6K\(Q\-1\)/\\eta\)\}proves the final assertion\. ∎

For completeness, the comparison in \([22](https://arxiv.org/html/2610.20997#S6.E22)\) follows directly from the definitions:

HHTG​\(μ\)\\displaystyle H\_\{\\mathrm\{HTG\}\}\(\\mu\)≤min⁡\{∑i=1Kσ2μi2,Hpos​\(μ\)\}\\displaystyle\\leq\\min\\left\\\{\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},H\_\{\\mathrm\{pos\}\}\(\\mu\)\\right\\\}≤min⁡\{∑i=1Kσ2μi2,K​σ2μ⋆2\}=HSH​\(μ\)Q−1\.\\displaystyle\\leq\\min\\left\\\{\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\},\\frac\{K\\sigma^\{2\}\}\{\\mu\_\{\\star\}^\{2\}\}\\right\\\}=\\frac\{H\_\{\\mathrm\{SH\}\}\(\\mu\)\}\{Q\-1\}\.The second inequality uses∑i\(μi\)\+2≥μ⋆2\\sum\_\{i\}\(\\mu\_\{i\}\)\_\{\+\}^\{2\}\\geq\\mu\_\{\\star\}^\{2\}\. The same definitions also giveHHTG​\(μ\)≤Hpos​\(μ\)H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\leq H\_\{\\mathrm\{pos\}\}\(\\mu\)\. These inequalities compare the leading complexities in the guarantees; they do not assert a finite\-budget ordering of the actual failure probabilities\.

#### I\.3Strict separations

We now establish separations in the actual sample budgets required for posterior success\. Fixσ,σ0\>0\\sigma,\\sigma\_\{0\}\>0,δ∈\(0,1/2\)\\delta\\in\(0,1/2\), and a centered priorμ0=0\\mu\_\{0\}=0\. Consider the family

μ1=σK,μ2=⋯=μK=−σ,K=2ℓ,ℓ≥1\.\\mu\_\{1\}=\\frac\{\\sigma\}\{K\},\\qquad\\mu\_\{2\}=\\cdots=\\mu\_\{K\}=\-\\sigma,\\qquad K=2^\{\\ell\},\\quad\\ell\\geq 1\.\(72\)For a sampling algorithm𝒜\\mathcal\{A\}, define

𝒯𝒜\(η;μ\):=min\{T∈ℕ:T≥K,ℙμ𝒜\(SuccTc\)≤η\}\.\\mathcal\{T\}\_\{\\mathcal\{A\}\}\(\\eta;\\mu\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\min\\left\\\{T\\in\\mathbb\{N\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}T\\geq K,\\;\\mathbb\{P\}\_\{\\mu\}^\{\\mathcal\{A\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq\\eta\\right\\\}\.\(73\)We first letη↓0\\eta\\downarrow 0withKKand all model parameters fixed, and then compare the dependence of the resulting coefficients onKK\.

###### Theorem 4\(Separation from uniform sampling and sequential halving\)\.

On the family \([72](https://arxiv.org/html/2610.20997#A9.E72)\),

limη↓0𝒯Uniform​\(η,μ\)log⁡\(1/η\)\\displaystyle\\lim\_\{\\eta\\downarrow 0\}\\frac\{\\mathcal\{T\}\_\{\\mathrm\{Uniform\}\}\(\\eta;\\mu\)\}\{\\log\(1/\\eta\)\}=2​K3,\\displaystyle=2K^\{3\},\(74\)limη↓0𝒯SH​\(η,μ\)log⁡\(1/η\)\\displaystyle\\lim\_\{\\eta\\downarrow 0\}\\frac\{\\mathcal\{T\}\_\{\\mathrm\{SH\}\}\(\\eta;\\mu\)\}\{\\log\(1/\\eta\)\}=2​K3​\(Q−1\)K−1,\\displaystyle=\\frac\{2K^\{3\}\(Q\-1\)\}\{K\-1\},lim supη↓0𝒯HTG​\(η,μ\)log⁡\(1/η\)\\displaystyle\\limsup\_\{\\eta\\downarrow 0\}\\frac\{\\mathcal\{T\}\_\{\\mathrm\{HTG\}\}\(\\eta;\\mu\)\}\{\\log\(1/\\eta\)\}≤192​\(K2\+K−1\)\.\\displaystyle\\leq 192\(K^\{2\}\+K\-1\)\.Consequently, in this order of limits, uniform sampling and the specified SH allocation can require factorsΩ⁡\(K\)\\Omega\(K\)andΩ⁡\(log⁡K\)\\Omega\(\\log K\)more observations, respectively, than HTG\.

###### Proof\.

*Uniform sampling\.*There is one positive arm, with meanσ/K\\sigma/K, soHpos​\(μ\)=K3H\_\{\\mathrm\{pos\}\}\(\\mu\)=K^\{3\}\. Proposition[3](https://arxiv.org/html/2610.20997#Thmproposition3)gives

limT→∞−1TlogℙμUniform\(SuccTc\)=12​K3\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{Uniform\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)=\\frac\{1\}\{2K^\{3\}\}\.\(75\)
*Sequential halving\.*For all sufficiently largeTT, the SH branch is used\. SinceK=2ℓK=2^\{\\ell\}andQ−1=ℓQ\-1=\\ell, its active\-set sizes arekr=K/2r−1k\_\{r\}=K/2^\{r\-1\}\. Recallnrn\_\{r\}andDDfrom \([63](https://arxiv.org/html/2610.20997#A9.E63)\), and setn⋆:=nQ−1\+Dn\_\{\\star\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=n\_\{Q\-1\}\+D, the count arm11receives if it survives every stage\.

The rounding remainder satisfies

0≤D<∑r=1Q−1kr=2​K−2\.0\\leq D<\\sum\_\{r=1\}^\{Q\-1\}k\_\{r\}=2K\-2\.Therefore, for fixedKK,

q1T⟶1K⁡\(Q−1\),n⋆T⟶K−1K⁡\(Q−1\)\.\\frac\{q\_\{1\}\}\{T\}\\longrightarrow\\frac\{1\}\{K\(Q\-1\)\},\\qquad\\frac\{n\_\{\\star\}\}\{T\}\\longrightarrow\\frac\{K\-1\}\{K\(Q\-1\)\}\.\(76\)
Define the deterministic\-count failure probability

aT:=ℙμ​\(Z1,n⋆<z\)=Φ⁡\(z​1\+λn⋆−n⋆K\)\.a\_\{T\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\mathbb\{P\}\_\{\\mu\}\(Z\_\{1,n\_\{\\star\}\}<z\)=\\Phi\\left\(z\\sqrt\{1\+\\frac\{\\lambda\}\{n\_\{\\star\}\}\}\-\\frac\{\\sqrt\{n\_\{\\star\}\}\}\{K\}\\right\)\.Gaussian tail asymptotics and \([76](https://arxiv.org/html/2610.20997#A9.E76)\) imply

limT→∞−1TlogaT=K−12​K3​\(Q−1\)=:αK\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log a\_\{T\}=\\frac\{K\-1\}\{2K^\{3\}\(Q\-1\)\}=\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\alpha\_\{K\}\.\(77\)
We compareaTa\_\{T\}with the actual failure probability by bounding elimination of arm11and certification of a negative arm\.

LetETE\_\{T\}be the event that arm11is eliminated\. If this happens at stagerr, some negative armjjhasX¯j,nr≥X¯1,nr\\overline\{X\}\_\{j,n\_\{r\}\}\\geq\\overline\{X\}\_\{1,n\_\{r\}\}\. At the deterministic countnrn\_\{r\},

X¯j,nr−X¯1,nr∼𝒩⁡\(−σ⁡\(1\+1K\),2​σ2nr\)\.\\overline\{X\}\_\{j,n\_\{r\}\}\-\\overline\{X\}\_\{1,n\_\{r\}\}\\sim\\mathcal\{N\}\\left\(\-\\sigma\\left\(1\+\\frac\{1\}\{K\}\\right\),\\frac\{2\\sigma^\{2\}\}\{n\_\{r\}\}\\right\)\.A union bound over all negative arms and stages gives

ℙμSH​\(ET\)≤\(K−1\)​\(Q−1\)​exp⁡\[−q1​\(1\+1/K\)24\]=:dT\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{SH\}\}\(E\_\{T\}\)\\leq\(K\-1\)\(Q\-1\)\\exp\\left\[\-\\frac\{q\_\{1\}\(1\+1/K\)^\{2\}\}\{4\}\\right\]=\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}d\_\{T\}\.\(78\)This bound uses the potential observations at deterministic counts; it does not condition on either arm being active\.

Next, letFTF\_\{T\}be the event that some negative arm has a terminal posterior score at leastzz\. Forj≥2j\\geq 2and a deterministic countnn, the centered prior gives

Zj,n≥z⟹Wj,n≥n\+z​n\+λ≥n\.Z\_\{j,n\}\\geq z\\quad\\Longrightarrow\\quad W\_\{j,n\}\\geq n\+z\\sqrt\{n\+\\lambda\}\\geq n\.Henceℙμ\(Zj,n≥z\)≤e−n/2\\mathbb\{P\}\_\{\\mu\}\(Z\_\{j,n\}\\geq z\)\\leq e^\{\-n/2\}\. Every terminal count belongs to𝒞T\\mathcal\{C\}\_\{T\}, whose elements are at leastq1q\_\{1\}\. Thus

ℙμSH\(FT\)≤\(K−1\)Qe−q1/2=:bT\.\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{SH\}\}\(F\_\{T\}\)\\leq\(K\-1\)Qe^\{\-q\_\{1\}/2\}=\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}b\_\{T\}\.\(79\)
OnETcE\_\{T\}^\{c\}, arm11has terminal countn⋆n\_\{\\star\}\. Consequently,

aT−dT−bT≤ℙμSH​\(SuccTc\)≤aT\+dT\.a\_\{T\}\-d\_\{T\}\-b\_\{T\}\\leq\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{SH\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)\\leq a\_\{T\}\+d\_\{T\}\.\(80\)The lower bound follows by requiringZ1,n⋆<zZ\_\{1,n\_\{\\star\}\}<ztogether withETc∩FTcE\_\{T\}^\{c\}\\cap F\_\{T\}^\{c\}; the upper bound follows because, outsideETE\_\{T\}, terminal failure requiresZ1,n⋆<zZ\_\{1,n\_\{\\star\}\}<z\.

By \([76](https://arxiv.org/html/2610.20997#A9.E76)\),

limT→∞−1TlogdT=\(1\+1/K\)24​K​\(Q−1\),limT→∞−1TlogbT=12​K​\(Q−1\)\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log d\_\{T\}=\\frac\{\(1\+1/K\)^\{2\}\}\{4K\(Q\-1\)\},\\qquad\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log b\_\{T\}=\\frac\{1\}\{2K\(Q\-1\)\}\.Both exponents are strictly larger thanαK\\alpha\_\{K\}for everyK≥2K\\geq 2\. ThusdT/aT→0d\_\{T\}/a\_\{T\}\\to 0andbT/aT→0b\_\{T\}/a\_\{T\}\\to 0\. The sandwich \([80](https://arxiv.org/html/2610.20997#A9.E80)\) implies

limT→∞−1TlogℙμSH\(SuccTc\)=αK=K−12​K3​\(Q−1\)\.\\lim\_\{T\\to\\infty\}\-\\frac\{1\}\{T\}\\log\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{SH\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)=\\alpha\_\{K\}=\\frac\{K\-1\}\{2K^\{3\}\(Q\-1\)\}\.\(81\)
*Converting the baseline exponents into sample budgets\.*For any of the specified algorithms, the failure probability is strictly positive at every finite budget\. Indeed, under the centered prior, the event that the firstTTpotential observations of every arm are negative has positive probability and forces every sampled arm to have a negative posterior score\.

More generally, supposepT\>0p\_\{T\}\>0for every finiteTTand−T−1​log⁡pT→r\>0\-T^\{\-1\}\\log p\_\{T\}\\to r\>0\. For everyε∈\(0,r\)\\varepsilon\\in\(0,r\)and all sufficiently largeTT,

e−\(r\+ε\)​T≤pT≤e−\(r−ε\)​T\.e^\{\-\(r\+\\varepsilon\)T\}\\leq p\_\{T\}\\leq e^\{\-\(r\-\\varepsilon\)T\}\.The finitely many smaller budgets have failure probabilities bounded away from zero\. It follows that

min\{T≥K:pT≤η\}∼1rlog1η,η↓0\.\\min\\\{T\\geq K\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}p\_\{T\}\\leq\\eta\\\}\\sim\\frac\{1\}\{r\}\\log\\frac\{1\}\{\\eta\},\\qquad\\eta\\downarrow 0\.This conclusion does not requirepTp\_\{T\}to be monotone inTT\. Applying it to \([75](https://arxiv.org/html/2610.20997#A9.E75)\) and \([81](https://arxiv.org/html/2610.20997#A9.E81)\) proves the first two statements in \([74](https://arxiv.org/html/2610.20997#A9.E74)\)\.

*HTG\.*On the family \([72](https://arxiv.org/html/2610.20997#A9.E72)\),

∑i=1Kσ2μi2=K2\+K−1\.\\sum\_\{i=1\}^\{K\}\\frac\{\\sigma^\{2\}\}\{\\mu\_\{i\}^\{2\}\}=K^\{2\}\+K\-1\.The definition \([8](https://arxiv.org/html/2610.20997#S4.E8)\) therefore givesHHTG​\(μ\)≤K2\+K−1H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\leq K^\{2\}\+K\-1\. For fixedKK, the offsetT0T\_\{0\}in Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)is finite and independent ofη\\eta\.

Fix anya\>192​HHTG​\(μ\)a\>192H\_\{\\mathrm\{HTG\}\}\(\\mu\)and chooseT=⌈a​log⁡\(1/η\)⌉T=\\lceil a\\log\(1/\\eta\)\\rceil\. For sufficiently smallη\\eta, Theorem[1](https://arxiv.org/html/2610.20997#Thmtheorem1)yields

ℙμHTG​\(SuccTc\)\\displaystyle\\mathbb\{P\}\_\{\\mu\}^\{\\mathrm\{HTG\}\}\\bigl\(\\mathrm\{Succ\}\_\{T\}^\{c\}\\bigr\)≤2​K​T​exp⁡\(T0192​HHTG​\(μ\)\)​ηa/\(192​HHTG​\(μ\)\)\\displaystyle\\leq 2KT\\exp\\left\(\\frac\{T\_\{0\}\}\{192H\_\{\\mathrm\{HTG\}\}\(\\mu\)\}\\right\)\\eta^\{a/\(192H\_\{\\mathrm\{HTG\}\}\(\\mu\)\)\}≤η\.\\displaystyle\\leq\\eta\.Here the exponent ofη\\etais strictly larger than one, whereasT=O⁡\(log⁡\(1/η\)\)T=O\(\\log\(1/\\eta\)\)\. Lettinga↓192​HHTG​\(μ\)a\\downarrow 192H\_\{\\mathrm\{HTG\}\}\(\\mu\)gives

lim supη↓0𝒯HTG​\(η,μ\)log⁡\(1/η\)≤192​HHTG​\(μ\)≤192​\(K2\+K−1\)\.\\limsup\_\{\\eta\\downarrow 0\}\\frac\{\\mathcal\{T\}\_\{\\mathrm\{HTG\}\}\(\\eta;\\mu\)\}\{\\log\(1/\\eta\)\}\\leq 192H\_\{\\mathrm\{HTG\}\}\(\\mu\)\\leq 192\(K^\{2\}\+K\-1\)\.This proves the third statement\.

Finally, these budget bounds imply

lim infη↓0𝒯Uniform​\(η,μ\)𝒯HTG​\(η,μ\)\\displaystyle\\liminf\_\{\\eta\\downarrow 0\}\\frac\{\\mathcal\{T\}\_\{\\mathrm\{Uniform\}\}\(\\eta;\\mu\)\}\{\\mathcal\{T\}\_\{\\mathrm\{HTG\}\}\(\\eta;\\mu\)\}≥K396​\(K2\+K−1\),\\displaystyle\\geq\\frac\{K^\{3\}\}\{96\(K^\{2\}\+K\-1\)\},lim infη↓0𝒯SH​\(η,μ\)𝒯HTG​\(η,μ\)\\displaystyle\\liminf\_\{\\eta\\downarrow 0\}\\frac\{\\mathcal\{T\}\_\{\\mathrm\{SH\}\}\(\\eta;\\mu\)\}\{\\mathcal\{T\}\_\{\\mathrm\{HTG\}\}\(\\eta;\\mu\)\}≥K3​\(Q−1\)96​\(K−1\)​\(K2\+K−1\)\.\\displaystyle\\geq\\frac\{K^\{3\}\(Q\-1\)\}\{96\(K\-1\)\(K^\{2\}\+K\-1\)\}\.The right\-hand sides grow asΩ⁡\(K\)\\Omega\(K\)andΩ⁡\(log⁡K\)\\Omega\(\\log K\), respectively, asKKincreases through powers of two\. ∎

The two separations have different allocation explanations\. Uniform sampling devotes only a1/K1/Kfraction of the budget to the unique positive arm\. For SH, even when this arm survives every stage, its terminal sample count is asymptotic toT⁡\(1−1/K\)/\(Q−1\)T\(1\-1/K\)/\(Q\-1\)\. Moreover, the probability of eliminating the positive arm is asymptotically negligible compared with the probability that the surviving positive arm fails to obtain a certificate\. Thus, the additionallog⁡K\\log Kcost of SH arises from splitting the budget acrossΘ⁡\(log⁡K\)\\Theta\(\\log K\)elimination stages, rather than from erroneous elimination\.

The baseline asymptotics above are exact, whereas the HTG result is an upper bound on its required budget\.

### Appendix JFlat\-Prior Frequentist Interpretation

We give the short derivation underlying Section[6\.2](https://arxiv.org/html/2610.20997#S6.SS2)\. Recall thatλ=σ2/σ02\\lambda=\\sigma^\{2\}/\\sigma\_\{0\}^\{2\}and

Zi,n=λ​μ0\+n​X¯i,nσ​n\+λ\.Z\_\{i,n\}=\\frac\{\\lambda\\mu\_\{0\}\+n\\overline\{X\}\_\{i,n\}\}\{\\sigma\\sqrt\{n\+\\lambda\}\}\.Lettingσ02→∞\\sigma\_\{0\}^\{2\}\\to\\inftywithμ0\\mu\_\{0\}fixed givesλ→0\\lambda\\to 0, and hence

Zi,n⟶n​X¯i,nσ\.Z\_\{i,n\}\\longrightarrow\\frac\{\\sqrt\{n\}\\,\\overline\{X\}\_\{i,n\}\}\{\\sigma\}\.This is the usual known\-variance Gaussian test statistic for

H0,i:μi≤0versusH1,i:μi\>0\.H\_\{0,i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\\leq 0\\qquad\\text\{versus\}\\qquad H\_\{1,i\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\.Accordingly, define the one\-sidedpp\-value

pi,n:=1−Φ⁡\(n​X¯i,nσ\)\.p\_\{i,n\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=1\-\\Phi\\left\(\\frac\{\\sqrt\{n\}\\,\\overline\{X\}\_\{i,n\}\}\{\\sigma\}\\right\)\.Since the posterior positivity probability isΦ⁡\(Zi,n\)\\Phi\(Z\_\{i,n\}\), the flat\-prior limit gives

ℙ\(μi\>0∣Xi,1:n\)=1−pi,n\.\\mathbb\{P\}\(\\mu\_\{i\}\>0\\mid X\_\{i,1\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}n\}\)=1\-p\_\{i,n\}\.
BecauseΦ\\Phiis increasing, ranking arms by posteriorZZ\-score is equivalent to ranking them by increasingpp\-value\. Thus HTG’s halving phase retains the active arms with the smallest currentpp\-values, its greedy phase samples an arm with the smallest currentpp\-value, and its terminal recommendation satisfies

JT∈arg⁡mini∈\[K\]⁡pi,Ni​\(T\)\.J\_\{T\}\\in\\arg\\min\_\{i\\in\[K\]\}p\_\{i,N\_\{i\}\(T\)\}\.Finally, sincez=Φ−1​\(1−δ\)z=\\Phi^\{\-1\}\(1\-\\delta\),

Zi,n≥z⟺pi,n≤δ\.Z\_\{i,n\}\\geq z\\quad\\Longleftrightarrow\\quad p\_\{i,n\}\\leq\\delta\.Therefore,

SuccT=\{mini∈\[K\]pi,Ni​\(T\)≤δ\}\.\\mathrm\{Succ\}\_\{T\}=\\left\\\{\\min\_\{i\\in\[K\]\}p\_\{i,N\_\{i\}\(T\)\}\\leq\\delta\\right\\\}\.Hence, in the flat\-prior limit, HTG can be interpreted in terms of one\-sided Gaussian test statistics andpp\-values\.

### Appendix KExperimental Details and Additional Results

We supplement Section[7](https://arxiv.org/html/2610.20997#S7)with full parameter sweeps, comparisons across the number of arms, and allocation trajectories\. All experiments compare HTG, uniform sampling, and posterior\-based sequential halving \(SH\), using observation varianceσ2=1\\sigma^\{2\}=1, working prior𝒩⁡\(0,1\)\\mathcal\{N\}\(0,1\), and credibility toleranceδ=0\.01\\delta=0\.01\. Every posterior incorporates all observations collected from the corresponding arm, and terminal recommendation maximizes the posteriorZZ\-score over all arms, including those removed during halving\. Success is evaluated after exactlyTTobservations; an earlier posterior certificate does not terminate a run\.

We use10,00010\{,\}000Monte Carlo repetitions per setting and budget\. Success\-probability plots show pointwise95%95\\%Wilson confidence intervals\. The intervals for empirical budget thresholds and mean allocation fractions are described separately below\. Throughout this appendix, the means are fixed within each setting: the reported probabilities are fixed\-instance success probabilities\.

#### K\.1Full parameter sweeps

Figures[2](https://arxiv.org/html/2610.20997#A11.F2)and[3](https://arxiv.org/html/2610.20997#A11.F3)extend the two instance families in Section[7](https://arxiv.org/html/2610.20997#S7)across the full tested parameter ranges\. We retainK=32K=32and positive meana=0\.1a=0\.1, and use the same budget grid as in the main experiments:1616approximately logarithmically spaced budgets from576576to65,53665\{,\}536, rounded to multiples ofKK\. The value of the varied parameter is indicated in each panel\.

##### Negative competitors\.

Figure[2](https://arxiv.org/html/2610.20997#A11.F2)considers

μ=\(a,−b,…,−b\),a=0\.1\.\\mu=\(a,\-b,\\ldots,\-b\),\\qquad a=0\.1\.This family corresponds to the single\-positive\-arm example in Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3)\. Sinceσ2=1\\sigma^\{2\}=1,

Hcap=1a2\+K−1\(a\+b\)2,Hpos=Ka2\.H\_\{\\mathrm\{cap\}\}=\\frac\{1\}\{a^\{2\}\}\+\\frac\{K\-1\}\{\(a\+b\)^\{2\}\},\\qquad H\_\{\\mathrm\{pos\}\}=\\frac\{K\}\{a^\{2\}\}\.Increasingbbtherefore reduces the separation component ofHcapH\_\{\\mathrm\{cap\}\}without changing the positive mean orHposH\_\{\\mathrm\{pos\}\}\. The sweep places the difficult\-negative and easy\-negative settings from the main text within a broader range of competitor means\. In particular, the well\-separated setting exhibits a substantial advantage for HTG, consistent with its ability to concentrate observations on the positive arm once the negative competitors can be screened effectively\.

Figure 2:Full negative\-competitor sweep\. One arm has mean0\.10\.1, and the remaining3131arms have mean−b\-b, with the value ofbbindicated in each panel\. Curves show terminal posterior success probability versus budget for HTG, uniform sampling, and SH\. Error bars show pointwise95%95\\%Wilson Monte Carlo confidence intervals based on10,00010\{,\}000repetitions\.
##### Certificates on negative recommendations\.

Whenbbis small, sampling noise can produce a posterior certificate for an arm whose true mean is negative\. Such an outcome is included in the posterior success objective\. More precisely,

ℙμ𝒜​\(SuccT\)=\\displaystyle\\mathbb\{P\}^\{\\mathcal\{A\}\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\}\)=\{\}ℙμ𝒜​\(SuccT,μJT\>0\)\\displaystyle\\mathbb\{P\}^\{\\mathcal\{A\}\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\},\\mu\_\{J\_\{T\}\}\>0\)\+ℙμ𝒜​\(SuccT,μJT≤0\)\.\\displaystyle\+\\mathbb\{P\}^\{\\mathcal\{A\}\}\_\{\\mu\}\(\\mathrm\{Succ\}\_\{T\},\\mu\_\{J\_\{T\}\}\\leq 0\)\.This distinction helps interpret uniform sampling’s initial lead in theb=0\.02b=0\.02setting: a higher posterior success probability need not correspond to a higher probability of certifying a truly positive recommendation\. The reported success curves retain both terms, as required by the objective\.

##### Multiple positive arms\.

Figure[3](https://arxiv.org/html/2610.20997#A11.F3)considers

μ=\(a,…,a⏟m​arms,−1,…,−1⏟K−m​arms\),a=0\.1\.\\mu=\\bigl\(\\underbrace\{a,\\ldots,a\}\_\{m\\text\{ arms\}\},\\underbrace\{\-1,\\ldots,\-1\}\_\{K\-m\\text\{ arms\}\}\\bigr\),\\qquad a=0\.1\.The sweep varies the number of positive arms without changing their individual means\. Here,

Hpos=Km​a2=3200m\.H\_\{\\mathrm\{pos\}\}=\\frac\{K\}\{ma^\{2\}\}=\\frac\{3200\}\{m\}\.Additional positive arms provide more opportunities to obtain a certificate, the same mechanism illustrated by the all\-positive example in Section[4\.3](https://arxiv.org/html/2610.20997#S4.SS3)\. Uniform sampling benefits substantially from this multiplicity, and the main\-text comparison betweenm=4m=4andm=16m=16shows a narrowing of HTG’s advantage over SH\. The full sweep documents how the methods compare across the remaining tested values ofmm\.

Figure 3:Full positive\-arm\-count sweep\. AmongK=32K=32arms,mmhave mean0\.10\.1and the remainingK−mK\-mhave mean−1\-1, withmmindicated in each panel\. Curves show terminal posterior success probability versus budget\. Error bars show pointwise95%95\\%Wilson Monte Carlo confidence intervals based on10,00010\{,\}000repetitions\.

#### K\.2Scaling with the number of arms

We next examine how the budget required for successful certification changes withKKon the instance family

μ\(K\)=\(1/K,−1,…,−1\),K∈\{8,16,32,64\}\.\\mu^\{\(K\)\}=\(1/K,\-1,\\ldots,\-1\),\\qquad K\\in\\\{8,16,32,64\\\}\.The positive mean decreases as the number of arms increases, while the negative means remain fixed\. This is the same family considered in Appendix[I\.3](https://arxiv.org/html/2610.20997#A9.SS3)\. In the high\-confidence regime, the analysis there gives the sample\-complexity scalings

THTG=O⁡\(K2​log​1η\),TSH=Θ⁡\(K2​log​K​log​1η\),TUniform=Θ⁡\(K3​log​1η\),T\_\{\\mathrm\{HTG\}\}=O\\\!\\left\(K^\{2\}\\log\\frac\{1\}\{\\eta\}\\right\),\\qquad T\_\{\\mathrm\{SH\}\}=\\Theta\\\!\\left\(K^\{2\}\\log K\\log\\frac\{1\}\{\\eta\}\\right\),\\qquad T\_\{\\mathrm\{Uniform\}\}=\\Theta\\\!\\left\(K^\{3\}\\log\\frac\{1\}\{\\eta\}\\right\),where1−η1\-\\etais the target posterior success probability\. Thus, suppressing the common dependence onη\\eta, the predicted dependence on the number of arms isK2K^\{2\},K2​log⁡KK^\{2\}\\log K, andK3K^\{3\}, respectively\.

Letp^𝒜,K​\(T\)\\widehat\{p\}\_\{\\mathcal\{A\},K\}\(T\)denote the empirical terminal success probability of method𝒜\\mathcal\{A\}at budgetTT, and let𝒢𝒜,K\\mathcal\{G\}\_\{\\mathcal\{A\},K\}be its tested budget grid\. We report

T^0\.9𝒜\(K\):=min\{T∈𝒢𝒜,K:p^𝒜,K\(T\)≥0\.9\}\.\\widehat\{T\}\_\{0\.9\}^\{\\mathcal\{A\}\}\(K\)\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}=\\min\\left\\\{T\\in\\mathcal\{G\}\_\{\\mathcal\{A\},K\}\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\widehat\{p\}\_\{\\mathcal\{A\},K\}\(T\)\\geq 0\.9\\right\\\}\.Thus,T^0\.9𝒜​\(K\)\\widehat\{T\}\_\{0\.9\}^\{\\mathcal\{A\}\}\(K\)is the first tested budget reaching90%90\\%empirical success\.

Figure[4](https://arxiv.org/html/2610.20997#A11.F4)reports these thresholds together with their normalized versions:

T^0\.9HTG​\(K\)K2,T^0\.9SH​\(K\)K2​log⁡K,T^0\.9Uniform​\(K\)K3\.\\frac\{\\widehat\{T\}\_\{0\.9\}^\{\\mathrm\{HTG\}\}\(K\)\}\{K^\{2\}\},\\qquad\\frac\{\\widehat\{T\}\_\{0\.9\}^\{\\mathrm\{SH\}\}\(K\)\}\{K^\{2\}\\log K\},\\qquad\\frac\{\\widehat\{T\}\_\{0\.9\}^\{\\mathrm\{Uniform\}\}\(K\)\}\{K^\{3\}\}\.These normalizations correspond to theKK\-dependence predicted by the theoretical rates above\. Because the denominators differ across methods, the vertical ordering in the normalized plot should not be interpreted as a direct performance ranking\.

HTG requires the smallest threshold budget at every tested value ofKK, followed by SH and then uniform sampling\. The normalized thresholds range from21\.621\.6to27\.327\.3for HTG, from19\.119\.1to21\.721\.7for SH, and from12\.912\.9to13\.013\.0for uniform sampling\. Their relatively limited variation over the tested values ofKKis consistent with the predictedK2K^\{2\},K2​log⁡KK^\{2\}\\log K, andK3K^\{3\}dependences, respectively\. The underlying success\-versus\-budget curves are provided in Figure[5](https://arxiv.org/html/2610.20997#A11.F5)\.

Figure 4:Scaling with the number of arms onμ\(K\)=\(1/K,−1,…,−1\)\\mu^\{\(K\)\}=\(1/K,\-1,\\ldots,\-1\)\. Left: first tested budget reaching90%90\\%empirical terminal success for each method\. Right: the same thresholds divided byK2K^\{2\}for HTG,K2​log⁡KK^\{2\}\\log Kfor SH, andK3K^\{3\}for uniform sampling\. The logarithm is natural\. Error bars show95%95\\%bootstrap intervals\. Thresholds are computed on the tested budget grids\.Figure 5:Terminal posterior success probability versus budget for theKK\-scaling study\. Each setting usesμ\(K\)=\(1/K,−1,…,−1\)\\mu^\{\(K\)\}=\(1/K,\-1,\\ldots,\-1\), withK∈\{8,16,32,64\}K\\in\\\{8,16,32,64\\\}\. Error bars show pointwise95%95\\%Wilson Monte Carlo confidence intervals based on10,00010\{,\}000repetitions per method and budget\. These curves underlie the threshold summaries in Figure[4](https://arxiv.org/html/2610.20997#A11.F4)\.
#### K\.3Allocation behavior

We examine allocation trajectories at budgetsT=2,048T=2\{,\}048andT=7,200T=7\{,\}200for the four representative settings from the main experiments\. The single\-positive\-arm settings useb∈\{0\.02,1\}b\\in\\\{0\.02,1\\\}, and the multiple\-positive\-arm settings usem∈\{4,16\}m\\in\\\{4,16\\\}\. All haveK=32K=32and positive meana=0\.1a=0\.1\.

For each timet≤Tt\\leq T, we consider the fraction of observations allocated to positive arms collectively,

1t∑i:μi\>0Ni\(t\),\\frac\{1\}\{t\}\\sum\_\{i\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\}N\_\{i\}\(t\),and the largest fraction allocated to any individual positive arm,

1tmaxi:μi\>0Ni\(t\)\.\\frac\{1\}\{t\}\\max\_\{i\\mathrel\{\\mathop\{\\mathchar 58\\relax\}\}\\mu\_\{i\}\>0\}N\_\{i\}\(t\)\.With a single positive arm, both quantities reduce toN1​\(t\)/tN\_\{1\}\(t\)/t\.

The figures plot the Monte Carlo average of these allocation fractions at eachtt\. For the largest individual allocation, the maximum is taken within each repetition before averaging, so the most\-sampled positive arm need not have the same label across repetitions\. Error bars show pointwise95%95\\%Monte Carlo confidence intervals for the corresponding mean fractions\. The dotted vertical line marks the end of HTG’s halving phase and the start of its greedy phase\.

##### Negative competitors\.

Figure[6](https://arxiv.org/html/2610.20997#A11.F6)shows how the separation of negative competitors affects allocation to the single positive arm\. AtT=2,048T=2\{,\}048, HTG allocates an average of51\.5%51\.5\\%of observations to the positive arm whenb=1b=1, compared with15\.4%15\.4\\%whenb=0\.02b=0\.02\. Uniform sampling allocates1/K=3\.125%1/K=3\.125\\%in either setting\. This allocation difference supports the interpretation of the success curves: easier negative competitors allow HTG to direct more of its budget toward collecting evidence for the positive arm\.

Figure 6:Allocation to the single positive arm forμ=\(0\.1,−b,…,−b\)\\mu=\(0\.1,\-b,\\ldots,\-b\), withK=32K=32andb∈\{0\.02,1\}b\\in\\\{0\.02,1\\\}\. The two rows correspond to budgetsT=2,048T=2\{,\}048andT=7,200T=7\{,\}200\. Curves show mean allocation fractions across10,00010\{,\}000repetitions, with pointwise95%95\\%Monte Carlo confidence intervals\. The dotted vertical line marks the end of HTG’s halving phase\.
##### Multiple positive arms\.

Figures[7](https://arxiv.org/html/2610.20997#A11.F7)and[8](https://arxiv.org/html/2610.20997#A11.F8)separate total allocation to positive arms from concentration on an individual positive arm\. These quantities can favor different methods\. For example, withm=16m=16andT=2,048T=2\{,\}048, SH allocates more observations to positive arms collectively than HTG:90\.2%90\.2\\%versus83\.6%83\.6\\%\. However, HTG’s mean largest individual positive\-arm allocation is substantially greater:48\.4%48\.4\\%versus21\.2%21\.2\\%for SH\. Thus, the fraction of observations assigned to positive arms alone does not explain the terminal success probabilities; the distribution of those observations among the positive arms also matters\.

Figure 7:Total allocation to positive arms\. AmongK=32K=32arms,m∈\{4,16\}m\\in\\\{4,16\\\}have mean0\.10\.1and the remaining arms have mean−1\-1\. The two rows correspond to budgetsT=2,048T=2\{,\}048andT=7,200T=7\{,\}200\. Curves show mean total positive\-arm allocation fractions across10,00010\{,\}000repetitions, with pointwise95%95\\%Monte Carlo confidence intervals\. The dotted vertical line marks the end of HTG’s halving phase\.Figure 8:Largest individual positive\-arm allocation\. Settings and row organization match Figure[7](https://arxiv.org/html/2610.20997#A11.F7)\. The largest positive\-arm allocation fraction is computed within each repetition and then averaged over10,00010\{,\}000repetitions\. Error bars show pointwise95%95\\%Monte Carlo confidence intervals\. The dotted vertical line marks the end of HTG’s halving phase\.