Multi-objective bandits identify small option sets for best overall outcomes
Few-for-Many Best-Arm Identification in Multi-Objective Bandits
Machine LearningArtificial Intelligence
Summary
Sometimes systems must work well across many goals but can only try a few choices. The authors study how to find a small set of options that do well overall, even if not perfect for every goal. They develop methods to pick these small sets efficiently by learning from noisy feedback. Their work shows that considering groups of goals together helps save effort in learning the best options. Experiments on simulated and real tasks confirm these savings.
What this means in practice
- •For marketing campaign teams: Find a small set of campaign strategies that perform well across multiple marketing goals to efficiently allocate budget and efforts.
- •For cloud resource managers: Select a limited number of resource allocation policies that balance performance across multiple objectives like cost, speed, and reliability.
Authors
Bo Xue, Yilu Liu, Haodong Jing, Hongzong Li, Xi Lin, Shuang Qiu
Abstract
Real-world systems often serve many objectives but can deploy only a few options, whose performance must be learned from noisy feedback. Modeling each option as an arm in a multi-objective bandit, we introduce \emph{few-for-many best-arm identification}, which seeks a small set of arms minimizing the worst weighted degradation from the objective-wise optima, rather than the best arm for every objective. We consider both known objective groups and latent groups specified only by a representative budget, and propose \textsc{GFM-Elim} and \textsc{AFM-Elim} with instance-dependent sample-complexity guarantees. For Gaussian rewards, we further derive a lower bound for the latent-group setting and show that it is asymptotically attainable with high probability by an oracle-based Track-and-Stop procedure. Our results show that sharing observations across objectives and ignoring irrelevant objective-wise distinctions can substantially reduce the sampling cost, as confirmed by experiments on synthetic and real-world tasks.