Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this paper, we introduce the concept of adaptive submodularity, generalizing submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy. We illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse applications including sensor placement, viral marketing and pool-based active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases and leads to natural generalizations.

@inproceedings{golovin10adaptive,
	author = {Daniel Golovin and Andreas Krause},
	booktitle = {Proc. Conference on Learning Theory (COLT)},
	title = {Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization},
	year = {2010}}