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

CREATORKapilan Balagopalan, Yinan Li, Yao Zhao, Tuan Nguyen, Anton Daitche, Houssam Nassif, Kwang-Sung Jun
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-03972

Browse the full library · About the Tower of Babel