SOURCE-LINKED INTELLIGENCE

Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping

arXiv · AI, language, vision and robotics · article · Sep 19, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global