How should we gather information to make effective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead of minimizing uncertainty per se, we consider a set of overlapping decision regions of these hypotheses. Our goal is to drive all remaining uncertainty into a single decision region as quickly as possible. This model captures many natural settings where uncertainty needs to be reduced in a structured way. We identify necessary and sucient conditions for correctly identifying a decision region that contains all the hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the intractable optimal policy. Our efficient implementation of the algorithm relies on computing subsets of the complete homogeneous symmetric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based search and active localization using a robot manipulator.

@inproceedings{javdani14near,
	author = {Shervin Javdani and Yuxin Chen and Amin Karbasi and Andreas Krause and James Andrew Bagnell and Siddhartha Srinivasa},
	booktitle = {In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS)},
	month = {April},
	title = {Near-Optimal Bayesian Active Learning for Decision Making},
	year = {2014}}