Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
Abstract
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.
Related
- Sharp Non-Asymptotic Analysis of the Penalized Challenger in β-EB-TCI for Bernoulli Bandits
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Minimax-Optimal Early Stopping for Continuous-Time SGD via the Discrepancy Principle
- Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
BibTeX
@misc{liu2026multiarmed,
title = {{Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping}},
author = {Huikang Liu and Zhengchao Wang and Daniel Kuhn and Wolfram Wiesemann},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22690},
eprint = {2609.22690},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22690},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
AU - Huikang Liu
AU - Zhengchao Wang
AU - Daniel Kuhn
AU - Wolfram Wiesemann
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.22690
UR - https://arxiv.org/abs/2609.22690
AB - 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.
ER -