首个统一解决优胜者选择与损失最小化的强化学习框架。
Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
- 用树形结构高效筛选出最优选项，仅需O(N)次比较。
- 在无需强假设下实现最优样本复杂度和弱损失控制。
- 适合需要快速收敛与稳定性能的推荐系统研究者。
我们研究在Condorcet优胜者假设下的N臂随机对抗性强化学习问题，考虑三种主流目标：最优臂识别（BAI）、弱遗憾（weak regret）和强遗憾（strong regret）。本文提出树引导的识别-利用框架（TG-ITE），是首个统一处理三类目标的方法。通过共享的树形引导识别机制，在无需更强假设的前提下，仅用O(N)次比较即可获得高置信度候选解。进一步设计不同利用策略以优化具体目标。该方法实现了：(1) 在无额外假设下达成O(N)样本复杂度的BAI；(2) 构建首个“胜者留任”式算法，实现O(N)弱遗憾；(3) 保持与专用强遗憾方法相同的O(N log T)保证；(4) 首次实现BAI与弱遗憾的联合优化，两者均达到O(N)保障，消除现有方法中因子优化导致的O(log N)差距。结果表明，对抗性带宽中BAI与遗憾最小化之间的权衡较轻微。
原文摘要 · Abstract (English)
We study $N$-armed stochastic dueling bandits under the Condorcet-winner assumption, 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 stronger 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. This methodology enables our approach to (1) achieve $O(N)$ sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve $O(N)$ weak regret; (3) enjoy the same $O(N \log T)$ guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with $O(N)$ guarantees for both, eliminating the sub-optimal gap of $O(\log N)$ in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。