Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
复制标题
DOI：
--
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
K. Fujii;Shinsaku Sakaue
中科院分区：
文献类型：
--
作者：
K. Fujii;Shinsaku Sakaue
我们提出了一个名为自适应子模比的新概念来研究顺序决策的贪婪策略。虽然众所周知，贪婪策略在实践中对于各种自适应随机优化问题表现良好，但仅针对有限类别的问题分析了其理论特性。我们通过使用自适应子模比来缩小理论与实践之间的差距，这使我们能够证明贪婪策略对更广泛的问题类别的近似保证。新分析的问题的例子包括自适应影响最大化和自适应特征选择等重要应用。我们的自适应子模块比率还提供了自适应间隙的界限。实验证实，与标准启发式方法相比，贪婪策略在所考虑的应用程序中表现良好。
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of problems. We narrow the gap between theory and practice by using adaptive submodularity ratio, which enables us to prove approximation guarantees of the greedy policy for a substantially wider class of problems. Examples of newly analyzed problems include important applications such as adaptive influence maximization and adaptive feature selection. Our adaptive submodularity ratio also provides bounds of adaptivity gaps. Experiments confirm that the greedy policy performs well with the applications being considered compared to standard heuristics.