The multi-armed bandit problem: An efficient nonparametric solution
Author:
- Hock Peng ChanHCHock Peng Chan
- 1 February 2020
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Statistics
- Vol. 48 (1) , 346-373
Abstract
Lai and Robbins (Adv. in Appl. Math. 6 (1985) 4–22) and Lai (Ann. Statist. 15 (1987) 1091–1114) 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. Nonparametric arm allocation procedures like $\epsilon $-greedy, Boltzmann exploration and BESA were studied, and modified versions of the UCB procedure were also analyzed under nonparametric settings. However, unlike UCB these nonparametric procedures are not efficient under general parametric settings. In this paper, we propose efficient nonparametric procedures.Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Optimal learning and experimentation in bandit problemsJournal of Economic Dynamics and Control, 2002
- Sample mean based index policies byO(logn) regret for the multi-armed bandit problemAdvances in Applied Probability, 1995
- Nonparametric bandit methodsAnnals of Operations Research, 1991
- Asymptotically efficient adaptive allocation schemes for controlled Markov chains: finite parameter spaceIEEE Transactions on Automatic Control, 1989
- Optimal stopping and dynamic allocationAdvances in Applied Probability, 1987
- Adaptive Treatment Allocation and the Multi-Armed Bandit ProblemThe Annals of Statistics, 1987
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- A dynamic allocation index for the discounted multiarmed bandit problemBiometrika, 1979
- A Bernoulli Two-armed BanditThe Annals of Mathematical Statistics, 1972
- Some Remarks on the Two-Armed BanditThe Annals of Mathematical Statistics, 1970