  We study $K$-armed bandit problems where the reward distributions of the arms
are all supported on the $[0,1]$ interval. It has been a challenge to design
regret-efficient randomized exploration algorithms in this setting. Maillard
sampling \cite{maillard13apprentissage}, an attractive alternative to Thompson
sampling, has recently been shown to achieve competitive regret guarantees in
the sub-Gaussian reward setting \cite{bian2022maillard} while maintaining
closed-form action probabilities, which is useful for offline policy
evaluation. In this work, we propose the Kullback-Leibler Maillard Sampling
(KL-MS) algorithm, a natural extension of Maillard sampling for achieving
KL-style gap-dependent regret bound. We show that KL-MS enjoys the asymptotic
optimality when the rewards are Bernoulli and has a worst-case regret bound of
the form $O(\sqrt{\mu^*(1-\mu^*) K T \ln K} + K \ln T)$, where $\mu^*$ is the
expected reward of the optimal arm, and $T$ is the time horizon length.
