Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy\n with Adaptive Submodularity Ratio

We propose a new concept named adaptive submodularity ratio to study the\ngreedy policy for sequential decision making. While the greedy policy is known\nto perform well for a wide variety of adaptive stochastic optimization problems\nin practice, its theoretical properties have been analyzed only for a limited\nclass of problems. We narrow the gap between theory and practice by using\nadaptive submodularity ratio, which enables us to prove approximation\nguarantees of the greedy policy for a substantially wider class of problems.\nExamples of newly analyzed problems include important applications such as\nadaptive influence maximization and adaptive feature selection. Our adaptive\nsubmodularity ratio also provides bounds of adaptivity gaps. Experiments\nconfirm that the greedy policy performs well with the applications being\nconsidered compared to standard heuristics.\n