利用单调性结构，大幅降低组合多集带宽学习的计算开销。
Efficient Matroid Bandit Linear Optimization Leveraging Unimodality
- 发现并利用多集带宽问题的单调结构，减少查询次数。
- 在近似最优损失下，查询次数降至 $\mathcal{O}(\log \log T)$。
- 适合大规模或查询昂贵的场景，如在线推荐多样性保障。
我们研究了在多集约束下的组合半带宽问题。尽管近期方法已达到最优遗憾率（regret），但在大型多集或成员检测代价高昂的场景（如需多样性的在线推荐）中，时间复杂度仍存在挑战。本文通过揭示该问题内在的单峰结构，提出新方法：在遗憾率几乎不变的前提下，将成员检测预言机的调用次数限制在 $\mathcal{O}(\log \log T)$。实验在多个多集基准上验证了：(i) 与最先进方法相比，遗憾率无损失；(ii) 显著降低时间复杂度和预言机调用次数。
原文摘要 · Abstract (English)
We study the combinatorial semi-bandit problem under matroid constraints. The regret achieved by recent approaches is optimal, in the sense that it matches the lower bound. Yet, time complexity remains an issue for large matroids or for matroids with costly membership oracles (e.g. online recommendation that ensures diversity). This paper sheds a new light on the matroid semi-bandit problem by exploiting its underlying unimodal structure. We demonstrate that, with negligible loss in regret, the number of iterations involving the membership oracle can be limited to \mathcal{O}(\log \log T)$. This results in an overall improved time complexity of the learning process. Experiments conducted on various matroid benchmarks show (i) no loss in regret compared to state-of-the-art approaches; and (ii) reduced time complexity and number of calls to the membership oracle.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。