arXiv：cs.AI· Bo Xue, Yilu Liu, Haodong Jing, Hongzong Li, Xi Lin, Shuang Qiu·· 20 小时前
多目标 Bandit 中的 Few-for-Many 最佳臂识别
Few-for-Many Best-Arm Identification in Multi-Objective Bandits
AI 导读
研究提出多目标 bandit 中的 few-for-many 最佳臂识别问题，目标是找到一小组臂使相对各目标最优值的最坏加权退化最小，而非为每个目标找最优臂。作者提出 GFM-Elim 与 AFM-Elim 算法，并给出实例相关的样本复杂度保证，覆盖已知目标分组和仅由代表性预算指定的潜在分组两种设定。
正文
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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.16840 [cs.LG] |
| (or arXiv:2610.16840v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.16840 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Bo Xue [view email]
[v1]
Mon, 12 Oct 2026 14:18:08 UTC (115 KB)
来源：arXiv：cs.AI · arxiv.org