# Batched Bandits with Crowd Externalities

arXiv: https://arxiv.org/abs/2109.14733 · HTML: https://mlsanity.com/paper/2109.14733/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 5 of 5)

- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Recovering Bandits](https://mlsanity.com/paper/1910.14354/) (2019)
- [Multi-armed Bandit Problem with Known Trend](https://mlsanity.com/paper/1508.07091/) (2015)
- [Bayesian Best-Arm Identification for Selecting Influenza Mitigation Strategies](https://mlsanity.com/paper/1711.06299/) (2017)
- [Bandit Learning with Positive Externalities](https://mlsanity.com/paper/1802.05693/) (2018)

## Abstract (arXiv)

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 textitcrowd, 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(√fracln xx+ε) 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 Oleft(max(Kln T,√Tln T)right), where K is the number of arms and T is the horizon.