# Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 19 Sep 2026.

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

- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [A minimax and asymptotically optimal algorithm for stochastic bandits](https://mlsanity.com/paper/1702.07211/) (2017)
- [Double Explore-then-Commit: Asymptotic Optimality and Beyond](https://mlsanity.com/paper/2002.09174/) (2020)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [Weak Signal Asymptotics for Sequentially Randomized Experiments](https://mlsanity.com/paper/2101.09855/) (2021)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Comparison Lift: Bandit-based Experimentation System for Online Advertising](https://mlsanity.com/paper/2009.07899/) (2020)
- [Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits](https://mlsanity.com/paper/1511.06014/) (2015)
- [Thompson Sampling with Information Relaxation Penalties](https://mlsanity.com/paper/1902.04251/) (2019)
- [Computing a classic index for finite-horizon bandits](https://mlsanity.com/paper/2207.14189/) (2022)

## Abstract (arXiv)

We develop an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions to single-arm bandit (SAB) problems. Each SAB problem involves choosing between an unknown Bernoulli arm and a known reward. We show that minimizing worst-case regret of SAB problems over all non-anticipative policies admits an exact semi-infinite linear programming formulation. The resulting stopping policies offer a natural way to compare arms: the higher the known reward against which a policy continues sampling, the more promising the unknown arm. We turn this intuition into indices based on cumulative continuation probabilities, with a monotone adjustment and a reward-shortfall cap. By relating index errors to the regret of single-arm stopping policies, we establish a distribution-free regret bound of 4.45√KT+10.75K for K arms and horizon T. This bound matches the minimax-optimal regret order established in the literature. The guarantee extends to rewards supported on [0,1] through Bernoulli randomization. We also provide a finite-grid implementation with quantified approximation loss. In numerical experiments, the SAB-based index policy achieves lower worst-case regret than every tested benchmark policy across all evaluated numbers of arms and horizons, while closely matching the grid-based MAB minimax policy in the two-arm setting.