  Lai and Robbins (1985) and Lai (1987) provided efficient parametric solutions
to the multi-armed bandit problem, showing that arm allocation via upper
confidence bounds (UCB) achieves minimum regret. These bounds are constructed
from the Kullback-Leibler information of the reward distributions, estimated
from specified parametric families. In recent years there has been renewed
interest in the multi-armed bandit problem due to new applications in machine
learning algorithms and data analytics. Non-parametric arm allocation
procedures like $\epsilon$-greedy, Boltzmann exploration and BESA were studied,
and modified versions of the UCB procedure were also analyzed under
non-parametric settings. However unlike UCB these non-parametric procedures are
not efficient under general parametric settings. In this paper we propose
efficient non-parametric procedures.
