  We study the best-arm identification (BAI) problem with a fixed budget and
contextual (covariate) information. In each round of an adaptive experiment,
after observing contextual information, we choose a treatment arm using past
observations and current context. Our goal is to identify the best treatment
arm, which is a treatment arm with the maximal expected reward marginalized
over the contextual distribution, with a minimal probability of
misidentification. In this study, we consider a class of nonparametric bandit
models that converge to location-shift models when the gaps go to zero. First,
we derive lower bounds of the misidentification probability for a certain class
of strategies and bandit models (probabilistic models of potential outcomes)
under a small-gap regime. A small-gap regime is a situation where gaps of the
expected rewards between the best and suboptimal treatment arms go to zero,
which corresponds to one of the worst cases in identifying the best treatment
arm. We then develop the ``Random Sampling (RS)-Augmented Inverse Probability
weighting (AIPW) strategy,'' which is asymptotically optimal in the sense that
the probability of misidentification under the strategy matches the lower bound
when the budget goes to infinity in the small-gap regime. The RS-AIPW strategy
consists of the RS rule tracking a target sample allocation ratio and the
recommendation rule using the AIPW estimator.
