CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20160418-155357882

[img] PDF - Published Version
See Usage Policy.

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

125kB
[img] PDF - Submitted Version
See Usage Policy.

371kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160418-155357882

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1214/15-AOS1381DOIArticle
http://projecteuclid.org/euclid.aos/1458245731PublisherArticle
http://arxiv.org/abs/1505.00369arXivDiscussion Paper
http://projecteuclid.org/euclid.aos/1458245731#supplementalPublisherSupplementary 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.
Funders:
Funding AgencyGrant Number
Agence Nationale pour la Recherche (ANR)ANR-13-JS01-0004
NSFDMS-13-17308
NSFSES-1156154
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
DOI:10.1214/15-AOS1381
Record Number:CaltechAUTHORS:20160418-155357882
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160418-155357882
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66261
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:19 Apr 2016 17:59
Last Modified:10 Nov 2021 23:55

Repository Staff Only: item control page