# Fixed-Confidence Guarantees for Bayesian Best-Arm Identification

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2019.

## Built on by (most cited first, 30 of 38)

- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Sampling](https://mlsanity.com/paper/2109.08229/) (2021)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [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)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022)
- [Best Arm Identification with Fairness Constraints on Subpopulations](https://mlsanity.com/paper/2304.04091/) (2023)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence](https://mlsanity.com/paper/2309.02202/) (2023)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap](https://mlsanity.com/paper/2201.04469/) (2022)
- [Thompson Sampling for (Combinatorial) Pure Exploration](https://mlsanity.com/paper/2206.09150/) (2022)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [Thompson Exploration with Best Challenger Rule in Best Arm Identification](https://mlsanity.com/paper/2310.00539/) (2023)
- [SPRT-based Efficient Best Arm Identification in Stochastic Bandits](https://mlsanity.com/paper/2207.11158/) (2022)
- [Best Arm Identification with Contextual Information under a Small Gap](https://mlsanity.com/paper/2209.07330/) (2022)
- [Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Bounds](https://mlsanity.com/paper/2302.02988/) (2023)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budget](https://mlsanity.com/paper/2310.19788/) (2023)
- [Active Sampling of Multiple Sources for Sequential Estimation](https://mlsanity.com/paper/2208.05406/) (2022)
- [Best Arm Identification in Stochastic Bandits: Beyond β-optimality](https://mlsanity.com/paper/2301.03785/) (2023)
- [Adaptive Experimentation at Scale: A Computational Framework for Flexible Batches](https://mlsanity.com/paper/2303.11582/) (2023)
- [Adaptive Experimental Design for Policy Learning](https://mlsanity.com/paper/2401.03756/) (2024)
- [Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identification](https://mlsanity.com/paper/2411.01808/) (2024)
- [Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification](https://mlsanity.com/paper/2202.05193/) (2022)
- [Best Arm Identification in Batched Multi-armed Bandit Problems](https://mlsanity.com/paper/2312.13875/) (2023)
- [UCB Exploration for Fixed-Budget Bayesian Best Arm Identification](https://mlsanity.com/paper/2408.04869/) (2024)

## Abstract (arXiv)

We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.