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

	PDF - Published Version See Usage Policy. 247kB
	PDF (additional simulations, including some using real data) - Supplemental Material See Usage Policy. 125kB
	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:

URL	URL Type	Description
http://dx.doi.org/10.1214/15-AOS1381	DOI	Article
http://projecteuclid.org/euclid.aos/1458245731	Publisher	Article
http://arxiv.org/abs/1505.00369	arXiv	Discussion Paper
http://projecteuclid.org/euclid.aos/1458245731#supplemental	Publisher	Supplementary 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 Agency	Grant Number
Agence Nationale pour la Recherche (ANR)	ANR-13-JS01-0004
NSF	DMS-13-17308
NSF	SES-1156154

Subject Keywords:

Multi-armed bandit problems, regret bounds, batches, multi-phase allocation, grouped clinical trials, sample size determination, switching cost

Issue or Number:

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