On Elimination Strategies for Bandit Fixed-Confidence Identification
Elimination algorithms for bandit identification, which prune the plausible
correct answers sequentially until only one remains, are computationally
convenient since they reduce the problem size over time. However, existing
elimination strategies are often not fully adaptive (they update their sampling
rule infrequently) and are not easy to extend to combinatorial settings, where
the set of answers is exponentially large in the problem dimension. On the
other hand, most existing fully-adaptive strategies to tackle general
identification problems are computationally demanding since they repeatedly
test the correctness of every answer, without ever reducing the problem size.
We show that adaptive methods can be modified to use elimination in both their
stopping and sampling rules, hence obtaining the best of these two worlds: the
algorithms (1) remain fully adaptive, (2) suffer a sample complexity that is
never worse of their non-elimination counterpart, and (3) provably eliminate
certain wrong answers early. We confirm these benefits experimentally, where
elimination improves significantly the computational complexity of adaptive
methods on common tasks like best-arm identification in linear bandits.