Batched bandit problems
Authors:
- Vianney PerchetVPVianney Perchet
- Philippe RigolletPRPhilippe Rigollet
- Sylvain ChassangSCSylvain Chassang
- Erik SnowbergESErik Snowberg
Top Cited Papers
Open Access
- 1 April 2016
- journal article
- research article
- Published by Institute of Mathematical Statistics in The Annals of Statistics
- Vol. 44 (2) , 660-681
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 32 references indexed in Scilit:
- A survey on the bandit problem with switching costsDe Economist, 2004
- Some Remarks on the Two-Armed BanditThe Annals of Mathematical Statistics, 1970
- A Two-Stage Model for Selecting One of Two Treatments1965
- A Model for Selecting One of Two Medical TreatmentsJournal of the American Statistical Association, 1963
- A Sequential Design for the Two Armed BanditThe Annals of Mathematical Statistics, 1960
- An Asymptotic Minimax Theorem for the Two Armed Bandit ProblemThe Annals of Mathematical Statistics, 1960
- SOME PROBLEMS OF OPTIMUM SAMPLINGBiometrika, 1954
- TWO-STAGE PROCEDURES FOR ESTIMATING THE DIFFERENCE BETWEEN MEANSBiometrika, 1954
- On the Non-Existence of Tests of "Student's" Hypothesis Having Power Functions Independent of $\sigma$The Annals of Mathematical Statistics, 1940
- ON THE LIKELIHOOD THAT ONE UNKNOWN PROBABILITY EXCEEDS ANOTHER IN VIEW OF THE EVIDENCE OF TWO SAMPLESBiometrika, 1933