How should we gather information to make effective deci- sions? A classical answer to this fundamental problem is given by the decision-theoretic value of information. Unfor- tunately, optimizing this objective is intractable, and myopic (greedy) approximations are known to perform poorly. In this paper, we introduce DIRECT, an efficient yet near-optimal algorithm for nonmyopically optimizing value of informa- tion. Crucially, DIRECT uses a novel surrogate objective that is (1) aligned with the value of information problem; (2) efficient to evaluate and (3) adaptive submodular. This lat- ter property enables us to utilize efficient greedy optimiza- tion while providing strong approximation guarantees. We extensively demonstrate the utility of our approach on three diverse case-studies: active learning for interactive content search, optimizing value of information in conservation man- agement, and touch-based robotic localization. On the latter application, we demonstrate DIRECT in closed-loop on an actual robotic platform.

@inproceedings{chen15submodular,
	author = {Yuxin Chen and Shervin Javdani and Amin Karbasi and James Andrew Bagnell and Siddhartha Srinivasa and Andreas Krause},
	booktitle = {Proc. Conference on Artificial Intelligence (AAAI)},
	month = {January},
	title = {Submodular Surrogates for Value of Information},
	year = {2015}}