Near-optimal Adaptive Information Acquisition: Theory and Applications

Abstract

Many problems in artificial intelligence require adaptively making a sequence of decisions, each based on the information obtained so far.As an example, consider interactive troubleshooting, where one can perform many tests on the system in question, and the goal is to adaptively conduct a small set of tests that are sufficient for making the correct diagnosis.Another example is active perception in robotics, where the goal is to localize a certain object by exploring the environment via some sensing actions, such as touch or vision.Understanding how to effectively acquire information under partial observability is fundamental for developing intelligent adaptive systems.Unfortunately, most of the existing techniques for solving such problems are either simple heuristics which do not strive for optimality or principled non-myopic approaches that are difficult to scale to larger problems.To ease the tension between theory and practice, this dissertation pursues the fundamentals of adaptive information acquisition, with the goal to devise a mathematical and algorithmic framework for efficient (in terms of computational complexity) and robust (in terms of decision quality and noise-tolerance) decision making under uncertainty.From the theoretical perspective, we look into different problem settings, where it is challenging to characterize the value of information due to complex constraints and modeling assumptions, such as indirect information, uncertain inputs, delayed feedback in parallel systems, and incomplete knowledge about the model.We provide new theoretical insights and develop novel algorithms for solving such problems.From the practical perspective, we demonstrate strong empirical performance for our proposed algorithms on a number of problem instances, including Bayesian experimental design for behavioral economics, interactive troubleshooting, active preference learning, active touch-based localization, and active object detection for biodiversity monitoring.More specifically, in Part II of this dissertation, we investigate sequential algorithms i which aim to optimize the value of information.We first look into a basic variant of the adaptive information acquisition problem, where the goal is to learn the value of some target random variable through a sequence of conditionally independent, possibly noisy tests.Here, the value of information is defined in terms of the informativeness of the tests performed, measured by Shannon's mutual information.We provide the first rigorous analysis of the greedy algorithm that holds under the persistent noise setting.In most practical applications, collecting information is not the goal of its own, but rather a means for making informed decisions.We further investigate novel, efficient objectives for such problems which are amenable to greedy optimization.In particular, we propose novel surrogate objectives that are: (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.Our algorithms achieve the state-of-the-art performance on a few problem instances including a real-world robotic manipulation task.Moving beyond the previous settings, we seek to generalize our theoretical insight of constructing submodular surrogates for solving more general sequential decision problems.We propose a principled approach to active object detection and show that for a rich class of base detection algorithms, one can derive a natural sequential decision problem for deciding when to invoke expert supervision.We demonstrate the effectiveness of our algorithm on several object detection problems.Part III of this dissertation aims to address some practical challenges of the adaptive information acquisition problem.For instance, in many practical scenarios, fully sequential selection could be infeasible.We study information-parallel l