提出新算法实现非单调子模函数在线优化的对数级后悔，优于现有方法。
Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit
- 设计双贪婪探索-承诺策略，结合探索与利用
- 在特定条件下达到O(d log(dT))对数后悔上界
- 适合需要高精度在线决策的场景，如推荐系统
研究在线无约束子模最大化问题（Online USM），在随机老虎机反馈设置下，决策者从定义在已知有界区间上的非单调子模函数中获得噪声奖励。本文提出双贪婪-探索-承诺（DG-ETC）算法，该算法源自离线与全信息在线场景中的双贪婪方法。该算法同时满足1/2近似伪后悔的O(d log(dT))问题相关上界和O(d T^{2/3} log(dT)^{1/3})问题无关上界，优于现有方法。特别地，引入了一个问题相关的困难度量，刻画了上界从对数到多项式转变的临界点。
原文摘要 · Abstract (English)
We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit feedback. In this framework, a decision-maker receives noisy rewards from a non monotone submodular function taking values in a known bounded interval. This paper proposes Double-Greedy - Explore-then-Commit (DG-ETC), adapting the Double-Greedy approach from the offline and online full-information settings. DG-ETC satisfies a $O(d\log(dT))$ problem-dependent upper bound for the $1/2$-approximate pseudo-regret, as well as a $O(dT^{2/3}\log(dT)^{1/3})$ problem-free one at the same time, outperforming existing approaches. In particular, we introduce a problem-dependent notion of hardness characterizing the transition between logarithmic and polynomial regime for the upper bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。