2017/03/24 by Hock Peng Chan, Chan, Hock Peng
Mathematics · #FOS: Mathematics #Statistics Theory (math.ST) #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1703.08285
arxiv created 2019/01/16 · arxiv updated 2019/01/17
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 ε-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.