降低组合半贝叶斯优化的查询次数，提升大规模场景下的效率。
Oracle-Efficient Combinatorial Semi-Bandits
- 设计高效框架，将每轮查询次数从线性降至对数级
- 在最坏情况下实现√T量级的误差累积，仅需log log T次查询
- 适用于高维、非线性奖励的复杂决策场景
我们研究组合半贝叶斯问题，即智能体选择一组基础臂并获得个体反馈。尽管该问题推广了经典多臂赌博机且应用广泛，但其可扩展性受限于组合优化的高昂成本——每轮都需要进行预言机查询。为此，我们提出了预言机高效的框架，显著减少查询次数的同时保持紧致的后悔上界。在最坏情况线性奖励设置下，算法仅需O(log log T)次预言机查询即可达到˜O(√T)的后悔率。我们还提出了利用噪声结构的自适应协方差算法，进一步优化性能，并将方法拓展至一般（非线性）奖励情形。总体而言，我们的方法将预言机使用量从线性降为（双重）对数级，具备强理论保障。
原文摘要 · Abstract (English)
We study the combinatorial semi-bandit problem where an agent selects a subset of base arms and receives individual feedback. While this generalizes the classical multi-armed bandit and has broad applicability, its scalability is limited by the high cost of combinatorial optimization, requiring oracle queries at every round. To tackle this, we propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees. For the worst-case linear reward setting, our algorithms achieve $\tilde{O}(\sqrt{T})$ regret using only $O(\log\log T)$ oracle queries. We also propose covariance-adaptive algorithms that leverage noise structure for improved regret, and extend our approach to general (non-linear) rewards. Overall, our methods reduce oracle usage from linear to (doubly) logarithmic in time, with strong theoretical guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。