Regret Bounds for Batched Bandits
This addresses the problem of efficient decision-making in bandit settings with limited batch updates, which is relevant for applications like clinical trials or online advertising.
The paper tackles the batched bandit problem by developing algorithms for stochastic and adversarial settings that achieve optimal expected regrets using only a logarithmic number of batches, with improvements over previous bounds.
We present simple and efficient algorithms for the batched stochastic multi-armed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets that improve over the best-known regret bounds for any number of batches. In particular, our algorithms in both settings achieve the optimal expected regrets by using only a logarithmic number of batches. We also study the batched adversarial multi-armed bandit problem for the first time and find the optimal regret, up to logarithmic factors, of any algorithm with predetermined batch sizes.