Batched bandit problems
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg
The Annals of Statistics · 2016 · Volume 44 · Issue 2
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
62C20, 62L05, batches, grouped clinical trials, Multi-armed bandit problems, multi-phase allocation, regret bounds, sample size determination, switching cost
Enable JavaScript for citation tools and additional paper interactions.