← 研踪 PaperTrailarXiv:2606.01799 · v2
Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
首次提交 2026-06-01 15:17
版本更新 2026-11-15 18:20
雷达观测 2026-11-17 19:15
摘要
We study -armed stochastic dueling bandits under the Condorcet-winner assumption with a positive global gap, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring transitivity assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. For a fixed global gap , this methodology enables our approach to (1) build the first winner-stays-style algorithm to achieve weak regret; (2) realize the joint optimization of BAI and weak regret with guarantees for both, eliminating the sub-optimal factors of the existing approach; (3) attain the same order as specialized strong-regret approaches; and (4) achieve sample complexity in BAI, matching a worst-case lower bound up to an additional term. If a lower bound on the minimal winner gap is known, this term can be removed. Our results suggest that a single identification primitive can serve BAI and both regret objectives with linear dependence on .
作者备注:Accepted to NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-15 18:20 · 最新观测版本
Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
We study -armed stochastic dueling bandits under the Condorcet-winner assumption with a positive global gap, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring transitivity assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. For a fixed global gap , this methodology enables our approach to (1) build the first winner-stays-style algorithm to achieve weak regret; (2) realize the joint optimization of BAI and weak regret with guarantees for both, eliminating the sub-optimal factors of the existing approach; (3) attain the same order as specialized strong-regret approaches; and (4) achieve sample complexity in BAI, matching a worst-case lower bound up to an additional term. If a lower bound on the minimal winner gap is known, this term can be removed. Our results suggest that a single identification primitive can serve BAI and both regret objectives with linear dependence on .
查看此版本解读 →查看此版本原文 ↗