The Role of Contextual Information in Best Arm Identification
  We study the best-arm identification problem with fixed confidence when
contextual (covariate) information is available in stochastic bandits. Although
we can use contextual information in each round, we are interested in the
marginalized mean reward over the contextual distribution. Our goal is to
identify the best arm with a minimal number of samplings under a given value of
the error rate. We show the instance-specific sample complexity lower bounds
for the problem. Then, we propose a context-aware version of the
"Track-and-Stop" strategy, wherein the proportion of the arm draws tracks the
set of optimal allocations and prove that the expected number of arm draws
matches the lower bound asymptotically. We demonstrate that contextual
information can be used to improve the efficiency of the identification of the
best marginalized mean reward compared with the results of Garivier & Kaufmann
(2016). We experimentally confirm that context information contributes to
faster best-arm identification.
