Batched bandit problems

Vianney Perchet; Philippe Rigollet; Sylvain Chassang; Erik Snowberg

doi:10.1214/15-AOS1381

Batched bandit problems

Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg

Research output: Contribution to journal › Article › peer-review

105 Scopus citations

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.

Original language	English (US)
Pages (from-to)	660-681
Number of pages	22
Journal	Annals of Statistics
Volume	44
Issue number	2
DOIs	https://doi.org/10.1214/15-AOS1381
State	Published - Apr 2016

All Science Journal Classification (ASJC) codes

Statistics and Probability
Statistics, Probability and Uncertainty

Keywords

Batches
Grouped clinical trials, sample size determination, switching cost
Multi-armed bandit problems
Multi-phase allocation
Regret bounds

Access to Document

10.1214/15-AOS1381

Cite this

@article{4b18eeff7ed44724a1965f099aad5a5f,

title = "Batched bandit problems",

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 = "Batches, Grouped clinical trials, sample size determination, switching cost, Multi-armed bandit problems, Multi-phase allocation, Regret bounds",

author = "Vianney Perchet and Philippe Rigollet and Sylvain Chassang and Erik Snowberg",

note = "Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2016.",

year = "2016",

month = apr,

doi = "10.1214/15-AOS1381",

language = "English (US)",

volume = "44",

pages = "660--681",

journal = "Annals of Statistics",

issn = "0090-5364",

publisher = "Institute of Mathematical Statistics",

number = "2",

}

TY - JOUR

T1 - Batched bandit problems

AU - Perchet, Vianney

AU - Rigollet, Philippe

AU - Chassang, Sylvain

AU - Snowberg, Erik

N1 - Publisher Copyright: © Institute of Mathematical Statistics, 2016.

PY - 2016/4

Y1 - 2016/4

N2 - 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.

AB - 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.

KW - Batches

KW - Grouped clinical trials, sample size determination, switching cost

KW - Multi-armed bandit problems

KW - Multi-phase allocation

KW - Regret bounds

UR - http://www.scopus.com/inward/record.url?scp=84963656247&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963656247&partnerID=8YFLogxK

U2 - 10.1214/15-AOS1381

DO - 10.1214/15-AOS1381

M3 - Article

AN - SCOPUS:84963656247

SN - 0090-5364

VL - 44

SP - 660

EP - 681

JO - Annals of Statistics

JF - Annals of Statistics

IS - 2

ER -

Batched bandit problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this