Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
Pu Wang, Yao-Xiang Ding
原文摘要
We study $N$-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)$ 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)$ weak regret; (2) realize the joint optimization of BAI and weak regret with $O(N)$ guarantees for both, eliminating the sub-optimal $O(\log N)$ factors of the existing approach; (3) attain the same $O(N\log T)$ order as specialized strong-regret approaches; and (4) achieve $O(N)$ sample complexity in BAI, matching a worst-case lower bound up to an additional $\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 $N$.
cs.LG · stat.ML