Thompson Exploration with Best Challenger Rule in Best Arm
  Identification
Jongyeong Lee Junya Honda Masashi Sugiyama
This paper studies the fixed-confidence best arm identification (BAI) problem
in the bandit framework in the canonical single-parameter exponential models.
For this problem, many policies have been proposed, but most of them require
solving an optimization problem at every round and/or are forced to explore an
arm at least a certain number of times except those restricted to the Gaussian
model. To address these limitations, we propose a novel policy that combines
Thompson sampling with a computationally efficient approach known as the best
challenger rule. While Thompson sampling was originally considered for
maximizing the cumulative reward, we demonstrate that it can be used to
naturally explore arms in BAI without forcing it. We show that our policy is
asymptotically optimal for any two-armed bandit problems and achieves near
optimality for general $K$-armed bandit problems for $K\geq 3$. Nevertheless,
in numerical experiments, our policy shows competitive performance compared to
asymptotically optimal policies in terms of sample complexity while requiring
less computation cost. In addition, we highlight the advantages of our policy
by comparing it to the concept of $\beta$-optimality, a relaxed notion of
asymptotic optimality commonly considered in the analysis of a class of
policies including the proposed one.