Fundamental Limitations of Fixed-Budget Best-Arm Identification Motti Goldberger Yale University
Abstract. In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across 𝐾 arms. Each sample provides noisy feedback about that arm’s mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several
arXiv:2607.11635v1 [cs.LG] 13 Jul 2026
adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle’s error decay rate uniformly across all problem instances. We answer this in the negative. For any 𝐾 ≥ 3 and for rewards drawn from any one-parameter natural exponential family, we show −1 log(𝐾 ) times that of the static that for any algorithm, there is at least one instance where the error decay rate is at most 1 + 8 oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity. Key words: Ranking-and-Selection, Best-Arm Identification, Multi-Armed Bandits
1.
Introduction
Best-arm identification (BAI) in multi-armed bandits is the problem of a decision maker who sequentially collects samples to identify the best arm from a set of alternatives. Each arm generates independent rewards from a distribution with an unknown mean, and the goal is to identify the arm with the largest mean. Also referred to as Ranking-and-Selection, BAI arises in settings such as sequential selection in clinical trials, A/B testing, new product development, and simulation optimization. There are two dominant formulations of BAI. In fixed-confidence identification, algorithms are designed to minimize the expected number of samples required to correctly identify the best arm at a prespecified confidence level. In fixed-budget identification, the total number of samples is fixed in advance, and algorithms are designed to minimize the probability of incorrect identification. A BAI problem is specified by the unknown mean rewards of the alternatives; we call this specification a problem instance. A central goal is to characterize the difficulty of a given problem instance—how ‘hard’ it is to identify the best arm. For fixed-confidence identification, Garivier and Kaufmann (2016) provide a complete answer in the asymptotic regime. They show that there is an instance-dependent lower bound on the expected number of samples required to achieve a target confidence level, and that a single algorithm (Track-and-Stop) achieves this bound on every instance. When such a lower bound exists, and a single algorithm achieves it uniformly over all instances, we say the problem admits a complexity. 1
2
The fixed-budget setting is less understood. Qin (2022) posed the open question of whether fixed-budget BAI has a complexity. Degenne (2023) formalized this question and showed that a complexity does not exist in certain special cases. In this paper, we show the fundamental result that when there are at least three arms with rewards drawn from any one-parameter natural exponential family (NEF), fixed-budget best-arm identification does not admit a complexity. 1.1.
The Fixed-Budget Setting
A problem instance with 𝐾 arms is described by its mean vector 𝜇 = (𝜇1 , . . . , 𝜇 𝐾 ) , where 𝑖 ∗ (𝜇) denotes the (assumed unique) arm with the largest mean reward. An algorithm with fixed budget 𝑇 sequentially collects samples, then selects an arm 𝑖ˆ𝑇 . On instance 𝜇, 𝑝 𝜇,𝑇 := P 𝜇 𝑖ˆ𝑇 ≠ 𝑖 ∗ (𝜇) denotes the probability of incorrect 1 identification. The relevant asymptotic performance measure is lim inf 𝑇→∞ 𝑇1 log 𝑝𝜇,𝑇 , the exponential decay
rate of the error probability. Informally, we say fixed-budget BAI has complexity Γ∗ (𝜇) if the following two conditions are satisfied (Degenne 2023). (i) (Universal upper bound). For every algorithm and every instance 𝜇, 1 1 ≤ Γ∗ (𝜇). lim inf log 𝑇→∞ 𝑇 𝑝 𝜇,𝑇 (ii) (Uniform achievability). There exists a single algorithm such that for every instance 𝜇, 1 1 lim inf log = Γ∗ (𝜇). 𝑇→∞ 𝑇 𝑝 𝜇,𝑇 ∗ (𝜇) , which A natural benchmark to measure the performance of an algorithm is the static oracle Γ𝑠𝑜 is, conceptually, the ‘best’ error decay rate achievable by a non-adaptive strategy that samples each arm a fixed proportion of the time, with proportions chosen optimally given knowledge of 𝜇. Glynn and Juneja (2004) characterize the optimal static oracle proportions. However, the static oracle is not the answer to the complexity question: it is possible that fully adaptive algorithms can achieve a better error decay rate. But to prove the non-existence of a complexity, the static oracle benchmark is sufficient by the following ∗ (𝜇) for all 𝜇 , since condition (i) must argument. Any candidate complexity Γ∗ (𝜇) must satisfy Γ∗ (𝜇) ≥ Γ𝑠𝑜
hold for every algorithm, including the static oracle strategy at 𝜇. Consequently, to rule out the existence of ∗ (𝜇) uniformly over all instances. a complexity, it is enough to show that no single algorithm can achieve Γ𝑠𝑜
In particular, if one proves that for any algorithm there exists an instance 𝜇 such that 1 1 ∗ ≤ 𝑐 Γ𝑠𝑜 (𝜇) for some constant 𝑐 < 1, lim inf log 𝑇→∞ 𝑇 𝑝 𝜇,𝑇 then condition (ii) does not hold, and fixed-budget BAI does not have a complexity. 1.2.
Relation to Ranking and Selection
The fixed-budget BAI problem arises in the ranking-and-selection/simulation-optimization literature, where one allocates a finite simulation budget to maximize the probability of identifying the best arm (often referred to as the best system). A common optimality target in adaptive algorithm design is for the empirical sampling proportions to converge to the optimal static allocation; see, e.g., (Shin et al. 2018, Chen and Ryzhov 2019,
3
2023, Avci et al. 2021). However, convergence of the allocation proportions to the static oracle proportions does not guarantee matching its error decay rate (Glynn and Juneja 2011, Wu and Zhou 2018). Until this paper, it has remained an open question whether one can design a procedure whose error probability decays at the static oracle rate. We show that the answer is negative when 𝐾 ≥ 3: no adaptive procedure can match the static oracle rate uniformly over all instances. 1.3.
Prior Work
Fixed-budget BAI has been studied extensively in the machine learning literature, with early work focusing on elimination algorithms (Audibert et al. 2010, Karnin et al. 2013). Their guarantees are expressed in terms of gap-based hardness measures (e.g., 𝐻2 (𝜇) = max 𝑗 ∈ [𝐾 ] 𝑗/Δ2𝑗 where Δ 𝑘 := 𝜇1 − 𝜇 𝑘 ). In particular, the Successive Rejects algorithm achieves error bounds of the form exp − Θ(𝑇/(𝐻2 (𝜇) log 𝐾)) . Carpentier and Locatelli (2016) derive lower bounds on the error exponent in terms of 𝐻2 (𝜇) , showing that the Successive Rejects guarantees are on the order of minimax optimal. Under the minimax optimality criterion, Komiyama et al. (2022) characterize the optimal worst-case exponential decay rate for general hardness measure 𝐻 . They also propose an algorithm designed to attain the optimal rate, but it is computationally prohibitive. More recently, Wang et al. (2023) develop tools for analyzing the performance of adaptive sampling algorithms from a large-deviation perspective, which sharpen the error-exponent analysis of Successive Rejects and motivate a new elimination algorithm (Continuous Rejects) with a better guarantee. ∗ (𝜇) uniformly However, these results leave open the question of whether a single algorithm can match Γ𝑠𝑜
over all instances (Qin 2022). Degenne (2023) formalize this question through difficulty ratios: the factor by which an algorithm’s error decay rate falls short of the oracle on instance 𝜇. They show that there is no complexity when 𝐾 = 2 with Bernoulli rewards, as well as when 𝐾 ≥ 𝑒 80/3 and rewards follow a Gaussian distribution with variance 1. Kaufmann et al. (2016) show that for 𝐾 = 2 with Gaussian rewards, the optimal allocation is the Neyman allocation (Neyman 1934), and the problem does have a complexity. 1.4.
Contribution
For 𝐾 ≥ 3 with rewards from any one-parameter NEF, we show that for every adaptive algorithm, there exists −1 ∗ (𝜇) . It follows that for any class an instance where the error decay rate is at most 1 + 81 log(𝐾) times Γ𝑠𝑜 of algorithms that contains the static proportion algorithms, there is no complexity. This builds on Degenne (2023) to fill that gap when 3 ≤ 𝐾 ≤ 𝑒 80/3 for Gaussian rewards with variance 1, and extends the negative result to all regular one-parameter NEFs. Table 1 summarizes what was known and the gap we fill. Organization. Section 2 formally introduces fixed-budget best-arm identification, the static oracle, and complexity. Section 3 proves the negative result for Gaussian arms with variance 1. Section 4 uses the argument from Section 3 together with a local quadratic approximation of the Kullback–Leibler (KL) divergence to extend the result to all one-parameter NEFs. Finally, Section 5 discusses implications of the result and surveys alternative theoretical targets suggested in recent work.
4 Table 1
2.
Known results on the existence of a complexity.
Arms
Distribution
Complexity? Reference
𝐾 =2 𝐾 =2 𝐾 ≥ 𝑒 80/3 𝐾 ≥3
Gaussian Bernoulli Gaussian variance 1 One-parameter NEF
Yes No No No
Kaufmann et al. (2016) Degenne (2023) Degenne (2023) This paper
Preliminaries
Consider 𝐾 arms with unknown mean vector 𝜇 = (𝜇1 , . . . , 𝜇 𝐾 ) ∈ Θ𝐾 , where Θ ⊆ R is an open interval. We assume the best arm is unique: 𝑖 ∗ (𝜇) := arg max 𝜇 𝑘 ,
[𝐾] := {1, . . . , 𝐾 },
𝑘 ∈ [𝐾 ]
and define Θ𝑢𝐾 := {𝜇 ∈ Θ𝐾 : 𝑖 ∗ (𝜇) is unique}. Sampling arm 𝑘 yields an independent draw from distribution 𝜈 𝜇𝑘 , where {𝜈 𝜃 : 𝜃 ∈ Θ} is a known parametric family with mean 𝜃 . An algorithm with fixed budget 𝑇 samples
arms 𝐴1 , . . . , 𝐴𝑇 ∈ [𝐾] sequentially, possibly adaptively based on observed rewards, and outputs a selection 𝑖ˆ𝑇 ∈ [𝐾] . We work with algorithm families A = (A𝑇 )𝑇 ≥1 , where A𝑇 denotes the prescribed algorithm for
budget 𝑇 . The error probability of algorithm family A on instance 𝜇 is 𝑝 𝜇,𝑇 (A𝑇 ) := P 𝜇 (𝑖ˆ𝑇 ≠ 𝑖 ∗ (𝜇)). Define the set of consistent algorithm families as o n Ccons (Θ) := A = (A𝑇 )𝑇 ≥1 : ∀ 𝜇 ∈ Θ𝑢𝐾 , lim 𝑝 𝜇,𝑇 (A𝑇 ) = 0 . 𝑇→∞
Note that all static proportion algorithms that allocate nonzero sampling proportion to each arm are in Ccons (Θ) (Degenne 2023).
2.1.
The Static Oracle
Consider fixed allocation proportions in the interior of the simplex 𝜔 = (𝜔1 , . . . , 𝜔 𝐾 ) ∈ Δ0𝐾 := {𝜔 ∈ (0, 1) 𝐾 : Í 𝑘 𝜔 𝑘 = 1} . A static strategy samples arm 𝑘 approximately 𝜔 𝑘 𝑇 times and recommends the arm with the highest empirical mean. Given a static allocation strategy 𝜔, the instance-dependent exponential error decay rate is given by 1 1 log = Γ(𝜇, 𝜔), 𝑇→∞ 𝑇 𝑝 𝜇,𝑇 lim
where
Γ(𝜇, 𝜔) :=
inf
𝐾 ∑︁
𝜔 𝑘 KL(𝜆 𝑘 , 𝜇 𝑘 )
𝜆∈Alt( 𝜇) 𝑘=1
and Alt(𝜇) := {𝜆 ∈ Θ𝐾 : ∃ 𝑗 ≠ 𝑖 ∗ (𝜇) such that 𝜆 𝑗 ≥ 𝜆 𝑖∗ ( 𝜇) } is the set of alternative instances where 𝑖 ∗ (𝜇) is not the unique best arm (Glynn and Juneja 2004, Degenne 2023). The static oracle chooses the best allocation 𝜔 knowing 𝜇, which yields the error decay rate and hardness ∗ Γ𝑠𝑜 (𝜇) := sup Γ(𝜇, 𝜔), 𝜔 ∈Δ0𝐾
𝐻𝑠𝑜 (𝜇) :=
1 ∗ (𝜇) . Γ𝑠𝑜
Here 𝐻𝑠𝑜 (𝜇) quantifies the asymptotic difficulty of the BAI task for the static oracle on instance 𝜇.
5
2.2.
Existence of Complexity
Following Degenne (2023), we formalize what it means for a complexity to exist. Define ℎ 𝜇,𝑇 (A𝑇 ) :=
𝑇 log(1/𝑝 𝜇,𝑇 (A𝑇 ))
∈ [0, ∞],
with ℎ 𝜇,𝑇 = 0 if 𝑝 𝜇,𝑇 = 0 and ℎ 𝜇,𝑇 = +∞ if 𝑝 𝜇,𝑇 = 1. For a benchmark difficulty function 𝐻 : Θ𝑢𝐾 → (0, ∞) , the difficulty ratio 𝑅 𝐻,𝑇 (·) measures how well algorithm family A performs relative to 𝐻 : 𝑅 𝐻,𝑇 (A, 𝜇) :=
ℎ 𝜇,𝑇 (A𝑇 ) , 𝐻 (𝜇)
and
𝑅 𝐻,∞ (A, 𝜇) := lim sup 𝑅 𝐻,𝑇 (A, 𝜇). 𝑇→∞
D EFINITION 1 (E XISTENCE OF C OMPLEXITY ). Let C be a class of algorithm families. A function 𝐻 : Θ𝑢𝐾 → (0, ∞) is a complexity for C iff:
(i) inf A ∈ C inf 𝜇∈Θ𝑢𝐾 𝑅 𝐻,∞ (A, 𝜇) ≥ 1. (ii) There exists A ∗ ∈ C such that sup 𝜇∈Θ𝑢𝐾 𝑅 𝐻,∞ (A ∗ , 𝜇) ≤ 1. In Definition 1, condition (i) requires 𝐻 (𝜇) to be a universal lower bound on the asymptotic hardness. Condition (ii) requires some algorithm to achieve this bound uniformly over all instances. The class of adaptive algorithms contains all static proportion algorithms, including the static oracle proportions at 𝜇, so ( 𝜇) if 𝐻 satisfies (i), then 𝐻𝐻𝑠𝑜( 𝜇) ≥ 1. Therefore, if 𝐻𝑠𝑜 fails condition (ii), then 𝐻 must also fail this condition,
and fixed-budget BAI does not admit a complexity. We establish the negative result by showing that for 𝐾 ≥ 3, 𝐻𝑠𝑜 fails condition (ii). Our proofs rely on the following theorem from Degenne (2023).
T HEOREM 1 (Degenne 2023, Theorem 3). Fix a benchmark 𝐻 (·) > 0, an instance 𝜇 ∈ Θ𝑢𝐾 , and a nonempty set D (𝜇) ⊆ Alt(𝜇) ∩ Θ𝑢𝐾 . For any A ∈ Ccons (Θ) , ( ! −1 sup 𝑅 𝐻,∞ (A, 𝜆) 𝜆∈ D ( 𝜇)
≤ sup
inf
𝐻 (𝜆)
𝜔 ∈Δ𝐾 𝜆∈ D ( 𝜇)
𝐾 ∑︁
) 𝜔 𝑘 KL(𝜇 𝑘 , 𝜆 𝑘 ) .
(1)
𝑘=1
Degenne’s proof of Theorem 1 uses the change of measure argument and data processing inequality common in the multi-armed bandit literature (Garivier et al. 2019, Degenne 2023) to bound the performance of any adaptive algorithm by a static optimization over 𝜔 ∈ Δ𝐾 . To show that a complexity does not exist, we use this inequality with benchmark 𝐻𝑠𝑜 and construct 𝜇 and a set of instances D (𝜇) ⊆ Alt(𝜇) ∩ Θ𝑢𝐾 such that the right-hand side is less than 1.
3.
Gaussian Rewards
As a building block for the more general result in Section 4, we start by considering the setting where each 2
. Throughout this section, arm has Gaussian rewards with variance 1, so KL(N (𝑎, 1) ∥N (𝑏, 1)) = (𝑎−𝑏) 2 Θ = R. Lemma 1 states that for a static allocation 𝜔 ∈ Δ0𝐾 , the error decay rate is determined by the hardest-
to-distinguish challenger arm 𝑗 ≠ 𝑖 ∗ (𝜇) , and that the optimal static oracle allocation balances sampling between the best arm and each challenger based on their distance.
6
L EMMA 1 (Gaussian Static Oracle). Let 𝜇 ∈ Θ𝑢𝐾 and 𝑏 = 𝑖 ∗ (𝜇) . For any static algorithm with proportions 𝜔 ∈ Δ0𝐾 , 𝜔 𝑏 𝜔 𝑗 (𝜇 𝑏 − 𝜇 𝑗 ) 2 · 𝑗≠𝑏 𝜔 𝑏 + 𝜔 𝑗 2
Γ(𝜇, 𝜔) = min
and
∗ Γ𝑠𝑜 (𝜇) = max Γ(𝜇, 𝜔). 𝜔 ∈Δ0𝐾
Degenne (2023) proved that for Gaussian variance 1 rewards, every consistent algorithm family A satisfies 3 sup 𝜇∈Θ𝑢𝐾 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ 80 log 𝐾 . This exceeds 1 when 𝐾 ≥ 𝑒 80/3 , which implies no complexity in that
regime. Here we strengthen this by deriving a lower bound on the difficulty ratio that is of the same logarithmic order and is larger than 1 for every 𝐾 ≥ 3. T HEOREM 2. For 𝐾 ≥ 3 and Gaussian variance 1 rewards, 𝐾 ∑︁ 1 1 > 1 + log(𝐾). inf sup 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ 1 + √︁ 2 A ∈ Ccons (Θ) 𝜇∈Θ𝐾 8 𝑢 𝑗=3 (1 + 𝑗 − 1) Proof:
Fix arbitrary A ∈ Ccons (Θ) . We start by giving the principles of the proof. The key will be to
construct a baseline instance 𝑥 and a family of instances {𝜆 𝐴 } ∪ {𝜆 𝐵,3 , . . . , 𝜆 𝐵,𝐾 } ⊆ Alt(𝑥) ∩ Θ𝑢𝐾 . Instance 𝜆 𝐴 differs from 𝑥 only on arms 1 and 2, so distinguishing 𝑥 from 𝜆 𝐴 requires substantial sampling of these
two arms. In contrast, for each 𝑗 ∈ {3, . . . , 𝐾 }, instance 𝜆 𝐵, 𝑗 makes arm 𝑗 optimal and leaves all other arms unchanged. So distinguishing 𝑥 from 𝜆 𝐵, 𝑗 requires substantial sampling of arm 𝑗 . Since we do not know the true instance in advance, we must allow for the possibility that 𝜇 is any of {𝜆 𝐴 } ∪ {𝜆 𝐵,3 , . . . , 𝜆 𝐵,𝐾 }. For each such 𝜇, the baseline 𝑥 belongs to Alt(𝜇) , so correctly identifying the best arm on 𝜇 requires collecting enough evidence to separate 𝜇 from 𝑥 . But these separations rely on different indices across the family (arms 1, 2 for 𝜆 𝐴 versus arm 𝑗 for 𝜆 𝐵, 𝑗 ), so a single sampling allocation cannot be simultaneously optimal for all
of them. We show this forces at least one instance in the family to satisfy the first inequality in Theorem 2. The proof proceeds in the following steps. Step 1 constructs a sequence of instance families indexed by 𝐿 and gives intuition for why these instances are chosen. Step 2 shows that for each 𝐿 , the right-hand side
of (1) is bounded above by −1 𝐾
1 ª © ∑︁ ® + 𝑜 𝐿 (1). 1 + √︁ 2 (1 + 𝑗 − 1) 𝑗=3 ¬ « Step 3 applies Theorem 1 and concludes by letting 𝐿 → ∞ so that the 𝑜 𝐿 (1) terms vanish.
Step 1: Instance construction. Fix an integer 𝐿 ≥ 𝐾 and define a baseline instance 𝑥 ( 𝐿) ∈ Θ𝑢𝐾 and alternative instances 𝜆 𝐴, (𝜆 𝐵, 𝑗 ) 𝐾𝑗=3 ∈ Θ𝑢𝐾 by 0, ( 𝐿) 𝑥 𝑘 = −1, 𝑘 −𝐿 ,
𝑘 = 1, 𝑘 = 2, 3 ≤ 𝑘 ≤ 𝐾,
√ − 𝐿, √ 𝜆 𝑘𝐴 = −1 + 𝐿, 𝑘 −𝐿 ,
𝑘 = 1, 𝑘 = 2, 3 ≤ 𝑘 ≤ 𝐾,
Note D 𝐿 := {𝜆 𝐴 } ∪ {𝜆 𝐵,3 , . . . , 𝜆 𝐵,𝐾 } ⊆ Alt(𝑥 ( 𝐿) ) ∩ Θ𝑢𝐾 .
0, −1, 𝐵, 𝑗 √ 𝜆𝑘 = 𝐿 𝑗 𝐿, −𝐿 𝑘 ,
𝑘 = 1, 𝑘 = 2, 3 ≤ 𝑘 ≤ 𝐾, 𝑘 = 𝑗, 3 ≤ 𝑘 ≤ 𝐾, 𝑘 ≠ 𝑗 .
7
Our goal is to show sup
𝐾 n ∑︁ o min 𝐻𝑠𝑜 (𝜆) 𝜔 𝑘 KL 𝑥 𝑘( 𝐿) , 𝜆 𝑘 < 1.
𝜔 ∈Δ𝐾 𝜆∈ D 𝐿
𝑘=1
The novel insight is to construct instances so that the minimum over 𝜆 ∈ D 𝐿 reduces to a minimum of linear terms in 𝜔. In particular o n o n ∑︁ min 𝐻𝑠𝑜 (𝜆) 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘 ) ≤ (1 + 𝑜 𝐿 (1)) min 𝜔1 + 𝜔2 , 𝑐 3 𝜔3 , . . . , 𝑐 𝐾 𝜔 𝐾 , 𝜆∈ D 𝐿
(2)
𝑘
for positive coefficients {𝑐 𝑗 } 𝐾𝑗=3 . Given that (2) holds, then taking the supremum w.r.t. 𝜔 and letting 𝐿 → ∞ −1 Í shows the left-hand side of (2) is less than 1 + 𝐾𝑗=3 𝑐 −1 . This immediately gives us a difficulty ratio 𝑗 larger than one for all 𝐾 ≥ 3, which is our main objective. Within the set of instances that satisfy (2), we get Í a tighter bound the larger 𝐾𝑗=3 𝑐 −1 𝑗 is. √ Í How we will get linear terms in (2). For 𝜆 𝐴, only arms 1, 2 change by 𝐿 , so 𝑘 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘𝐴) = (𝜔1 + 𝜔2 ) · 𝐿2 . We will show 𝐻𝑠𝑜 (𝜆 𝐴) is at most 2/𝐿 up to a (1 + 𝑜 𝐿 (1)) factor, which makes the product Í 𝐻𝑠𝑜 (𝜆 𝐴) 𝑘 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘𝐴) at most 𝜔1 + 𝜔2 up to a (1 + 𝑜 𝐿 (1)) factor. For 𝜆 𝐵, 𝑗 only arm 𝑗 changes √ Í 2 𝑗+1 𝐵, 𝑗 from −𝐿 𝑗 to 𝐿 𝑗 𝐿 , thus 𝑘 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘 ) = 𝜔 𝑗 · 𝐿 2 (1 + 𝑜 𝐿 (1)) . We will show 𝐻𝑠𝑜 (𝜆 𝐵, 𝑗 ) is at most √︁ 2(1 + 𝑗 − 1) 2 /𝐿 2 𝑗+1 up to a (1 + 𝑜 𝐿 (1)) factor, so the 𝐿 2 𝑗+1 cancels and leaves a finite coefficient 𝑐 𝑗
multiplying 𝜔 𝑗 . Making 𝑐 𝑗 ’s small. The coefficients 𝑐 𝑗 are determined by the optimal static oracle allocation to differentiate 𝑥 ( 𝐿) and 𝜆 𝐵, 𝑗 . On a high level, each 𝑐 𝑗 is smaller when there are fewer contender arms close to the best, and
the allocation can be concentrated on them. 𝜆 𝐵, 𝑗 and 𝑥 ( 𝐿) only differ at index 𝑗 and the values 𝑥 𝑘( 𝐿) = −𝐿 𝑘 √ 𝐵, 𝑗 𝐵, 𝑗 are chosen so that 𝜆 𝑗 − 𝜆𝑖 = 𝐿 𝑗 𝐿 (1 + 𝑜 𝐿 (1)) , for arms 𝑖 = 1, . . . , 𝑗 − 1, whereas every arm 𝑘 > 𝑗 has √ 𝐵, 𝑗 𝐵, 𝑗 difference 𝜆 𝑗 − 𝜆 𝑘 = 𝐿 𝑘 (1 + 𝑜 𝐿 (1)) ≫ 𝐿 𝑗 𝐿 . Thus, it is only the 𝑗 − 1 ‘close’ challengers that the oracle √︁ needs to spend non-negligible budget on, which gives the coefficients 𝑐 𝑗 = (1 + 𝑗 − 1) 2 . Step 2: Verify Equation (2). Fix 𝜔 ∈ Δ𝐾 . For each 𝜆 ∈ D 𝐿 we upper bound the quantity Í ( 𝐿) 𝐴 𝐻𝑠𝑜 (𝜆) 𝐾 𝑘=1 𝜔 𝑘 KL(𝑥 𝑘 , 𝜆 𝑘 ) . We begin by considering the static oracle hardness terms 𝐻 𝑠𝑜 (𝜆 ) and 𝐻𝑠𝑜 (𝜆 𝐵, 𝑗 ) . To keep the main body of the paper focused, we state this as Lemma 2 and give its proof in
the Appendix. The main idea is to choose an explicit allocation proportion vector 𝛼 to get an upper bound ∗ (𝜆) −1 ≤ Γ(𝜆, 𝛼) −1 . Γ(𝜆, 𝛼) −1 , and then use 𝐻𝑠𝑜 (𝜆) = Γ𝑠𝑜
L EMMA 2. For the instances 𝜆 𝐴 and 𝜆 𝐵, 𝑗 defined in Step 1: 2 (a) 𝐻𝑠𝑜 (𝜆 𝐴) ≤ 1 + 𝑜 𝐿 (1) . 𝐿 (b) For each 𝑗 ∈ {3, . . . , 𝐾 }, √︁ 2(1 + 𝑗 − 1) 2 𝐵, 𝑗 𝐻𝑠𝑜 (𝜆 ) ≤ 1 + 𝑜 (1) . 𝐿 𝐿 2 𝑗+1
8
Next, we compute
( 𝐿) 𝐴 𝐵, 𝑗 . Since each alternative differs from 𝑘=1 𝜔 𝑘 KL(𝑥 𝑘 , 𝜆 𝑘 ) for 𝜆 = 𝜆 and for 𝜆 = 𝜆
Í𝐾
𝑥 ( 𝐿) at only a few indices, the sum collapses to a simple expression. For alternative 𝜆 𝐴, only arms 1 and 2 √ change, each by 𝐿 , hence 𝐾 ∑︁ 𝐿 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘𝐴) = (𝜔1 + 𝜔2 ) · . 2 𝑘=1 √ For alternative 𝜆 𝐵, 𝑗 , only arm 𝑗 changes from −𝐿 𝑗 to 𝐿 𝑗 𝐿 , hence √ 𝐾 ∑︁ (𝐿 𝑗 𝐿 + 𝐿 𝑗 ) 2 𝐿 2 𝑗+1 ( 𝐿) 𝐵, 𝑗 𝜔 𝑘 KL(𝑥 𝑘 , 𝜆 𝑘 ) = 𝜔 𝑗 · = 𝜔𝑗 · 1 + 𝑜 𝐿 (1) . 2 2 𝑘=1
Combining these with Lemma 2 gives 𝐾 ∑︁ 𝐻𝑠𝑜 (𝜆 𝐴) 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘𝐴) ≤ (1 + 𝑜 𝐿 (1)) (𝜔1 + 𝜔2 ), 𝑘=1
𝐻𝑠𝑜 (𝜆 𝐵, 𝑗 )
𝐾 ∑︁
𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘 ) ≤ (1 + 𝐵, 𝑗
√︁
𝑗 − 1) 2 (1 + 𝑜 𝐿 (1)) 𝜔 𝑗 ,
𝑗 ∈ {3, . . . , 𝐾 }.
𝑘=1
Defining 𝑐 𝑗 := (1 +
√︁
𝑗 − 1) 2 and taking the minimum over 𝜆 ∈ D 𝐿 yields (2).
Step 3: Apply Theorem 1 and conclude. Applying Theorem 1 with 𝜇 = 𝑥 ( 𝐿) , D (𝜇) = D 𝐿 , and 𝐻 = 𝐻𝑠𝑜 , and then using (2), gives ! −1 sup 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜆)
( ≤ sup min
𝜔 ∈Δ𝐾 𝜆∈ D 𝐿
𝜆∈ D 𝐿
𝐻𝑠𝑜 (𝜆)
𝐾 ∑︁
) 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘 )
𝑘=1
n o ≤ (1 + 𝑜 𝐿 (1)) sup min 𝜔1 + 𝜔2 , 𝑐 3 𝜔3 , . . . , 𝑐 𝐾 𝜔 𝐾 𝜔 ∈Δ𝐾 −1 𝐾
© ∑︁ −1 ª ≤ 1 + 𝑐 𝑗 ® + 𝑜 𝐿 (1). 𝑗=3 ¬ « The last inequality follows from Lemma A.1, which is proven in the Appendix. Since sup 𝜇∈Θ𝑢𝐾 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ sup𝜆∈ D𝐿 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜆) for every 𝐿 , letting 𝐿 → ∞ gives sup 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ 1 + 𝜇∈Θ𝑢𝐾
𝐾 ∑︁
1 1 > 1 + log(𝐾), √︁ 2 8 𝑗=3 (1 + 𝑗 − 1)
of which the second inequality is proven in Lemma A.2 of the Appendix. Since A ∈ Ccons (Θ) was arbitrary, taking inf A ∈ Ccons (Θ) gives the result.
4.
□
Extension to Natural Exponential Families
We now generalize the result of Theorem 2 to settings where rewards are drawn from any regular oneparameter NEF. D EFINITION 2 (R EGULAR ONE - PARAMETER NATURAL EXPONENTIAL FAMILY ). A family of distributions {𝜈 𝜃 : 𝜃 ∈ Θ} on R is a regular one-parameter NEF parameterized by its mean if there exist an open
9
interval H ⊂ R, a probability distribution 𝜈0 supported on X ⊆ R, and 𝐴 ∈ 𝐶 2 (H ) with 0 < 𝐴′′ (𝜂) < ∞ for all 𝜂 ∈ H such that, for every 𝜂 ∈ H , 𝑑𝜈 𝜂 (𝑥) = exp(𝜂𝑥 − 𝐴(𝜂)), 𝑥 ∈ X. 𝑑𝜈0 Define 𝜃 (𝜂) := E𝜈𝜂 [𝑋] = 𝐴′ (𝜂) , set Θ := 𝜃 (H ) , and write 𝜈 𝜃 := 𝜈 𝜂 ( 𝜃 ) where 𝜂(·) = 𝜃 −1 (·) . Throughout this section, assume {𝜈 𝜃 : 𝜃 ∈ Θ} is a family of distributions as in Definition 2, with Var𝜈 𝜃 (𝑋) ∈ (0, ∞) for all 𝜃 ∈ Θ. The key fact we use is that, on a sufficiently small neighborhood of any fixed 𝜃 0 ∈ Θ, the
KL divergence is locally quadratic. Lemma 3 formalizes this local approximation, which allows us to use a similar argument to that in the proof of Theorem 2 if we can construct instances that are sufficiently close together. L EMMA 3. Let {𝜈 𝜃 : 𝜃 ∈ Θ} be a regular one-parameter NEF parameterized by its mean, with Θ open. Fix 𝜃 0 ∈ Θ and let 𝑣 0 = Var𝜈 𝜃0 (𝑋) ∈ (0, ∞) . Then for every sequence 𝑟 𝐿 ↓ 0 there exists 𝛿 𝐿 → 0 such that, for all sufficiently large 𝐿 and all 𝜃, 𝜃 ′ ∈ (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ) , (𝜃 − 𝜃 ′ ) 2 (𝜃 − 𝜃 ′ ) 2 (1 − 𝛿 𝐿 ) ≤ KL(𝜃, 𝜃 ′ ) ≤ (1 + 𝛿 𝐿 ) . 2𝑣 0 2𝑣 0 T HEOREM 3. For 𝐾 ≥ 3 and reward distributions of a regular one-parameter NEF, 𝐾 ∑︁ 1 inf sup 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ 1 + . √︁ 2 A ∈ Ccons (Θ) 𝜇∈Θ𝐾 (1 + 𝑗 − 1) 𝑢 𝑗=3 Proof:
Fix arbitrary A ∈ Ccons (Θ) . The proof will use the arguments in the proof of Theorem 2, but
we first scale the instances so that all means are sufficiently close to a fixed 𝜃 0 ∈ Θ. The proof proceeds as follows. Step 1 chooses a sequence 𝜀 𝐿 ↓ 0 and defines a baseline 𝑥 ( 𝐿) together with a set of instances D 𝐿 ⊆ Alt(𝑥 ( 𝐿) ) ∩ Θ𝑢𝐾 by taking the same instances as in the Gaussian proof (centered at 𝜃 0 ) and multiplying
every deviation from 𝜃 0 by 𝜀 𝐿 . Step 2 then chooses a sequence 𝑟 𝐿 ↓ 0 and verifies that, for 𝐿 large, every component in 𝑥 ( 𝐿) and in D 𝐿 lies in (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ) , which ensures Lemma 3 applies to every KL term Í that will appear. Step 3 then uses Lemma 3 to replace the KL terms in the sums 𝑘 𝜔 𝑘 KL(𝑥 𝑘( 𝐿) , 𝜆 𝑘 ) , as well as in 𝐻𝑠𝑜 (𝜆) , with (𝜃 − 𝜃 ′ ) 2 /(2𝑣 0 ) . Combining these yields an inequality that upper bounds (1). Step 4 then shifts the instances by 𝜃 0 and rescales by 𝜀 𝐿 , so the instances align with those used in Theorem 2, allowing the analysis of Theorem 2 to be reused. Finally, Step 5 uses this together with Theorem 1 and lets 𝐿 → ∞ to obtain the stated lower bound. Step 1: Instance construction. Fix an integer 𝐿 ≥ 𝐾 and set 𝜀 𝐿 := 𝐿 − (𝐾+1) . Define the baseline 𝑥 ( 𝐿) ∈ R𝐾 and alternatives 𝜆 𝐴, (𝜆 𝐵, 𝑗 ) 𝐾𝑗=3 ∈ R𝐾 by 𝜃 , 0 ( 𝐿) 𝑥 𝑘 = 𝜃0 − 𝜀 𝐿 , 𝜃0 − 𝐿 𝑘 𝜀 𝐿 ,
𝑘 = 1, 𝑘 = 2, 3 ≤ 𝑘 ≤ 𝐾,
√ 𝜃0 − 𝐿 𝜀 𝐿 , √ 𝜆 𝑘𝐴 = 𝜃 0 − 𝜀 𝐿 + 𝐿 𝜀 𝐿 , 𝜃0 − 𝐿 𝑘 𝜀 𝐿 ,
𝑘 = 1, 𝑘 = 2, 3 ≤ 𝑘 ≤ 𝐾,
𝜃0, 𝜃0 − 𝜀 𝐿 , 𝐵, 𝑗 √ 𝜆𝑘 = 𝑗 𝐿𝜀 , 𝜃 + 𝐿 0 𝐿 𝜃0 − 𝐿 𝑘 𝜀 𝐿 ,
𝑘 = 1, 𝑘 = 2, 𝑘 = 𝑗, 𝑘 ≠ 𝑗.
10
All of these instances lie in Θ for sufficiently large 𝐿 , since the largest deviation from 𝜃 0 is at most √ 𝐿 𝐾 𝐿 𝜀 𝐿 = 𝐿 −1/2 . Thus for sufficiently large 𝐿 , D 𝐿 := {𝜆 𝐴 } ∪ {𝜆 𝐵,3 , . . . , 𝜆 𝐵,𝐾 } ⊆ Alt(𝑥 ( 𝐿) ) ∩ Θ𝑢𝐾 . Step 2: KL is “Gaussian-like” on our scale. Set 𝑟 𝐿 := 𝐿 −1/3 . By Lemma 3 there exists a sequence 𝛿 𝐿 → 0 such that for all 𝜃, 𝜃 ′ ∈ (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ) , (1 − 𝛿 𝐿 ) KL0 (𝜃, 𝜃 ′ ) ≤ KL(𝜃, 𝜃 ′ ) ≤ (1 + 𝛿 𝐿 ) KL0 (𝜃, 𝜃 ′ ),
where
KL0 (𝜃, 𝜃 ′ ) :=
(𝜃 − 𝜃 ′ ) 2 . 2𝑣 0
𝑟 𝐿 is chosen to decay slower than the instances do, so for sufficiently large 𝐿 , all components of 𝑥 ( 𝐿) and all
instances in D 𝐿 lie in (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ) . Step 3: Replace KL with KL0 . At this point, Step 2 ensures that Lemma 3 applies for all instances we consider. The goal of this step is to upper bound the quantity 𝐾 ∑︁ 𝐻𝑠𝑜 (𝜆) 𝜔 𝑘 KL 𝑥 𝑘( 𝐿) , 𝜆 𝑘 𝑘=1
by replacing the KL in it by KL0 . There are two places where KL enters: the KL sum and the static-oracle hardness 𝐻𝑠𝑜 (𝜆) . We handle them in turn and then combine the bounds. Define 𝐾 ∑︁ Γ0 (𝜇, 𝛼) := inf 𝛼 𝑘 KL0 (𝜆 𝑘 , 𝜇 𝑘 ), Γ0∗ (𝜇) := sup Γ0 (𝜇, 𝛼), 𝜆∈Alt( 𝜇)
𝐻0 (𝜇) :=
𝛼∈Δ0𝐾
𝑘=1
1 . Γ0∗ (𝜇)
(i) KL sums. Fix 𝜆 ∈ D 𝐿 and 𝜔 ∈ Δ𝐾 . Applying Lemma 3 coordinate-wise gives 𝐾 𝐾 ∑︁ ∑︁ 𝜔 𝑘 KL0 𝑥 𝑘( 𝐿) , 𝜆 𝑘 . 𝜔 𝑘 KL 𝑥 𝑘( 𝐿) , 𝜆 𝑘 ≤ (1 + 𝛿 𝐿 ) 𝑘=1
𝑘=1
(ii) Hardness terms. Fix 𝜆 ∈ D 𝐿 and 𝛼 ∈ Δ0𝐾 , and let 𝑏 = 𝑖 ∗ (𝜆) . As in the proof of Lemma 1, n o Γ(𝜆, 𝛼) = min inf 𝛼𝑏 KL(𝑚, 𝜆 𝑏 ) + 𝛼 𝑗 KL(𝑚, 𝜆 𝑗 ) , 𝑗≠𝑏 𝑚∈Θ
and the infimum is attained at some 𝑚 ∈ (𝜆 𝑗 , 𝜆 𝑏 ) . For 𝜆 ∈ D 𝐿 and 𝐿 large, (𝜆 𝑗 , 𝜆 𝑏 ) ⊂ (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ) , so Lemma 3 implies n o 𝛼𝑏 KL(𝑚, 𝜆 𝑏 ) + 𝛼 𝑗 KL(𝑚, 𝜆 𝑗 ) ≥ (1 − 𝛿 𝐿 ) 𝛼𝑏 KL0 (𝑚, 𝜆 𝑏 ) + 𝛼 𝑗 KL0 (𝑚, 𝜆 𝑗 ) . ∗ (𝜆) ≥ (1 − 𝛿 )Γ∗ (𝜆) , Taking inf 𝑚 and then min 𝑗≠𝑏 yields Γ(𝜆, 𝛼) ≥ (1 − 𝛿 𝐿 )Γ0 (𝜆, 𝛼) . Taking sup 𝛼 gives Γ𝑠𝑜 𝐿 0
i.e. 𝐻𝑠𝑜 (𝜆) ≤
1 𝐻0 (𝜆). 1 − 𝛿𝐿
Combining (i) and (ii), for all 𝜆 ∈ D 𝐿 and 𝜔 ∈ Δ𝐾 , 𝐾 𝐾 ∑︁ ∑︁ 1 + 𝛿𝐿 ( 𝐿) 𝐻𝑠𝑜 (𝜆) 𝜔 𝑘 KL 𝑥 𝑘 , 𝜆 𝑘 ≤ 𝐻0 (𝜆) 𝜔 𝑘 KL0 𝑥 𝑘( 𝐿) , 𝜆 𝑘 . 1 − 𝛿𝐿 𝑘=1 𝑘=1 Step 4: Transform to instances in Theorem 2. What remains is to control ( ) 𝐾 ∑︁ sup min 𝐻0 (𝜆) 𝜔 𝑘 KL0 𝑥 𝑘( 𝐿) , 𝜆 𝑘 . 𝜔 ∈Δ𝐾 𝜆∈ D 𝐿
𝑘=1
11
The point of this step is that, after shifting by 𝜃 0 and rescaling by 𝜀 𝐿 , this quantity becomes exactly the same Gaussian variance 1 expression that was analyzed in the proof of Theorem 2. Define the rescaled mean vectors 𝐵, 𝑗 𝜆 𝑘 − 𝜃0 𝑥 𝑘( 𝐿) − 𝜃 0 𝜆 𝑘𝐴 − 𝜃 0 𝐵, 𝑗 ( 𝐿) 𝐴 ˜ ˜ , 𝜆 𝑘 := , 𝜆 𝑘 := ( 𝑗 = 3, . . . , 𝐾), 𝑥˜ 𝑘 := 𝜀𝐿 𝜀𝐿 𝜀𝐿 and let D̃ 𝐿 := {𝜆˜ 𝐴 } ∪ {𝜆˜ 𝐵,3 , . . . , 𝜆˜ 𝐵,𝐾 }. By construction, 𝑥˜ ( 𝐿) and D̃ 𝐿 are the baseline and instance family
used in the proof of Theorem 2. (i) The KL0 sums rescale to Gaussian variance 1 KL. For any 𝜔 ∈ Δ𝐾 and any 𝜆 ∈ D 𝐿 , 2 𝐾 𝐾 𝐾 ∑︁ ( 𝑥˜ 𝑘( 𝐿) − 𝜆˜ 𝑘 ) 2 𝜀 𝐿 ( 𝑥˜ 𝑘( 𝐿) − 𝜆˜ 𝑘 ) 𝜀 2𝐿 ∑︁ ∑︁ ( 𝐿) 𝜔 𝑘 KL0 𝑥 𝑘 , 𝜆 𝑘 = 𝜔𝑘 = 𝜔𝑘 . 2𝑣 0 𝑣 0 𝑘=1 2 𝑘=1 𝑘=1 (ii) 𝐻0 rescales by the same factor. Shifting and scaling preserve Alt(·) , so for any 𝛼 ∈ Δ0𝐾 , Γ0 (𝜆, 𝛼) =
inf
𝐾 ∑︁
𝜈 ∈Alt(𝜆)
𝛼 𝑘 KL0 (𝜈 𝑘 , 𝜆 𝑘 ) =
𝑘=1
𝐾 ∑︁ 𝜀 2𝐿 ( 𝜈˜ 𝑘 − 𝜆˜ 𝑘 ) 2 inf 𝛼𝑘 . ˜ 𝑣 0 𝜈˜ ∈Alt( 𝜆) 2 𝑘=1
𝜀 2 𝐺,∗ 𝐺,∗ ˜ , where Γ𝑠𝑜 Therefore Γ0∗ (𝜆) = 𝑣𝐿0 Γ𝑠𝑜 (𝜆) is the Gaussian variance 1 static oracle decay rate, and hence
𝐻0 (𝜆) =
1 𝑣0 𝐺 ˜ = 2 𝐻𝑠𝑜 (𝜆), ∗ Γ0 (𝜆) 𝜀 𝐿
𝐺 corresponding to the Gaussian variance 1 static oracle hardness function. with 𝐻𝑠𝑜
Combining (i) and (ii), for any 𝜔 ∈ Δ𝐾 and 𝜆 ∈ D 𝐿 , 𝐻0 (𝜆)
𝐾 ∑︁
( 𝐿)
𝐾 ∑︁ ( 𝑥˜ 𝐺 ˜ 𝜔 𝑘 KL0 𝑥 𝑘( 𝐿) , 𝜆 𝑘 = 𝐻𝑠𝑜 (𝜆) 𝜔𝑘 𝑘
𝑘=1
𝑘=1
− 𝜆˜ 𝑘 ) 2 .
2
Thus the max–min expression over 𝜆 ∈ D 𝐿 under (𝐻0 , KL0 ) is identical to the Gaussian variance 1 max–min expression over 𝜆˜ ∈ D̃ 𝐿 with baseline 𝑥˜ ( 𝐿) . Applying the analysis from Theorem 2 we get −1 ) ( 𝐾 𝐾 ∑︁ ∑︁ 1 © ª sup min 𝐻0 (𝜆) 𝜔 𝑘 KL0 𝑥 𝑘( 𝐿) , 𝜆 𝑘 ≤ 1 + ® + 𝑜 𝐿 (1). √︁ 2 𝜔 ∈Δ𝐾 𝜆∈ D 𝐿 (1 + 𝑗 − 1) 𝑘=1 𝑗=3 « ¬ Step 5: Apply Theorem 1 and conclude. We now have the elements needed to complete the proof. ! −1 ( ) ∑︁ ( 𝐿) sup 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜆) ≤ sup min 𝐻𝑠𝑜 (𝜆) 𝜔 𝑘 KL(𝑥 𝑘 , 𝜆 𝑘 ) (Thm. 1) 𝜆∈ D 𝐿
𝜔 ∈Δ𝐾 𝜆∈ D 𝐿
𝑘
(
𝐾 ∑︁ 1 + 𝛿𝐿 ≤ sup min 𝐻0 (𝜆) 𝜔 𝑘 KL0 𝑥 𝑘( 𝐿) , 𝜆 𝑘 1 − 𝛿 𝐿 𝜔 ∈Δ𝐾 𝜆∈ D𝐿 𝑘=1
)
(Step 3)
−1 𝐾 1 + 𝛿 𝐿 ©© ∑︁ 1 ª ≤ 1 + ® √︁ 2 1 − 𝛿𝐿 (1 + 𝑗 − 1) 𝑗=3 ¬ ««
ª + 𝑜 𝐿 (1) ®®
−1
𝐾
1 © ∑︁ ª = 1 + ® √︁ 2 (1 + 𝑗 − 1) 𝑗=3 « ¬
+ 𝑜 𝐿 (1).
¬
(Step 4)
12
Since sup 𝜇∈Θ𝑢𝐾 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ sup𝜆∈ D𝐿 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜆) for every 𝐿 , letting 𝐿 → ∞ gives sup 𝑅 𝐻𝑠𝑜 ,∞ (A, 𝜇) ≥ 1 + 𝜇∈Θ𝑢𝐾
𝐾 ∑︁
1 . √︁ 2 𝑗=3 (1 + 𝑗 − 1)
Since A ∈ Ccons (Θ) was arbitrary, taking inf A ∈ Ccons (Θ) gives the result.
5.
□
Discussion
This paper establishes the fundamental result that fixed-budget BAI does not admit a complexity. This answers the question posed by Qin (2022) and Degenne (2023) of whether an analog to the fixed-confidence theory established by Garivier and Kaufmann (2016) can be extended to the fixed-budget setting. This result also has implications for the ranking-and-selection literature, where the static oracle is often used as a benchmark. We show that, for 𝐾 ≥ 3, the static oracle rate is unattainable as a uniform guarantee across all instances. In particular, for every consistent algorithm family A , there exists an instance 𝜇 such that lim inf 𝑇→∞
1 1 ≤ log 𝑇 𝑝 𝜇,𝑇 (A𝑇 )
1 1+
Í𝐾 𝑗=3
∗
1+
√︁
𝑗 −1
−2 Γ𝑠𝑜 (𝜇).
Since matching the static oracle uniformly is not possible, it is natural to aim for other theoretical guarantees. Minimax analysis provides strong guarantees, but the established algorithms that achieve the optimal error exponent are computationally intractable (Komiyama et al. 2022). Another direction recently explored is large-deviation admissibility: compare algorithms by their instance-dependent error exponents and determine whether one procedure uniformly dominates another. For two-armed Bernoulli rewards, Wang et al. (2024) show that uniform sampling is admissible even though a complexity does not exist. Imbens et al. (2025) construct an adaptive elimination algorithm that dominates uniform sampling when 𝐾 ≥ 3 with Gaussian equal-variance rewards. Constructing relevant classes of algorithms, such as elimination or static oracle-tracking algorithms, and determining which algorithms are admissible within these classes, is a promising direction for future research.
Acknowledgments I would like to thank Nils Rudi for his mentorship and helpful discussions throughout this project.
Appendix A:
Proofs
Proof of Lemma 1:
Let 𝜇 ∈ R𝐾 have unique best arm 𝑏 = 𝑖 ∗ (𝜇). Fix 𝜔 ∈ Δ0𝐾 and define 𝐹𝜔 (𝜉) :=
𝐾 ∑︁
𝐾 ∑︁ (𝜉 𝑘 − 𝜇 𝑘 ) 2 𝜔 𝑘 KL N (𝜉 𝑘 , 1) ∥ N (𝜇 𝑘 , 1) = 𝜔𝑘 . 2 𝑘=1 𝑘=1
By definition, Γ(𝜇, 𝜔) = inf 𝜉 ∈Alt( 𝜇) 𝐹𝜔 (𝜉). For each 𝑗 ≠ 𝑏 define Alt 𝑗 (𝜇) := {𝜉 ∈ R𝐾 : 𝜉 𝑗 ≥ 𝜉 𝑏 }. Alt(𝜇) = Ð 𝑗≠𝑏 Alt 𝑗 (𝜇), so inf
𝜉 ∈Alt( 𝜇)
𝐹𝜔 (𝜉) = min
inf
𝑗≠𝑏 𝜉 ∈Alt 𝑗 ( 𝜇)
𝐹𝜔 (𝜉).
13 Fix 𝑗 ≠ 𝑏. The constraint defining Alt 𝑗 (𝜇) only involves (𝜉 𝑏 , 𝜉 𝑗 ), and each term of 𝐹𝜔 is nonnegative and separable, so for any feasible (𝑢, 𝑣) with 𝑣 ≥ 𝑢 we may set 𝜉 𝑏 = 𝑢, 𝜉 𝑗 = 𝑣, and 𝜉 𝑘 = 𝜇 𝑘 for 𝑘 ∉ {𝑏, 𝑗 }. Thus ) ( (𝑣 − 𝜇 𝑗 ) 2 (𝑢 − 𝜇 𝑏 ) 2 . +𝜔𝑗 inf 𝐹𝜔 (𝜉) = inf 𝜔𝑏 𝜉 ∈Alt 𝑗 ( 𝜇) 2 2 (𝑢,𝑣) ∈R2 : 𝑣 ≥𝑢 The objective is strictly convex in (𝑢, 𝑣), and its unconstrained minimizer is (𝑢, 𝑣) = (𝜇 𝑏 , 𝜇 𝑗 ), which violates 𝑣 ≥ 𝑢 because 𝜇 𝑏 > 𝜇 𝑗 . Thus, the constrained minimizer lies on the boundary 𝑢 = 𝑣 =: 𝑥, and the problem reduces to ( ) (𝑥 − 𝜇 𝑗 ) 2 (𝑥 − 𝜇 𝑏 ) 2 inf 𝜔 𝑏 . +𝜔𝑗 𝑥 ∈R 2 2
(3)
Differentiating w.r.t. 𝑥 and setting to zero gives (𝜔 𝑏 + 𝜔 𝑗 )𝑥 = 𝜔 𝑏 𝜇 𝑏 + 𝜔 𝑗 𝜇 𝑗
=⇒
𝑥∗ =
𝜔𝑏 𝜇𝑏 + 𝜔 𝑗 𝜇 𝑗 , 𝜔𝑏 + 𝜔 𝑗
Plugging this into (3) gives inf
𝜉 ∈Alt 𝑗 ( 𝜇)
𝐹𝜔 (𝜉) =
𝜔 𝑏 𝜔 𝑗 (𝜇 𝑏 − 𝜇 𝑗 ) 2 · . 𝜔𝑏 + 𝜔 𝑗 2
Therefore, for every 𝜔 ∈ Δ0𝐾 , 𝜔 𝑏 𝜔 𝑗 (𝜇 𝑏 − 𝜇 𝑗 ) 2 · . 2 𝜔 ∈Δ0𝐾 𝑗≠𝑏 𝜔 𝑏 + 𝜔 𝑗
∗ Γ𝑠𝑜 (𝜇) = max min
Proof of Lemma 2:
□
∗ (𝜆) by choosing an allocation 𝛼 ∈ Δ0 and lower bounding We upper bound 𝐻𝑠𝑜 (𝜆) = 1/Γ𝑠𝑜 𝐾
∗ (𝜆) via Lemma 1. In particular, if 𝑏 = 𝑖 ∗ (𝜆), then for any 𝛼 ∈ Δ0 , Γ𝑠𝑜 𝐾 ∗ Γ𝑠𝑜 (𝜆) ≥ min 𝑖≠𝑏
𝛼𝑏 𝛼𝑖 (𝜆 𝑏 − 𝜆𝑖 ) 2 · . 𝛼𝑏 + 𝛼𝑖 2
(4)
(a) The instance 𝜆 𝐴. Here 𝑖 ∗ (𝜆 𝐴) = 𝑏 = 2. Consider the allocation 𝐿−𝐾 +2 1 𝛼1𝐴 = 𝛼2𝐴 = , 𝛼 𝑘𝐴 = (𝑘 = 3, . . . , 𝐾). 2𝐿 𝐿 We lower bound separately the 𝑖 = 1 term and the terms 𝑖 ∈ {3, . . . , 𝐾 } in (4). The overall minimum is at least the minimum of these lower bounds, so it suffices to show both are ≥ 𝐿2 (1 + 𝑜 𝐿 (1)). √ Arm 𝑖 = 1: 𝜆2𝐴 − 𝜆1𝐴 = 2 𝐿 − 1, therefore 𝐿−𝐾 +2 𝐿 √ 𝛼2𝐴𝛼1𝐴 (𝜆2𝐴 − 𝜆1𝐴) 2 𝐿 − 𝐾 + 2 1 −1 1 = 2𝐿 − 2 = 1 − 1 + 𝑜 (1) . + 𝑂 (𝐿 ) = · 𝐿 + √ 𝐿 2 2 4𝐿 2 2 𝛼2𝐴 + 𝛼1𝐴 𝐿 √ Arms 𝑖 ∈ {3, . . . , 𝐾 }: Here 𝜆 2𝐴 − 𝜆𝑖𝐴 = 𝐿 𝑖 + 𝐿 − 1, and 𝛼2𝐴𝛼𝑖𝐴 𝛼2𝐴 + 𝛼𝑖𝐴 Therefore,
=
(𝐿 − 𝐾 + 2)/(2𝐿) · (1/𝐿) 𝐿−𝐾 +2 = . (𝐿 − 𝐾 + 2)/(2𝐿) + 1/𝐿 𝐿 (𝐿 − 𝐾 + 4)
√ (𝜆 2𝐴 − 𝜆𝑖𝐴) 2 𝐿−𝐾 +2 (𝐿 𝑖 + 𝐿 − 1) 2 𝐿 · = · ≥ 1 + 𝑜 𝐿 (1) . 𝐴 𝐴 2 𝐿 (𝐿 − 𝐾 + 4) 2 2 𝛼2 + 𝛼𝑖 𝛼2𝐴𝛼𝑖𝐴
∗ (𝜆 𝐴) ≥ 𝐿 (1 + 𝑜 (1)), and Hence Γ𝑠𝑜 𝐿 2
𝐻𝑠𝑜 (𝜆 𝐴) =
1 2 ≤ 1 + 𝑜 𝐿 (1) . ∗ (𝜆 𝐴) 𝐿 Γ𝑠𝑜
(b) The instance 𝜆 𝐵, 𝑗 . Fix 𝑗 ∈ {3, . . . , 𝐾 } and write 𝜆 := 𝜆 𝐵, 𝑗 , so 𝑖 ∗ (𝜆) = 𝑏 = 𝑗. For 𝑖 < 𝑗 we have 𝜆 𝑖 ∈ {0, −1, −𝐿 3 , . . . , −𝐿 𝑗 −1 }, so √ √ 𝜆 𝑗 − 𝜆𝑖 = 𝐿 𝑗 𝐿 + 𝑂 (𝐿 𝑗 −1 ) = 𝐿 𝑗 𝐿 1 + 𝑜 𝐿 (1) ,
thus
(𝜆 𝑗 − 𝜆𝑖 ) 2 = 𝐿 2 𝑗+1 1 + 𝑜 𝐿 (1) ,
14 √ while for 𝑘 > 𝑗 we have 𝜆 𝑗 − 𝜆 𝑘 = 𝐿 𝑗 𝐿 + 𝐿 𝑘 ≥ 𝐿 𝑘 .
√ For large 𝐿 arms 1, . . . , 𝑗 − 1 are the only ‘close’ challengers (gap scales with 𝐿 𝑗 𝐿), so we choose 𝛼 to balance
arm 𝑗 against these 𝑗 − 1 arms. The arms 𝑘 > 𝑗 have much larger gaps, so we assign them only a vanishing mass, but distribute it proportional to (𝜆 𝑗 − 𝜆 𝑘 ) −2 so that the 𝑘 > 𝑗 terms do not end up controlling the minimum in (4). Let 𝜏𝐿 := 1{ 𝑗 < 𝐾 }/𝐿 and define 𝛼 ∈ Δ0𝐾 by 1 − 𝜏𝐿 √︁ √︁ , 𝑗 −1 1+ 𝑗 −1 1 − 𝜏𝐿 , √︁ 𝛼𝑘 = 1 + 𝑗 − 1 (𝜆 𝑗 − 𝜆 𝑘 ) −2 𝜏 , 𝐿 Í𝐾 −2 ℓ= 𝑗+1 (𝜆 𝑗 − 𝜆 ℓ )
1 ≤ 𝑘 ≤ 𝑗 − 1, 𝑘 = 𝑗, 𝑗 + 1 ≤ 𝑘 ≤ 𝐾.
We lower bound the minimum in (4) by treating 𝑖 < 𝑗 and (when 𝑗 < 𝐾) 𝑘 > 𝑗 separately. √︁ Arms 𝑖 < 𝑗: For 𝑖 < 𝑗, we have 𝛼𝑖 = 𝛼 𝑗 / 𝑗 − 1 and (𝜆 𝑗 − 𝜆𝑖 ) 2 = 𝐿 2 𝑗+1 (1 + 𝑜 𝐿 (1)) so 𝛼 𝑗 𝛼𝑖 (𝜆 𝑗 − 𝜆𝑖 ) 2 1 − 𝜏𝐿 𝐿 2 𝑗+1 · = 𝐿 2 𝑗+1 1 + 𝑜 𝐿 (1) = 1 + 𝑜 𝐿 (1) . √︁ √︁ 2 2 𝛼 𝑗 + 𝛼𝑖 2 2(1 + 𝑗 − 1) 2(1 + 𝑗 − 1) Arms 𝑘 > 𝑗 (when 𝑗 < 𝐾): Here 𝛼 𝑘 ≤ 𝜏𝐿 = 1/𝐿 while 𝛼 𝑗 ≥
√1 2(1+
𝑗 −1)
for all 𝐿 ≥ 2, so for 𝐿 large 𝛼 𝑘 ≤ 𝛼 𝑗 and thus
𝛼 𝑗 /(𝛼 𝑗 + 𝛼 𝑘 ) ≥ 1/2. So 𝛼 𝑘 (𝜆 𝑗 − 𝜆 𝑘 ) 2 𝛼 𝑗 𝛼 𝑘 (𝜆 𝑗 − 𝜆 𝑘 ) 2 ≥ . · 𝛼 𝑗 + 𝛼𝑘 2 4 By the definition of 𝛼 𝑘 , 𝛼 𝑘 (𝜆 𝑗 − 𝜆 𝑘 ) 2 =
𝜏𝐿 , 𝑆
𝑆 :=
𝐾 ∑︁
(𝜆 𝑗 − 𝜆ℓ ) −2 .
ℓ= 𝑗+1
Using 𝜆 𝑗 − 𝜆ℓ
≥ 𝐿 ℓ for ℓ > 𝑗 gives 𝑆≤
∞ ∑︁
𝐿 −2ℓ =
ℓ= 𝑗+1
𝐿 −2( 𝑗+1) 4 −2 𝑗 −2 ≤ 𝐿 , 3 1 − 𝐿 −2
thus 𝛼 𝑗 𝛼 𝑘 (𝜆 𝑗 − 𝜆 𝑘 ) 2 1 1/𝐿 3 = 𝐿 2 𝑗+1 . · ≥ · 𝛼 𝑗 + 𝛼𝑘 2 4 (4/3)𝐿 −2 𝑗 −2 16 3 Since 16 >
√1 2(1+
𝑗 −1) 2
for every 𝑗 ≥ 3, the 𝑘 > 𝑗 terms are strictly larger than the 𝑖 < 𝑗 terms for 𝐿 large. Therefore the
minimum in (4) is attained among 𝑖 < 𝑗, and we conclude ∗ Γ𝑠𝑜 (𝜆) ≥
Proof of Lemma 3:
𝐿 2 𝑗+1 1 + 𝑜 𝐿 (1) , √︁ 2(1 + 𝑗 − 1) 2
𝐻𝑠𝑜 (𝜆
𝐵, 𝑗
√︁ 2(1 + 𝑗 − 1) 2 ) ≤ 1 + 𝑜 𝐿 (1) . 2 𝑗+1 𝐿
□
Because the family is regular, there exists an open interval H ⊂ R and a 𝐶 2 strictly convex
log-partition function 𝐴 : H → R such that for 𝜂 ∈ H , 𝑑𝜈 𝜂 (𝑥) = exp(𝜂𝑥 − 𝐴(𝜂)), KL(𝜈 𝜂 ∥𝜈 𝜂 ′ ) = 𝐴(𝜂 ′ ) − 𝐴(𝜂) − 𝐴′ (𝜂) (𝜂 ′ − 𝜂). 𝑑𝜈0 In this parameterization, 𝜃 (𝜂) := E𝜈𝜂 [𝑋] = 𝐴′ (𝜂),
Var𝜈𝜂 (𝑋) = 𝐴′′ (𝜂).
Since 𝐴′′ > 0, the map 𝜂 ↦→ 𝜃 (𝜂) is strictly increasing and thus invertible; write 𝜂(𝜃) for its inverse. Let 𝜂0 := 𝜂(𝜃 0 ), so 𝑣 0 = 𝐴′′ (𝜂0 ).
15 Fix 𝜃, 𝜃 ′ ∈ Θ and let 𝜂 := 𝜂(𝜃) and 𝜂 ′ := 𝜂(𝜃 ′ ). By Taylor’s theorem applied to 𝐴 at 𝜂, there exists 𝑐 between 𝜂 and 𝜂 ′ such that 1 ′′ 𝐴 (𝑐) (𝜂 ′ − 𝜂) 2 . 2 By the mean value theorem applied to 𝐴′ there exists 𝑑 ∈ (𝜂, 𝜂 ′ ) such that KL(𝜈 𝜂 ∥𝜈 𝜂 ′ ) =
(5)
𝜃 ′ − 𝜃 = 𝐴′ (𝜂 ′ ) − 𝐴′ (𝜂) = 𝐴′′ (𝑑) (𝜂 ′ − 𝜂).
(6)
Combining (5) and (6) gives 1 𝐴′′ (𝑐) (𝜃 − 𝜃 ′ ) 2 . 2 𝐴′′ (𝑑) 2 Let 𝑟 𝐿 ↓ 0. By continuity of 𝜂(·) at 𝜃 0 , 𝑠 𝐿 := sup{|𝜂(𝜃) − 𝜂0 | : |𝜃 − 𝜃 0 | ≤ 𝑟 𝐿 } → 0. Define KL(𝜃, 𝜃 ′ ) =
𝑚 𝐿 := inf{ 𝐴′′ (𝑢) : |𝑢 − 𝜂0 | ≤ 𝑠 𝐿 },
(7)
𝑀 𝐿 := sup{ 𝐴′′ (𝑢) : |𝑢 − 𝜂0 | ≤ 𝑠 𝐿 }.
Then 𝑚 𝐿 → 𝑣 0 , 𝑀 𝐿 → 𝑣 0 , and 𝑚 𝐿 > 0 for 𝐿 large. For any 𝜃, 𝜃 ′ ∈ (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ), we have 𝜂, 𝜂 ′ ∈ [𝜂0 − 𝑠 𝐿 , 𝜂0 + 𝑠 𝐿 ], and 𝑐, 𝑑 ∈ [𝜂0 − 𝑠 𝐿 , 𝜂0 + 𝑠 𝐿 ], therefore 𝑚 𝐿 ≤ 𝐴′′ (𝑐) ≤ 𝑀 𝐿 ,
𝑚 𝐿 ≤ 𝐴′′ (𝑑) ≤ 𝑀 𝐿 .
Thus 𝑚𝐿 𝐴′′ (𝑐) 𝑀𝐿 ≤ ≤ 2. 2 ′′ 2 𝐴 (𝑑) 𝑀𝐿 𝑚𝐿 ( ) 𝑣 0 𝑀𝐿 𝑣0𝑚 𝐿 𝛿 𝐿 := max −1 , −1 . 𝑀 𝐿2 𝑚 2𝐿
Let
Then 𝛿 𝐿 ↓ 0 and, for 𝐿 large, 1 − 𝛿𝐿 𝐴′′ (𝑐) 1 + 𝛿𝐿 ≤ ′′ 2 ≤ . 𝑣0 𝑣0 𝐴 (𝑑) Plugging this into (7) gives, for all 𝜃, 𝜃 ′ ∈ (𝜃 0 − 𝑟 𝐿 , 𝜃 0 + 𝑟 𝐿 ), (𝜃 − 𝜃 ′ ) 2 (𝜃 − 𝜃 ′ ) 2 (1 − 𝛿 𝐿 ) ≤ KL(𝜃, 𝜃 ′ ) ≤ (1 + 𝛿 𝐿 ) . 2𝑣 0 2𝑣 0 A.1. Auxiliary Lemmas
□
L EMMA A.1. Let 𝐾 ≥ 3 and let 𝑐 3 , . . . , 𝑐 𝐾 > 0. Then −1 𝐾
© ∑︁ 1 ª sup min 𝜔1 + 𝜔2 , 𝑐 3 𝜔3 , . . . , 𝑐 𝐾 𝜔 𝐾 = 1 + ® . 𝑐 𝜔 ∈Δ𝐾 𝑗=3 𝑗 ¬ « Let 𝑡 := min{𝜔1 + 𝜔2 , 𝑐 3 𝜔3 , . . . , 𝑐 𝐾 𝜔 𝐾 }. Then 𝜔1 + 𝜔2 ≥ 𝑡 and 𝜔 𝑗 ≥ 𝑡/𝑐 𝑗 for all 𝑗 ≥ 3, so n
Proof:
o
𝐾 ∑︁
𝐾 ∑︁ 𝑡
𝐾
© ∑︁ 1 ª = 𝑡 1 + ®. 𝑐 𝑐 𝑘=1 𝑗=3 𝑗 𝑗=3 𝑗 ¬ « Í −1 Í −1 Thus 𝑡 ≤ 1 + 𝐾𝑗=3 𝑐1𝑗 . Equality is reached at 𝑡 ∗ := 1 + 𝐾𝑗=3 𝑐1𝑗 , choosing 𝜔 𝑗 = 𝑡 ∗ /𝑐 𝑗 for 𝑗 ≥ 3, and 𝜔1 + 𝜔2 = 1=
𝑡∗.
𝜔𝑘 ≥ 𝑡 +
□ L EMMA A.2. For every integer 𝐾 ≥ 3, 𝐾 ∑︁
1 1 > log 𝐾. √︁ 2 8 𝑗=3 (1 + 𝑗 − 1)
Proof:
log(3)
For 𝐾 = 3, 16 > 8 . Now assume 𝐾 ≥ 4. ∫ 𝐾 𝐾 𝐾 ∑︁ ∑︁ 1 1 1 𝐾1 1 1 > > 𝑑𝑥 = log ≥ log 𝐾. √︁ 2 4( 𝑗 − 1) 4 2 𝑥 4 2 8 𝑗=3 (1 + 𝑗 − 1) 𝑗=3
□
16
References Audibert JY, Bubeck S, Munos R (2010) Best arm identification in multi-armed bandits. Proceedings of the Conference On Learning Theory. Avci H, Nelson B, Wächter A (2021) Getting to “rate-optimal” in ranking & selection. Proceedings of the 2021 Winter Simulation Conference. Carpentier A, Locatelli A (2016) Tight (lower) bounds for the fixed budget best arm identification bandit problem. Proceedings of the Conference on Learning Theory. Chen Y, Ryzhov I (2019) Complete expected improvement converges to an optimal budget allocation. Advances in Applied Probability 51(1):209–235. Chen Y, Ryzhov I (2023) Balancing optimal large deviations in sequential selection. Management Science 69(6):3457– 3473. Degenne R (2023) On the existence of a complexity in fixed budget bandit identification. Proceedings of the 36th Annual Conference on Learning Theory. Garivier A, Kaufmann E (2016) Optimal best arm identification with fixed confidence. Proceedings of the 29th Annual Conference on Learning Theory. Garivier A, Ménard P, Stoltz G (2019) Explore first, exploit next: The true shape of regret in bandit problems. Mathematics of Operations Research 44(2):377–399. Glynn P, Juneja S (2004) A large deviations perspective on ordinal optimization. Proceedings of the 2004 Winter Simulation Conference. Glynn P, Juneja S (2011) Ordinal optimization: A nonparametric framework. Proceedings of the 2011 Winter Simulation Conference. Imbens G, Qin C, Wager S (2025) Admissibility of completely randomized trials: A large-deviation approach. ArXiv preprint arXiv:2506.05329. Karnin Z, Koren T, Somekh O (2013) Almost optimal exploration in multi-armed bandits. Proceedings of the 30th International Conference on Machine Learning. Kaufmann E, Cappé O, Garivier A (2016) On the complexity of best-arm identification in multi-armed bandit models. JMLR 17(1):1–42. Komiyama J, Tsuchiya T, Honda J (2022) Minimax optimal algorithms for fixed-budget best arm identification. Proceedings of the 36th Conference on Neural Information Processing Systems. Neyman J (1934) On the two different aspects of the representative method: The method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society 97(4):558–625. Qin C (2022) Open problem: Optimal best arm identification with fixed budget. Proceedings of the 35th Annual Conference on Learning Theory.
17 Shin D, Broadie M, Zeevi A (2018) Tractable sampling strategies for ordinal optimization. Operations Research 66(6):1693–1712. Wang PA, Ariu K, Proutiere A (2024) On universally optimal algorithms for A/B testing. Proceedings of the 41st International Conference on Machine Learning. Wang PA, Tzeng RC, Proutiere A (2023) Best arm identification with fixed budget: A large deviation perspective. Proceedings of the 37th Conference on Neural Information Processing Systems. Wu D, Zhou E (2018) Analyzing and provably improving fixed budget ranking and selection algorithms. ArXiv preprint arXiv:1811.12183.