提出高效算法,一次性找出多目标中最优的臂,保证误差极小。
Optimal Multi-Objective Best Arm Identification with Fixed Confidence
- 用代理比例设计采样策略,避开复杂优化计算。
- 理论证明算法渐近最优,实验验证效率显著提升。
- 适合需同时优化多个指标的场景,如多任务推荐系统。
考虑有限个臂的多臂老虎机问题,每个臂选择后产生一个 M 维向量奖励,各维度奖励独立生成。每维的目标最优臂是该维度均值最大的臂。目标是在固定置信度下,以最短期望时间识别出所有目标的最优臂。我们建立了问题相关的期望停止时间下限,其由一个计算复杂的极大极小优化问题刻画。提出基于代理比例的新算法,避免在每步求解该优化问题,理论证明其渐近最优,并通过大量实验验证其高效性。现有研究多关注帕累托前沿识别,本工作填补了多目标最优臂识别的空白。
原文摘要 · Abstract (English)
We consider a multi-armed bandit setting with finitely many arms, in which each arm yields an $M$-dimensional vector reward upon selection. We assume that the reward of each dimension (a.k.a. {\em objective}) is generated independently of the others. The best arm of any given objective is the arm with the largest component of mean corresponding to the objective. The end goal is to identify the best arm of {\em every} objective in the shortest (expected) time subject to an upper bound on the probability of error (i.e., fixed-confidence regime). We establish a problem-dependent lower bound on the limiting growth rate of the expected stopping time, in the limit of vanishing error probabilities. This lower bound, we show, is characterised by a max-min optimisation problem that is computationally expensive to solve at each time step. We propose an algorithm that uses the novel idea of {\em surrogate proportions} to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step. We demonstrate theoretically that our algorithm is asymptotically optimal. In addition, we provide extensive empirical studies to substantiate the efficiency of our algorithm. While existing works on pure exploration with multi-objective multi-armed bandits predominantly focus on {\em Pareto frontier identification}, our work fills the gap in the literature by conducting a formal investigation of the multi-objective best arm identification problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。