Abstract
In Batched Multi-Armed Bandits (BMAB), the policy is not allowed to be updated at each time step. Usually, the setting asserts a maximum number of allowed policy updates and the algorithm schedules them so that to minimize the expected regret. In this paper, we describe a novel setting for BMAB, with the following twist: the timing of the policy update is not controlled by the BMAB algorithm, but instead the amount of data received during each batch, called \textit{crowd}, is influenced by the past selection of arms. We first design a near-optimal policy with approximate knowledge of the parameters that we prove to have a regret in O(√ln x/x+ε) where x is the size of the crowd and ε is the parameter error. Next, we implement a UCB-inspired algorithm that guarantees an additional regret in O(max(Kln T,√Tln T)), where K is the number of arms and T is the horizon.