Batched Bandits with Crowd Externalities

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 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(sqrt{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(K ln T), sqrt{T ln T})), where K is the number of arms and T is the horizon.