arXiv：cs.AI· Bo Xue, Ji Cheng, Yuanyu Wan, Shuang Qiu·· 20 小时前
多目标为何让识别更容易：偏好与反馈在多目标老虎机中的作用
When More Objectives Make Identification Easier: The Role of Preferences and Feedback
AI 导读
针对多目标老虎机中的最优臂识别（BAI），研究为高斯老虎机建立了在偏好序上一致成立的固定置信度特征时间下界，并通过 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