Sub-sampling for Efficient Non-Parametric Bandit Exploration
Dorian Baudry, Emilie Kaufmann, Odalric-Ambrym Maillard
Abstract
In this paper we propose the first multi-armed bandit algorithm based on re-sampling that achieves asymptotically optimal regret simultaneously for different families of arms (namely Bernoulli, Gaussian and Poisson distributions). Unlike Thompson Sampling which requires to specify a different prior to be optimal in each case, our proposal RB-SDA does not need any distribution-dependent tuning. RB-SDA belongs to the family of Sub-sampling Duelling Algorithms (SDA) which combines the sub-sampling idea first used by the BESA and SSMC algorithms with different sub-sampling schemes. In particular, RB-SDA uses Random Block sampling. We perform an experimental study assessing the flexibility and robustness of this promising novel approach for exploration in bandit models.
BibTeX
@inproceedings{NEURIPS2020_3ab6be46,
author = {Baudry, Dorian and Kaufmann, Emilie and Maillard, Odalric-Ambrym},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {5468--5478},
publisher = {Curran Associates, Inc.},
title = {Sub-sampling for Efficient Non-Parametric Bandit Exploration},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/3ab6be46e1d6b21d59a3c3a0b9d0f6ef-Paper.pdf},
volume = {33},
year = {2020}
}