arXiv:2606.01799v2 cs.LG

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

Pu Wang, Yao-Xiang Ding

제출 2026-11-17

원문 초록

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 $\Delta$, 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/\Delta)$ 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$.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.01799v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.