提出新型组合强化学习算法，解决多臂选择中探索不足问题。
Optimal Arm Elimination Algorithms for Combinatorial Bandits
- 将臂分为确认、活跃和淘汰三类，显式设计探索机制
- 在图反馈与线性上下文场景下实现近似最优后悔值
- 适用于推荐系统等需高效多选的场景
组合多臂赌博机将经典赌博机框架扩展到每轮选择多个臂的场景，应用于在线推荐和商品组合优化。尽管上置信界（UCB）算法可自然推广，但臂消除方法的适配更具挑战性。本文提出一种新型消除方案，将臂划分为三类（确认、活跃、淘汰），并通过显式探索更新集合。在组合多臂赌博机（一般图反馈）和组合线性上下文赌博机两种场景中，本方法均实现近似最优后悔率；而基于UCB的方法因缺乏显式探索，可能在理论上失败。同时提供了匹配的下界。
原文摘要 · Abstract (English)
Combinatorial bandits extend the classical bandit framework to settings where the learner selects multiple arms in each round, motivated by applications such as online recommendation and assortment optimization. While extensions of upper confidence bound (UCB) algorithms arise naturally in this context, adapting arm elimination methods has proved more challenging. We introduce a novel elimination scheme that partitions arms into three categories (confirmed, active, and eliminated), and incorporates explicit exploration to update these sets. We demonstrate the efficacy of our algorithm in two settings: the combinatorial multi-armed bandit with general graph feedback, and the combinatorial linear contextual bandit. In both cases, our approach achieves near-optimal regret, whereas UCB-based methods can provably fail due to insufficient explicit exploration. Matching lower bounds are also provided.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。