Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors

The best-arm identification (BAI) problem is one of the most fundamental problems in interactive machine learning, which has two flavors: the fixed-budget setting (FB) and the fixed-confidence setting (FC). For $K$-armed bandits with a unique best arm, the optimal sample complexities for both settings have been settled down and they match up to logarithmic factors. This prompts an interesting research question about the generic, potentially structured BAI problems: is FB harder than FC or the other way around? In this paper, we show that FB is no harder than FC up to logarithmic factors. We do this constructively: we propose a novel algorithm called FC2FB (fixed confidence to fixed budget), which is a meta algorithm that takes in an FC algorithm $\mathcal{A}$ and turn it into an FB algorithm. We prove that FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of $\mathcal{A}$. This means that the optimal FC sample complexity is an upper bound of the optimal FB sample complexity up to logarithmic factors. Our result not only reveals a fundamental relationship between FB and FC, but also has a significant implication: FC2FB combined with existing state-of-the-art FC algorithms, leads to improved sample complexity for a number of FB problems.

When a system needs to repeatedly make decisions, like a recommendation engine choosing which ad to show, a doctor selecting a treatment, or a website personalizing content, it must try different options to learn which one works best on average. This is called the "best-arm identification" problem in the bandit setting: you pull the arms of a slot machine (i.e., collect reward samples from different options) and try to estimate which arm gives the highest average reward. Researchers have studied two practical versions of this problem. In the fixed-confidence setting, you are given an error tolerance and must identify the best option while using as few trials (samples) as possible. In the fixed-budget setting, you are given a fixed number of trials and must minimize the chance of picking the wrong option. Both settings care about "sample efficiency", that is, how many trials you need to achieve a certain level of accuracy, and comparing them is an important research question. A long-standing open question in the field was: Is the fixed-budget problem fundamentally harder than the fixed-confidence problem? This paper answers that question with a clear no: by proving that whenever there exists an efficient algorithm for FC, there exists an algorithm for FB that is almost equally efficient. This is captured in our title: "Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors." We achieve this through a general-purpose meta-framework called FC2FB, which takes any fixed-confidence algorithm as a black box and automatically converts it into a fixed-budget algorithm. Because FC2FB treats the underlying algorithm as a black box, this result is broadly applicable across many bandit domains, including multi-arm bandits, linear bandits, unimodal bandits, cascading bandits, and more. Our contribution is therefore twofold: (1) we resolve a fundamental theoretical question, "Is the fixed-budget problem fundamentally harder than the fixed-confidence problem?" by proving that whenever there exists an efficient algorithm for FC, there exists an algorithm for FB that is almost equally efficient, and (2) we provide a practical, domain-agnostic tool that practitioners can use to apply well-studied fixed-confidence algorithms to fixed-budget settings where good algorithms were previously unavailable.