Carnegie Mellon University
The
Submodular Surrogates for Value of Information

Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew (Drew) Bagnell, Siddhartha Srinivasa, and Andreas Krause
The Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15), January, 2015.


Download
  • Adobe portable document format (pdf) (3MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
How should we gather information to make effective decisions? A classical answer to this fundamental problem is given by the decision-theoretic value of information. Unfortunately, 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 information. 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 latter property enables us to utilize an efficient greedy optimization while providing strong approximation guarantees. We demonstrate the utility of our approach on four diverse case-studies: touch-based robotic localization, comparison-based preference learning, wild-life conservation management, and preference elicitation in behavioral economics. In the first application, we demonstrate DIRECT in closed-loop on an actual robotic platform.

Keywords
Sequential Decision Making, Value of Information, Adaptive Submodularity, Decision Region Determination, Touch-based Localizatoin

Notes

Text Reference
Yuxin Chen, Shervin Javdani, Amin Karbasi, J. Andrew (Drew) Bagnell, Siddhartha Srinivasa, and Andreas Krause, "Submodular Surrogates for Value of Information," The Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15), January, 2015.

BibTeX Reference
@inproceedings{Javdani_2015_7811,
   author = "Yuxin Chen and Shervin Javdani and Amin Karbasi and J. Andrew (Drew) Bagnell and Siddhartha Srinivasa and Andreas Krause",
   title = "Submodular Surrogates for Value of Information",
   booktitle = "The Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI-15)",
   month = "January",
   year = "2015",
}