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

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
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
Publication status	Published - 1 Apr 2016
Externally published	Yes

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{de2eceb36db34d3c9a88681f99ed9f74,

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,

day = "1",

doi = "10.1214/15-AOS1381",

language = "English",

volume = "44",

pages = "660--681",

journal = "Annals of Statistics",

issn = "0090-5364",

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/1

Y1 - 2016/4/1

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

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

Keywords

Access to Document

Fingerprint

Cite this