Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality = 디커플드 밴딧에서의 이론적 강건성과 실용성

국문 초록 (Abstract)

본 연구에서는 탐색과 활용을 분리하여 수행하는 디커플드 멀티암드 밴딧(Decoupled Multi-Armed Bandit) 문제를 다룬다. 학습자는 각 라운드마다 탐색을 위해 선택한 팔의 손실을 관찰할 수 있으나, 해당 손실은 누적 손실에 포함되지 않는다. 반면, 활용을 위해 선택한 팔에서는 손실이 발생하지만, 학습자는 그 값을 관찰할 수 없다. 이러한 설정 하에서, 본 연구는 Pareto 분포 기반의 Follow-the-Perturbed-Leader(FTPL) 정책을 새롭게 제안한다. 제안된 정책은 환경의 유형에 관계없이 최적 수준의 후회(regret)를 보장하는 Best-of-Both-Worlds(BOBW) 특성을 갖는다. 구체적으로, 확률적 환경에서는 표준 멀티암드 밴딧 정책 대비 개선된 상수 수준의 후회를, 적대적 환경에서는 미니맥스 최적(minimax-optimal) 후회를 보장한다. 제안하는 방법의 핵심은 기존의 BOBW 정책에서 요구되던 컨벡스 최적화 과정과, FTPL 계열 연구에서 일반적으로 필요로 하던 재샘플링(resampling) 단계를 모두 제거했다는 점이다. 실험 결과, 제안된 정책은 계산 효율성을 크게 개선했을 뿐만 아니라, 확률적·적대적 환경 모두에서 기존 정책 대비 우수한 성능을 입증하였다.

다국어 초록 (Multilingual Abstract)

We study the decoupled multi-armed bandit problem, where the learner selects one arm for exploration and one arm for exploitation separately at each round. In this setting, the loss of the explored arm is observed but not incurred, whereas the loss of the exploited arm is incurred without being observed. We propose an efficient Follow-the-Perturbed-Leader (FTPL) policy that achieves Best-of-Both-Worlds (BOBW) guarantees with constant regret in the stochastic regime and minimax optimal regret in the adversarial regime. A key feature of our method is that it completely avoids both the convex optimization required by prior BOBW policy, and the resampling procedures that are typically used in FTPL bandit policies. This allows FTPL to fully realize its computational efficiency advantages, and thus leads to substantial reductions in computational cost. We empirically confirm that our policy not only improves the runtime but also demonstrates superior regret performance in both regimes.

목차 (Table of Contents)

• 1. Introduction 1
• 1.1. Contributions 3
• 2. Preliminaries 5
• 2.1. Notation 5
• 2.2. Problem setting 5
• 2.3. Previous approaches in decoupled bandits 6
• 3. FTPL for decoupled bandits 8
• 3.1. Technical challenges 8
• 3.2. Proposed policy 9
• 3.3. Regret analysis 10
• 3.4. Proof sketch of the regret in the SCA regime 11
• 4. Numerical experiments 15
• 4.1. Adversarial regime 15
• 4.2. Stochastic regime 16
• 5. Conclusion 18
• Bibliography 19
• A. Omitted Proofs for Lemmas 22
• A.1. Proof for the regret decomposition 22
• A.2. Proof for the stability term 25
• A.3. Proof for the penalty term 27
• B. Regret bound for adversarial bandits (Theorem 1) 29
• C. Regret bound for stochastic bandits (Theorem 2) 31
• D. Auxiliary lemmas 40
• E. Additional experiments 46
• E.1. Implementation details 46
• E.2. Adversarial regime 46
• 초록 48
• Acknowledgements 49