# Simple Bayesian Algorithms for Best Arm Identification

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

## Key facts

- Cited by 117 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2016.

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

- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Online Multi-Armed Bandits with Adaptive Inference](https://mlsanity.com/paper/2102.13202/) (2021)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Almost Optimal Variance-Constrained Best Arm Identification](https://mlsanity.com/paper/2201.10142/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [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)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [Bayesian Fixed-Budget Best-Arm Identification](https://mlsanity.com/paper/2211.08572/) (2022)
- [Targeted Active Learning for Bayesian Decision-Making](https://mlsanity.com/paper/2106.04193/) (2021)
- [Vector Optimization with Stochastic Bandit Feedback](https://mlsanity.com/paper/2110.12311/) (2021)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choices](https://mlsanity.com/paper/2403.03589/) (2024)
- [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)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [An Experimental Design for Anytime-Valid Causal Inference on Multi-Armed Bandits](https://mlsanity.com/paper/2311.05794/) (2023)
- [Adaptive Experimentation in the Presence of Exogenous Nonstationary Variation](https://mlsanity.com/paper/2202.09036/) (2022)
- [On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits](https://mlsanity.com/paper/2210.00895/) (2022)
- [Differential Good Arm Identification](https://mlsanity.com/paper/2303.07154/) (2023)
- [Optimal Best-Arm Identification in Bandits with Access to Offline Data](https://mlsanity.com/paper/2306.09048/) (2023)
- [Diffusion Approximations for a Class of Sequential Testing Problems](https://mlsanity.com/paper/2102.07030/) (2021)
- [A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits](https://mlsanity.com/paper/2105.12978/) (2021)
- [Risk and optimal policies in bandit experiments](https://mlsanity.com/paper/2112.06363/) (2021)
- [Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning](https://mlsanity.com/paper/2211.12004/) (2022)

## Abstract (arXiv)

This paper considers the optimal adaptive allocation of measurement effort for identifying the best among a finite set of options or designs. An experimenter sequentially chooses designs to measure and observes noisy signals of their quality with the goal of confidently identifying the best design after a small number of measurements. This paper proposes three simple and intuitive Bayesian algorithms for adaptively allocating measurement effort, and formalizes a sense in which these seemingly naive rules are the best possible. One proposal is top-two probability sampling, which computes the two designs with the highest posterior probability of being optimal, and then randomizes to select among these two. One is a variant of top-two sampling which considers not only the probability a design is optimal, but the expected amount by which its quality exceeds that of other designs. The final algorithm is a modified version of Thompson sampling that is tailored for identifying the best design. We prove that these simple algorithms satisfy a sharp optimality property. In a frequentist setting where the true quality of the designs is fixed, one hopes the posterior definitively identifies the optimal design, in the sense that that the posterior probability assigned to the event that some other design is optimal converges to zero as measurements are collected. We show that under the proposed algorithms this convergence occurs at an exponential rate, and the corresponding exponent is the best possible among all allocation