Papers for

online advertisers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Minimax policy improves decision making in bernoulli bandit problems

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\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.

Sat 19 SeptMachine Learning
The gist
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.
Open → 2609.22690v1