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