Diagnose and Decide: An Optimal Bayesian Approach
Christopher Amato, Emma Brunskill · 2012
Many real-world scenarios require making informed choices after some sequence of actions that yield noisy information about a latent state. Prior research has mostly focused on generic methods that struggle to scale to large domains. We focus on a subclass with two particular characteristics. First, once performed, an information gathering action (or test) will always yield the same result. This means it is sufficient to perform each test once. Second, we assume that test costs can be expressed in the same units as costs of the final decisions made. We call such scenarios diagnose-and-decide problems. We prove diagnose-and-decide problems are a special subclass of POMDPs for which the optimal policy can be computed in time polynomial in the number of possible test outcomes. We use a simple algorithm that takes advantage of the problem structure, and show our approach can equal or outperform a state-of-the-art POMDP planner. We demonstrate this perfor-mance on two simulations based on real-world data (colon cancer screening and object recognition) as well as a large synthetic domain. Consider a doctor who may run diagnostic tests before treating a patient, or an autonomous surveillance helicopter that may fly closer to a target to get a better view before raising a security alert, or a drug discovery problem where a drug