Batched Multi-armed Bandits Problem

Abstract

In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the regret for the multi-armed case is still open. Moreover, the question whether adaptively chosen batch sizes will help to reduce the regret also remains underexplored. In this paper, we propose the BaSE (batched successive elimination) policy to achieve the rate-optimal regrets (within logarithmic factors) for batched multi-armed bandits, with matching lower bounds even if the batch sizes are determined in an adaptive manner.

To appear in NeurIPS 2019 as an oral presentation

References in corpus (3)

• Batched bandit problems
• Online Learning with Switching Costs and Other Adaptive Adversaries
• Bounded regret in stochastic multi-armed bandits

Cited by in corpus (7)

• Advances of Machine Learning in Materials Science: Ideas and Techniques
• Provably Efficient Q-Learning with Low Switching Cost
• Online Learning of Energy Consumption for Navigation of Electric Vehicles
• Diffusion Approximations for Thompson Sampling in the Small Gap Regime
• Online Batch Decision-Making with High-Dimensional Covariates
• Asymptotic Performance of Thompson Sampling in the Batched Multi-Armed Bandits
• Batched Bandits with Crowd Externalities