Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors
Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun · 2026
Read Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factors by Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-03972.txt.
Description
Finding the best option by testing is a classic problem with two flavors. Kapilan Balagopalan and 6 co-authors connect them in a 2026 paper on best-arm identification. In the fixed-confidence version, testing stops once the answer is sure enough. In the fixed-budget version, tests are capped in advance.
Their meta-algorithm, FC2FB, converts any fixed-confidence method into a fixed-budget one. The converted method needs about as many samples as the original, up to logarithmic factors. So the fixed-budget problem is provably no harder. The result settles a structural question for bandit theory and gives algorithm designers a free transfer tool.
Catalog record
| CREATOR | Kapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-03972