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

Laboratoire de Probabilités et Modèles Aléatoires
Department of Mathematics and Idss
Massachusetts Institute of Technology
Department of Economics
Princeton University
California Institute of Technology

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

143 Citations (Scopus)

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",

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