# Fixed Confidence Best Arm Identification in the Bayesian Setting

arXiv: https://arxiv.org/abs/2402.10429 · HTML: https://mlsanity.com/paper/2402.10429/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 16 Feb 2024.

## Builds on (most cited first, 18 of 18)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Non-stochastic Best Arm Identification and Hyperparameter Optimization](https://mlsanity.com/paper/1502.07943/) (2015)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [On the Complexity of A/B Testing](https://mlsanity.com/paper/1405.3224/) (2014)
- [Rate-optimal Bayesian Simple Regret in Best Arm Identification](https://mlsanity.com/paper/2111.09885/) (2021)
- [Non-Asymptotic Analysis of a UCB-based Top Two Algorithm](https://mlsanity.com/paper/2210.05431/) (2022)
- [A Bad Arm Existence Checking Problem](https://mlsanity.com/paper/1901.11200/) (2019)
- [An varepsilon-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond](https://mlsanity.com/paper/2305.16041/) (2023)
- [Thresholding Bandit Problem with Both Duels and Pulls](https://mlsanity.com/paper/1910.06368/) (2019)

## Abstract (arXiv)

We consider the fixed-confidence best arm identification (FC-BAI) problem in the Bayesian setting. This problem aims to find the arm of the largest mean with a fixed confidence level when the bandit model has been sampled from the known prior. Most studies on the FC-BAI problem have been conducted in the frequentist setting, where the bandit model is predetermined before the game starts. We show that the traditional FC-BAI algorithms studied in the frequentist setting, such as track-and-stop and top-two algorithms, result in arbitrarily suboptimal performances in the Bayesian setting. We also obtain a lower bound of the expected number of samples in the Bayesian setting and introduce a variant of successive elimination that has a matching performance with the lower bound up to a logarithmic factor. Simulations verify the theoretical results.