Batched bandit problems

DOI10.1214/15-AOS1381zbMATH Open1338.62180arXiv1505.00369OpenAlexW1958090791MaRDI QIDQ282463FDOQ282463

Authors: Vianney Perchet, Philippe Rigollet, Sylvain Chassang, Erik Snowberg 

Publication date: 12 May 2016

Published in: The Annals of Statistics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1505.00369

Recommendations

• Bandit algorithms
• scientific article; zbMATH DE number 3854141
• Multistage bandit problems
• scientific article; zbMATH DE number 4078557
• Generalized Bandit Problems
• Combinatorial bandits
• scientific article; zbMATH DE number 4059270
• The Nonstochastic Multiarmed Bandit Problem
• Bandit problems with Lévy processes

zbMATH Keywords

sample size determinationbatchesgrouped clinical trialsmulti-armed bandit problemsmulti-phase allocationregret boundsswitching cost

Mathematics Subject Classification ID

Applications of statistics to biology and medical sciences; meta analysis (62P10) Sequential statistical design (62L05) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Title not available (Why is that?)
• Introduction to nonparametric estimation
• Asymptotically efficient adaptive allocation rules
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some aspects of the sequential design of experiments
• Finite-time analysis of the multiarmed bandit problem
• Regret bounds and minimax policies under partial monitoring
• An Asymptotic Minimax Theorem for the Two Armed Bandit Problem
• A Two-Sample Test for a Linear Hypothesis Whose Power is Independent of the Variance
• Optimal few-stage designs
• Sequential experimentation in clinical trials. Design and analysis
• Multistage bandit problems
• Asymptotically optimal multistage tests of simple hypotheses
• Batched bandit problems
• Regret Minimization for Reserve Prices in Second-Price Auctions
• A Sequential Design for the Two Armed Bandit
• Title not available (Why is that?)
• A Learning Approach for Interactive Marketing to a Customer Segment
• The multi-armed bandit problem with covariates
• Kullback-Leibler upper confidence bounds for optimal sequential allocation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Remarks on the Two-Armed Bandit
• On the Non-Existence of Tests of "Student's" Hypothesis Having Power Functions Independent of $\sigma$
• TWO-STAGE PROCEDURES FOR ESTIMATING THE DIFFERENCE BETWEEN MEANS
• SOME PROBLEMS OF OPTIMUM SAMPLING
• UCB revisited: improved regret bounds for the stochastic multi-armed bandit problem

Cited In (18)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Learning the distribution with largest mean: two bandit frameworks
• Bayesian adaptive bandit-based designs using the Gittins index for multi-armed trials with normally distributed endpoints
• Invariant description of control in a Gaussian one-armed bandit problem
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits Under Realizability
• Batched bandit problems
• Title not available (Why is that?)
• Optimization of two-alternative batch processing with parameter estimation based on data inside batches
• Functional Sequential Treatment Allocation
• UCB strategies and optimization of batch processing in a one-armed bandit problem
• Greedy Algorithm Almost Dominates in Smoothed Contextual Bandits
• Rejoinder
• Title not available (Why is that?)
• Learning unknown service rates in queues: a multiarmed bandit approach
• Customization of J. Bather's UCB strategy for a Gaussian multiarmed bandit
• Online learning of energy consumption for navigation of electric vehicles
• Gaussian two-armed bandit: limiting description

This page was built for publication: Batched bandit problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q282463)