Near-optimal bayesian active learning for decision making

How should we gather information to make ef-fective decisions? We address Bayesian active learning and experimental design problems, where we sequentially select tests to reduce uncertainty about a set of hypotheses. Instead ofminimizing uncertainty per se, we consider a set of overlapping decision regions of these hy-potheses. Our goal is to drive uncertainty into a single decision region as quickly as possible. We identify necessary and sufficient condi-tions for correctly identifying a decision region that contains all hypotheses consistent with observations. We develop a novel Hyperedge Cutting (HEC) algorithm for this problem, and prove that is competitive with the in-tractable optimal policy. Our efficient imple-mentation of the algorithm relies on comput-ing subsets of the complete homogeneous sym-metric polynomials. Finally, we demonstrate its effectiveness on two practical applications: approximate comparison-based learning and active localization using a robotmanipulator.