Optimal Best Arm Identification with Fixed Confidence

By Aurélien Garivier, Emilie Kaufmann. Annual Conference Computational Learning Theory, 2016

421 citations recorded by the source corpus.

We give a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the `Track-and-Stop' strategy, which we prove to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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

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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Simple Bayesian Algorithms for Best Arm Identification (2016, methodology): “…of the complexity of best-arm identification appear to have been derived independently in statistics [Chernoff, 1959, Jennison et al., 1982], simulation optimization [Glynn and Juneja, 2004], and, concurrently with this paper, in the machine learning literature [Garivier and Kaufmann, 2016].”
Bandit Algorithms (2020, methodology): “4 is due to [Gerchinovitz, 2013, Thm. 10]. A recent paper by Rakhlin and Sridharan [2017] also discusses relationship between online learning regret bounds and self-normalized tail bounds of the type given here.”
Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling (2018, background): “As explained by [10] the oracle weights correspond to the fraction of samples that should be allocated to each arm under a strategy matching the lower bound.”