Better algorithms improve budgeted exploration in decision making
Budgeted Bayesian Bandits for Future Utilization
Machine LearningData Structures and Algorithms
Summary
The paper looks at a problem where you have limited chances to try new options before picking the best one to keep using. Existing methods only guarantee to find about one third or less of the best possible outcome. The authors found ways to do better, giving algorithms that come closer to 43% or even 63% of the best results under certain conditions. These improvements help decide when to stop testing and start using the best option confidently.
What this means in practice
- •For online advertising teams: Optimize testing ad variants within fixed budgets before choosing the best-performing ads for campaigns.
- •For clinical trial coordinators: Plan limited patient trials to explore treatment options efficiently before committing to the most promising therapy.
Authors
Sudipto Guha
Abstract
The multi-armed bandit problem models the trade-off between exploration and exploitation. In this paper, we study the variant where exploration has a hard budget and precedes exploitation. Prior guarantees include a 1/3 approximation by Guha and Munagala using Lagrangian duality, and a 4/27 approximation by Ma against a primal linear programming relaxation for a more general model. We show that the analyses of both algorithms are tight, even when their relaxations are asymptotically exact. We provide a different efficient algorithm that achieves a 0.43 approximation. We then provide an efficient algorithm whose guarantee approaches 1-e^{-1} approx 0.63 for bounded exchangeable reward observations in a non-vanishing regime, which is asymptotically tight against natural linear programming relaxations. The technique also gives certificates for stopping sequential model evaluation.