提出混合反馈下高效识别最优选项的算法,显著减少试错次数。
Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback
- 结合绝对与相对反馈,构建统一置信区间
- 新算法在95%置信度下停止时间更短
- 适合需要快速决策的高成本场景
我们研究广义线性多臂赌博机中固定置信度下的最优臂识别问题,采用混合反馈模型:每轮可选择单臂的绝对奖励反馈或一对臂的相对(对战)反馈,二者均服从广义线性模型。提出一种基于似然比的置信序,统一处理异质广义线性观测,在自协调假设下生成显式的椭球置信集。基于此置信集,设计了一种混合追踪-停止算法,通过跟踪联合动作空间(单臂与臂对)上的极小极大最优设计,自适应分配查询。证明了δ-正确性,并给出停止时间的高概率上界。进一步扩展至考虑不同反馈模式获取成本差异的成本感知设置。实验表明,所提算法在样本效率上显著优于基线方法。
原文摘要 · Abstract (English)
We study fixed-confidence best arm identification in generalized linear bandits under a hybrid feedback model: at each round, the learner may query either (i) absolute reward feedback from a single arm or (ii) relative (dueling) feedback from an arm pair, both governed by generalized linear models. We introduce a likelihood-ratio--based confidence sequence that unifies heterogeneous generalized linear observations and yields an explicit ellipsoidal confidence set under a self-concordance assumption. Building on this confidence set, we propose a hybrid Track-and-Stop algorithm that adaptively allocates queries by tracking a minimax-optimal design over a joint action space of arms and pairs. We establish $δ$-correctness and provide high-probability upper bounds on the stopping time. We further extend the framework to a cost-aware setting that accounts for heterogeneous acquisition costs across feedback modalities. Empirical experiments demonstrate that the proposed algorithms significantly improve sample efficiency over baseline methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。