A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits
Antoine Barrier, Aurélien Garivier, Tomáš Kocák
Abstract
We propose a new strategy for best-arm identification with fixed confidence of Gaussian variables with bounded means and unit variance. This strategy, called Exploration-Biased Sampling, is not only asymptotically optimal: it is to the best of our knowledge the first strategy with non-asymptotic bounds that asymptotically matches the sample complexity. But the main advantage over other algorithms like Track-and-Stop is an improved behavior regarding exploration: Exploration-Biased Sampling is biased towards exploration in a subtle but natural way that makes it more stable and interpretable. These improvements are allowed by a new analysis of the sample complexity optimization problem, which yields a faster numerical resolution scheme and several quantitative regularity results that we believe of high independent interest.
BibTeX
@InProceedings{pmlr-v151-barrier22a,
title = { A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits },
author = {Barrier, Antoine and Garivier, Aur\'elien and Koc\'ak, Tom\'a\v{s}},
booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
pages = {10078--10109},
year = {2022},
editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
volume = {151},
series = {Proceedings of Machine Learning Research},
month = {28--30 Mar},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v151/barrier22a/barrier22a.pdf},
url = {https://proceedings.mlr.press/v151/barrier22a.html},
abstract = { We propose a new strategy for best-arm identification with fixed confidence of Gaussian variables with bounded means and unit variance. This strategy, called Exploration-Biased Sampling, is not only asymptotically optimal: it is to the best of our knowledge the first strategy with non-asymptotic bounds that asymptotically matches the sample complexity. But the main advantage over other algorithms like Track-and-Stop is an improved behavior regarding exploration: Exploration-Biased Sampling is biased towards exploration in a subtle but natural way that makes it more stable and interpretable. These improvements are allowed by a new analysis of the sample complexity optimization problem, which yields a faster numerical resolution scheme and several quantitative regularity results that we believe of high independent interest. }
}