跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

We study NN-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 O(N)O(N) 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 O(N)O(N) weak regret; (2) realize the joint optimization of BAI and weak regret with O(N)O(N) guarantees for both, eliminating the sub-optimal O(log⁡N)O(\log N) factors of the existing approach; (3) attain the same O(Nlog⁡T)O(N\log T) order as specialized strong-regret approaches; and (4) achieve O(N)O(N) sample complexity in BAI, matching a worst-case lower bound up to an additional log⁡(1/Δ)\log(1/Δ) 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 NN.

作者备注:Accepted to NeurIPS 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 NN-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 O(N)O(N) 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 O(N)O(N) weak regret; (2) realize the joint optimization of BAI and weak regret with O(N)O(N) guarantees for both, eliminating the sub-optimal O(log⁡N)O(\log N) factors of the existing approach; (3) attain the same O(Nlog⁡T)O(N\log T) order as specialized strong-regret approaches; and (4) achieve O(N)O(N) sample complexity in BAI, matching a worst-case lower bound up to an additional log⁡(1/Δ)\log(1/Δ) 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 NN.

查看此版本解读 →查看此版本原文 ↗