# Best arm identification in rare events

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 14 Mar 2023.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)

## Abstract (arXiv)

We consider the best arm identification problem in the stochastic multi-armed bandit framework where each arm has a tiny probability of realizing large rewards while with overwhelming probability the reward is zero. A key application of this framework is in online advertising where click rates of advertisements could be a fraction of a single percent and final conversion to sales, while highly profitable, may again be a small fraction of the click rates. Lately, algorithms for BAI problems have been developed that minimise sample complexity while providing statistical guarantees on the correct arm selection. As we observe, these algorithms can be computationally prohibitive. We exploit the fact that the reward process for each arm is well approximated by a Compound Poisson process to arrive at algorithms that are faster, with a small increase in sample complexity. We analyze the problem in an asymptotic regime as rarity of reward occurrence reduces to zero, and reward amounts increase to infinity. This helps illustrate the benefits of the proposed algorithm. It also sheds light on the underlying structure of the optimal BAI algorithms in the rare event setting.