A Caltech Library Service

Batched bandit problems

Perchet, Vianney and Rigollet, Philippe and Chassang, Sylvain and Snowberg, Erik (2016) Batched bandit problems. Annals of Statistics, 44 (2). pp. 660-681. ISSN 0090-5364. doi:10.1214/15-AOS1381.

[img] PDF - Published Version
See Usage Policy.

[img] PDF (additional simulations, including some using real data) - Supplemental Material
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper Information
Additional Information:© 2016 Institute of Mathematical Statistics. Received May 2015; revised August 2015. Supported by ANR Grant ANR-13-JS01-0004. Supported by NSF Grants DMS-13-17308 and CAREER. Supported by NSF Grant SES-1156154.
Funding AgencyGrant Number
Agence Nationale pour la Recherche (ANR)ANR-13-JS01-0004
Subject Keywords:Multi-armed bandit problems, regret bounds, batches, multi-phase allocation, grouped clinical trials, sample size determination, switching cost
Issue or Number:2
Classification Code:MSC2010 subject classifications: Primary 62L05; secondary 62C20
Record Number:CaltechAUTHORS:20160418-155357882
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66261
Deposited By: Tony Diaz
Deposited On:19 Apr 2016 17:59
Last Modified:10 Nov 2021 23:55

Repository Staff Only: item control page