Source-linked AI summary
Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
Alexandra Carpentier, Andrea Locatelli
TL;DR
The paper studies fixed-budget best arm identification and asks how small the error probability can be when the problem complexity H is not tightly known. It develops lower bounds for this setting and shows that the unavoidable error can scale as exp(-T/(log(K)H)), establishing a complexity-adaptation price and optimality of Successive Rejection strategies. The result closes the stated upper–lower bound gap, subject to the paper’s scope and assumptions.
Problem
Fixed-budget best arm identification lacked a matching understanding of error bounds, especially when the learner does not have tight knowledge of H.
Method
The paper proves lower bounds for adaptive K-armed stochastic bandit strategies under a fixed horizon and complexity H.
Results
The paper establishes a lower bound of order exp(-T/(log(K)H)) for some problem and proves that Successive Rejection strategies are optimal.
Takeaways & Limitations
Unlike fixed-confidence identification, fixed-budget adaptation to unknown H incurs a log(K) price.
Takeaways & Limitations
The paper notes that its construction does not show a log(K) adaptation price is unavoidable for all easier problems, leaving effective adaptation to those problems open.
Abstract
from arXiv · showhide
We consider the problem of \textit{best arm identification} with a \textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with arms distribution defined on $[0,1]$. We prove that any bandit strategy, for at least one bandit problem characterized by a complexity $H$, will misidentify the best arm with probability lower bounded by $$\exp\Big(-\frac{T}{\log(K)H}\Big),$$ where $H$ is the sum for all sub-optimal arms of the inverse of the squared gaps. Our result disproves formally the general belief - coming from results in the fixed confidence setting - that there must exist an algorithm for this problem whose probability of error is upper bounded by $\exp(-T/H)$. This also proves that some existing strategies based on the Successive Rejection of the arms are optimal - closing therefore the current gap between upper and lower bounds for the fixed budget best arm identification problem.
1. Introduction
The paper studies fixed-budget best arm identification and addresses a major gap between known upper and lower error bounds. It proves that adaptation to unknown complexity H incurs a log(K) factor and establishes optimality for Successive Rejection strategies.
- Problem: The problem is to identify the highest-mean arm among K stochastic arms using T adaptively collected samples.Arms have distributions supported on [0,1].
- Motivation: The fixed-budget setting remained separated by a major gap between upper and lower bounds despite extensive study.The gap concerns the probability of failing to identify an optimal arm.
- Contribution: The paper improves the lower bound and proves Audibert and Bubeck’s strategies optimal whether or not an upper bound on H is known.The claim applies uniformly in the relevant settings.
- Main result: The unexpected lower bound has order exp(-T/(log(K)H)), contradicting the conjectured exp(-T/H) dependence in the absence of complexity knowledge.The additional log(K) factor is described as an adaptation price.
- Proof approach: The paper uses lower-bound proofs based on a class of problems with different complexities.The authors characterize the proofs as simple and short.
2. Setting
The setting is a K-armed stochastic bandit with a fixed horizon T, where an adaptive learner sequentially samples arms and finally recommends one. Success is identifying an arm with the highest mean, and complexity is characterized by gap-based quantities H and H2.
- Learning setting: Each of K arms has a distribution on [0,1] with mean μk, and the learner makes T sequential adaptive arm choices.At each time, the learner receives a noisy reward from the chosen arm.
- Learning setting: At the end of the horizon, the learner returns one arm as its recommendation.The recommendation is denoted k̂T in the setting.
- Objective: Best arm identification means finding an arm with the highest mean within T iterations.The set of optimal arms contains all arms attaining the highest mean.
- Objective: The expected loss is the probability of not identifying an optimal arm, which the learner seeks to minimize.This is the fixed-budget best arm identification objective.
- Complexity: The problem-dependent complexities H and H2 are defined from ordered arm means and satisfy H2 ≤ H ≤ log(2K)H2 ≤ 2 log(K)H2.These quantities characterize the difficulty of bandit problems.
3. Literature review
The literature distinguishes fixed-confidence identification from fixed-budget identification, with the latter retaining an important upper–lower bound gap when H is not known tightly. The paper positions this gap as more consequential than its logarithmic appearance suggests.
- Two settings: Fixed-confidence identification targets error probability δ while minimizing samples, whereas fixed-budget identification minimizes error probability under T pulls.The two settings are described as stopping-time and resource-allocation problems, respectively.
- Fixed-confidence literature: Fixed-confidence results established the importance of H and became tight in multiplicative H terms, though logarithmic terms remained imperfect.Several later works refined these second-order terms.
- Fixed-budget literature: Before this paper, fixed-budget results still had an important gap between the best known upper and lower bounds.Audibert and Bubeck provided the best known upper bounds, while Kaufmann et al. provided the best known lower bound.
- Open gap: The fixed-budget gap includes a log(K) factor when the learner lacks a tight upper bound on H.The factor affects the exponent and remains relevant for small δ.
- Related problems: Related TopK and pure-exploration results apply to best arm identification but do not improve the cited fixed-budget bounds.Best arm identification is a special case of those broader settings.
4. Main results
The paper establishes lower bounds showing that fixed-budget best-arm identification can require a log(K) adaptation price, and proves that Successive Reject is optimal in this setting. The results remain valid even under a technically easier finite-family problem formulation known to the learner.
- Theorem 1 gives lower bounds for any strategy over bandit problems whose complexity H is bounded by a.The theorem has separate statements depending on whether the learner knows an upper bound a on H.
- For sufficiently large T, a, and K, some problem forces error probability at least an exponential bound involving log(K)H.The paper states this for T larger order than a^2 log(K), a larger order than K^2, and K greater than 2.
- The lower bound contradicts the conjectured fixed-budget rate exp(-T/H) and instead identifies a log(K) adaptation price when H is unknown.The paper contrasts this with fixed-confidence results, where adaptation to H does not require knowing H.
- The Successive Reject strategy is optimal because its error upper bound matches the paper’s lower-bound order.The comparison concerns problems with many sub-optimal arms close to the optimal arm, for which H2 is of the same order as H.
- The stronger theorem shows that the lower bound persists even when the learner knows it faces one of K fully described bandit settings.The proof constructs settings by flipping each arm around the second-best arm and argues that some arm is under-sampled relative to the optimal allocation.
- The technical construction uses Bernoulli product distributions in which bandit problem i differs by replacing arm i with its reflected distribution, making arm i uniquely optimal.The family uses p1 = 1/2, pk in [1/4, 1/2), νk = B(pk), and ν′k = B(1 − pk).
5. Proof of the theorems
The proof constructs concentrated change-of-measure events and applies them across bandit instances to establish the theorem's lower bounds. It concludes both parts by identifying instances on which the algorithm must incur substantial error.
- Proof strategy: The proof begins by defining a high-probability event on which empirical KL divergences concentrate uniformly over arms and sampling times.The bounded i.i.d. KL increments enable Hoeffding's inequality, and a union bound yields probability at least 5/6 for the concentration event.
- Proof strategy: The change-of-measure step relates probabilities under bandit instances that differ in one arm, using the stochastic sample counts generated by the fixed-budget strategy.The strategy samples exactly T times, while the compared product distributions differ only in the selected arm.
- First lower bound: For any reasonable algorithm, the constructed event has probability at least 1/6 under the reference problem, forcing a nontrivial probability of selecting a non-optimal arm on another instance.If the algorithm already errs on the reference problem with probability at least 1/2, the desired lower-bound conclusion is immediate.
- First lower bound: The first theorem part follows by combining the event lower bound with the change-of-measure inequality and the identity H(1) = max_i H(i).The proof uses contraposition to identify an instance for which the algorithm's error probability satisfies the claimed lower bound.
- Second lower bound: The second theorem part is obtained by the analogous construction and concludes with the corresponding lower bound for the broader problem class.The proof explicitly states that the second part follows after applying the same argument to the selected instance.
6. An α−parametrization
The α-parametrization creates a family of bandit problems with varying complexities. For α > 1/2, it spans instances where the adaptation quantity grows at least logarithmically with K, whereas for α < 1/2 the construction does not establish such a price.
- Complexity range: The parametrization defines problems indexed by α whose complexities satisfy H(1) ≥ H(i) ≥ H(K), with the easiest problem having complexity of order K.The hardest problem's complexity depends on α and is treated separately.
- α < 1/2: For α < 1/2, the easiest and hardest problems have complexities of the same order up to a constant.Both endpoints of the restricted class therefore scale similarly in this regime.
- α > 1/2: For α > 1/2, H(1) is of order H(K)^(2α), spanning problems with varying complexities, and h* is at least of order log(K).This regime supplies the logarithmic adaptation behavior used in the construction.
- Open boundary: For α < 1/2, the ratio governing the construction is upper bounded by a constant because both terms are of order K.Consequently, this construction does not show that a log(K) adaptation price is unavoidable in every case, leaving effective adaptation for easier problems open.
Conclusion
The paper establishes a lower bound for fixed-budget best arm identification when the complexity H is not tightly known, formally rejecting the conjectured exp(-T/H) error rate. It identifies an adaptation price and supports optimality of the relevant Successive Rejection strategies.
- Main result: For problems of complexity H without a sufficiently tight upper bound, every bandit strategy makes an error on some problem with probability at least the paper's lower bound.The theorem is stated for a problem G with complexity H(G).
- Main result: The result formally disproves the belief that an algorithm can achieve error at most exp(-T/H) for every fixed-budget problem of complexity H.The conjecture is contrasted with the lower bound established by the paper.
- Implication: Unlike the fixed-confidence setting, fixed-budget identification incurs a price for adaptation to the unknown problem complexity H.The paper connects this adaptation-price phenomenon to analogous effects in other model-selection problems.
- Acknowledgment: The work is supported by the DFG's Emmy Noether grant MuSyAD (CA 1488/1-1).This funding statement is included in the conclusion materials.