트리 가이드 기반 Identify-Then-Exploit: Dueling Bandits를 위한 최적 팔 식별(BAI) 및 후회

우리는 Condorcet-winner 가설 하에서의 $N$-arm 확률적 dueling bandits (dueling bandits)를 연구하며, 널리 채택되는 세 가지 목적 함수인 최적 팔 식별 (best-arm identification, BAI), 약한 후회 (weak regret), 그리고 강한 후회 (strong regret)를 고려합니다. 우리는 우리가 아는 한 이러한 모든 목적을 다루는 최초의 통합 프레임워크인 Tree-Guided Identify-Then-Exploit (TG-ITE)를 제안합니다. 더 강력한 가설을 요구하지 않고도, 우리는 $O(N)$ 번의 비교 내에 높은 신뢰도의 incumbent (기존 우승자)를 찾기 위한 공유된 트리 가이드 식별 (tree-guided identification) 접근 방식을 제안합니다. 나아가, 우리는 이 warm-start 단계(초기 구동 단계)를 활용하여 당면한 특정 목적 함수들을 최적화하기 위한 다양한 exploitation (활용) 전략을 제안합니다. 이 방법론을 통해 우리의 접근 방식은 (1) 일반적으로 채택되는 더 강력한 가설 없이도 BAI에서 $O(N)$의 sample complexity (샘플 복잡도)를 달성하고, (2) $O(N)$의 약한 후회를 달성하는 최초의 winner-stays-style 알고리즘을 구축하며, (3) 특화된 strong-regret 접근 방식과 동일한 $O(N ext{ } ext{log} ext{ } T)$ 보장을 누리고, (4) 기존 방식의 $O( ext{log} ext{ } N)$의 sub-optimal (차선책) 격차를 제거하면서 두 목적 모두에 대해 $O(N)$ 보장을 갖는 BAI와 약한 후회의 공동 최적화를 실현합니다. 우리의 결과는 dueling bandits에서 BAI와 regret minimization (후회 최소화) 사이의 trade-off (절충 관계)가 상대적으로 양호하다는 증거를 제공합니다.