Batched bandit problems
Authors:
- Vianney PerchetVPVianney Perchet
- Philippe RigolletPRPhilippe Rigollet
- Sylvain ChassangSCSylvain Chassang
- Erik SnowbergESErik Snowberg
Preprint
Abstract
Motivated by practical applications, chiefly clinical trials, we study the regret achievable for stochastic bandits under the constraint that the employed policy must split trials into a small number of batches. We propose a simple policy, and show that a very small number of batches gives close to minimax optimal regret bounds. As a byproduct, we derive optimal policies with low switching cost for stochastic bandits.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problemPeriodica Mathematica Hungarica, 2010
- Asymptotically optimal multistage tests of simple hypothesesThe Annals of Statistics, 2007
- A survey on the bandit problem with switching costsDe Economist, 2004
- Optimal few-stage designsJournal of Statistical Planning and Inference, 2002
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- Group Sequential Methods with Applications to Clinical Trials1999
- Multistage bandit problemsJournal of Statistical Planning and Inference, 1996
- Asymptotically efficient adaptive allocation rulesAdvances in Applied Mathematics, 1985
- Randomized Allocation of Treatments in Sequential ExperimentsJournal of the Royal Statistical Society Series B: Statistical Methodology, 1981
- Some aspects of the sequential design of experimentsBulletin of the American Mathematical Society, 1952