Simple Bayesian Algorithms for Best Arm Identification

By Daniel Russo. Annual Conference Computational Learning Theory, 2016

314 citations recorded by the source corpus.

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. Just as the multiarmed bandit problem crystallizes the tradeoff between exploration and exploitation, this “pure exploration” variant crystallizes the challenge of rapidly gathering information before committing to a final decision. The paper proposes several simple Bayesian algorithms for allocating measurement effort and, by characterizing fundamental asymptotic limits on the performance of any algorithm, formalizes a sense in which these seemingly naive algorithms are the best possible.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/a4668ef49df712cf0d66351885c38e9d2ce2a6a2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Management Science and Operations Research

Citations in the corpus

Accurate Inference for Adaptive Linear Models (2017, background): “This is true for certain regret-optimal algorithms [Russo, 2016, Garivier and Cappé, 2011].”
Learning the distribution with largest mean: two bandit frameworks (2017, background): “[Russo, 2016] Russo, D. (2016).”
A Tutorial on Thompson Sampling (2017, background): “Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband and Zheng Wen (2018), “A Tutorial on Thompson Sampling”, : Vol.”
Optimal Testing in the Experiment-rich Regime (2018, background): “There is also a strong connection to the multi-armed bandit literature [Gittins et al., 2011, Bubeck and Cesa-Bianchi, 2012], especially the pure exploration problem [Bubeck et al., 2009, Jamieson et al., 2014, Russo, 2016], where the goal is to find the best arm.”
Bandit Algorithms (2020, background): “We should mention there is a recent book on bandits by Slivkins [2018] that is currently in progress and freely available on-line.”