The Multi-Armed Bandit Problem: An Efficient Non-Parametric Solution
Preprint
Abstract
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 within a specified parametric family. 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 an efficient non-parametric subsample comparison procedure.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Kullback–Leibler upper confidence bounds for optimal sequential allocationThe Annals of Statistics, 2013
- Optimal learning and experimentation in bandit problemsJournal of Economic Dynamics and Control, 2002
- Optimal Adaptive Policies for Sequential Allocation ProblemsAdvances in Applied Mathematics, 1996
- Adaptive Treatment Allocation and the Multi-Armed Bandit ProblemThe Annals of Statistics, 1987
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985