ICML 2022spotlight10 citations
Choosing Answers in Epsilon-Best-Answer Identification for Linear Bandits
Abstract
In pure-exploration problems, information is gathered sequentially to answer a question on the stochastic environment. While best-arm identification for linear bandits has been extensively studied in recent years, few works have been dedicated to identifying one arm that is $\varepsilon$-close to the best one (and not exactly the best one). In this problem with several correct answers, an identification algorithm should focus on one candidate among those answers and verify that it is correct. We demonstrate that picking the answer with highest mean does not allow an algorithm to reach asymptotic optimality in terms of expected sample complexity. Instead, a
BibTeX
@InProceedings{pmlr-v162-jourdan22a,
title = {Choosing Answers in Epsilon-Best-Answer Identification for Linear Bandits},
author = {Jourdan, Marc and Degenne, R{\'e}my},
booktitle = {Proceedings of the 39th International Conference on Machine Learning},
pages = {10384--10430},
year = {2022},
editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
volume = {162},
series = {Proceedings of Machine Learning Research},
month = {17--23 Jul},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v162/jourdan22a/jourdan22a.pdf},
url = {https://proceedings.mlr.press/v162/jourdan22a.html},
abstract = {In pure-exploration problems, information is gathered sequentially to answer a question on the stochastic environment. While best-arm identification for linear bandits has been extensively studied in recent years, few works have been dedicated to identifying one arm that is $\varepsilon$-close to the best one (and not exactly the best one). In this problem with several correct answers, an identification algorithm should focus on one candidate among those answers and verify that it is correct. We demonstrate that picking the answer with highest mean does not allow an algorithm to reach asymptotic optimality in terms of expected sample complexity. Instead, a