Minimax policy improves decision making in bernoulli bandit problems
Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
Machine Learning
Summary
Choosing the best option among several uncertain choices is a common problem in fields like online advertising or clinical trials. The authors develop a strategy that focuses on single choices and compares them to known rewards to decide when to stop exploring. Their method guarantees good performance across all possible situations and works well when multiple choices are involved. Tests show this strategy outperforms existing methods, especially when dealing with several options over limited trials.
What this means in practice
- •For online advertisers: Select and stop showing uncertain ads efficiently to minimize lost revenue over limited time campaigns.
- •For clinical trial designers: Decide when to stop testing experimental treatments against standard care to reduce patient risk while gaining useful data.
Authors
Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann
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\sqrt{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.