arXiv cs.AI· Bo Xue, Ji Cheng, Yuanyu Wan, Shuang Qiu·· 3 天前AI 评分20
多目标为何让识别更容易：偏好与反馈在多目标 bandit 最佳臂识别中的作用
When More Objectives Make Identification Easier: The Role of Preferences and Feedback
AI 导读
针对多目标 bandit 中的最佳臂识别（BAI），研究刻画了多目标何时以及为何比单目标更容易。对高斯 bandit，作者建立了在任意偏好序下一致成立的固定置信度特征时间下界，并在 Pareto、线性与字典序偏好下揭示三种现象：识别更大的最优集合可能比识别唯一最优解所需样本更少；向量反馈相对坐标反馈的优势取决于偏好序；多目标识别甚至可能比对应的最易单目标问题更省样本。
正文 · 原文
Abstract:Best-arm identification (BAI) aims to identify the optimal arm using as few samples as possible. While most existing work focuses on a single objective, many real-world applications involve multiple criteria, which motivates the study of BAI in multi-objective bandits. Intuitively, multi-objective identification seems harder, since the learner must identify optimal arms in a higher-dimensional reward space; however, the additional objectives also provide richer feedback that can reduce the required exploration. In this paper, we characterize when and why multiple objectives can make BAI easier. For Gaussian bandits, we establish a characteristic-time lower bound for fixed-confidence identification that holds uniformly across preference orders. Through explicit comparisons under Pareto, linear, and lexicographic preferences, we reveal three phenomena: (i) identifying a larger optimal set can require fewer samples than identifying a unique optimum; (ii) the advantage of vector feedback over coordinate feedback depends fundamentally on the preference order; and (iii) multi-objective identification can require fewer samples than even the easiest corresponding single-objective problem. Finally, we propose Order-Aware Track-and-Stop (OATS), an algorithm that is correct at any prescribed confidence level and asymptotically matches the lower bound.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.18577 [cs.LG] |
| (or arXiv:2610.18577v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.18577 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Bo Xue [view email]
[v1]
Tue, 13 Oct 2026 15:42:39 UTC (158 KB)
来源：arXiv cs.AI · arxiv.org