Abstract
We introduce a new multi-armed bandit (MAB) problem in which arms must be sampled in batches, rather than one at a time. This is motivated by applications in social media monitoring and biological screening where feedback is delayed or parallelized. We formalize the $(b, r)$-batch setting and propose two algorithms, BatchRacing and BatchSAR, for fixed-confidence and fixed-budget objectives respectively. Our theoretical and empirical results demonstrate that batching constraints do not significantly degrade sample complexity, offering near-optimal performance in real-world tasks.
Introduction
The classic Multi-Armed Bandit (MAB) framework typically assumes a sequential interaction: an agent pulls an arm, observes a reward, and uses this information to decide the next pull. However, many practical domains—such as high-throughput biological screening or API-limited social media monitoring—require decisions to be made in batches. For instance, a biologist using a 384-well plate must commit to 384 experiments simultaneously. This paper addresses the "Top-$k$ Identification" problem under such batch constraints.
The $(b, r)$-Batch Setting
The authors formalize this as the $(b, r)$-batch setting, defined by two parameters:
- $b$ (Batch Size): The total number of pulls that must be committed in each round.
- $r$ (Repeat Limit): The maximum number of times any single arm can be pulled within a single batch.
The central challenge is determining if this loss of adaptivity—the inability to react to every single data point immediately—fundamentally ruins the sample complexity.
Proposed Algorithms
Two primary algorithms are introduced to handle the two standard MAB objectives:
- BatchRacing (Fixed Confidence): Aimed at identifying the top-$k$ arms with a success probability of at least $1-\delta$ using the minimum number of batches. It employs a "Racing" strategy, maintaining confidence intervals and eliminating arms once they are statistically confirmed to be inside or outside the top-$k$ set.
- BatchSAR (Fixed Budget): Designed to find the best arms within a fixed budget of $B$ batches. It is an adaptation of the Successive Accepts and Rejects (SAR) algorithm, dividing the budget into phases and eliminating the least promising arms at each step.
Both algorithms utilize a RoundRobin sub-routine to distribute the $b$ pulls across surviving arms while respecting the $r$ constraint, ensuring efficient exploration.
Empirical Evaluation
The algorithms were validated on synthetic data and two significant real-world datasets:
- Biological Screening: Identifying genes that promote influenza virus replication from a dataset of 12,979 drosophila gene knockdowns.
- Social Media Monitoring: Identifying the top-100 most active users discussing "bullying" on Twitter from a pool of over 500,000 users.
Key Results and Insights
The study yields several critical findings:
- Minimal Adaptivity Gap: Theoretically, the "sample complexity" (total pulls) for batch MABs is nearly identical to sequential versions, with only a minor additive $\log n$ term representing the cost of batching.
- Efficiency of $r$: As long as the repeat limit $r$ is not excessively small relative to $b$, the number of rounds required is reduced by a factor of approximately $1/b$.
- Superiority over Naive Baselines: Simply treating a batch MAB as a sequential one by ignoring samples is highly inefficient. BatchSAR and BatchRacing significantly outperform standard RoundRobin strategies.
As shown in the figures, BatchSAR consistently achieves lower error rates compared to the Halving and RoundRobin baselines across different budgets and values of $k$.
Conclusion
This work bridges the gap between sequential MAB theory and batch-oriented practical applications. By proving that batching does not fundamentally ruin sample complexity and providing robust algorithms like BatchSAR, the authors enable more efficient decision-making in fields where parallelized experimentation is the norm. Future work includes exploring the exact lower bounds related to the repeat limit $r$ and adapting other MAB frameworks to the batch setting.
Summary updated