Choosing Answers in $\varepsilon$-Best-Answer Identification for Linear Bandits
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 \textit{furthest answer} should
be identified. Using that insight to choose the candidate answer carefully, we
develop a simple procedure to adapt best-arm identification algorithms to
tackle $\varepsilon$-best-answer identification in transductive linear
stochastic bandits. Finally, we propose an asymptotically optimal algorithm for
this setting, which is shown to achieve competitive empirical performance
against existing modified best-arm identification algorithms.