![[2602.03972] Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.03972] Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors
Summary
This paper explores the relationship between fixed-budget and fixed-confidence settings in best-arm identification, demonstrating that they are equivalent up to logarithmic factors through a novel algorithm.
Why It Matters
Understanding the equivalence between fixed-budget and fixed-confidence settings in best-arm identification can significantly enhance algorithm efficiency in interactive machine learning, impacting various applications in AI and decision-making processes.
Key Takeaways
- Fixed-budget and fixed-confidence settings in best-arm identification are equivalent up to logarithmic factors.
- The proposed FC2FB algorithm transforms fixed-confidence algorithms into fixed-budget algorithms.
- The findings improve sample complexity for a range of fixed-budget problems.
- This research contributes to the theoretical understanding of interactive machine learning.
- The results suggest potential enhancements for existing algorithms in practical applications.
Statistics > Machine Learning arXiv:2602.03972 (stat) [Submitted on 3 Feb 2026 (v1), last revised 18 Feb 2026 (this version, v2)] Title:Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors Authors:Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun View a PDF of the paper titled Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors, by Kapilan Balagopalan and 6 other authors View PDF Abstract: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 the 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 this FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of $\mathcal{A}$. This means...
