Diagnose and Decide: An Optimal Bayesian Approach

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 diagnoseand-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 performance 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 can be tested in various ways before deciding whether or not to develop and market it. These are all instances where there exists some hidden state that affects the quality of a resulting decision, and a decision maker has the opportunity run some, potentially costly, information-gathering operations before making that decision. In the above three cases, and many others, the results of the information-gathering operations will not change when they are repeated due to some underlying bias. In addition, we are interested in when the cost of the information-gathering operations is directly comparable to the cost of the final decision made, such as the time to raise an alert, or the financial cost of testing and then producing a drug. We call these problems diagnose-and-decide (DAD) problems. In this paper we focus on computing optimal conditional policies for DAD problems that specify what information-gathering operations to perform, and what final decision to make, in order to minimize the expected total cost. We show the special structure of DADs allows them to fall in a lower complexity class than generic partially observable Markov decision processes (POMDPs). We present a branch and bound approach to solving DADs, and show, somewhat surprisingly, that our approach achieves similar or better performance than POMCP [10], a state-of-the-art approximate POMDP solver, for the domains tried. Unlike POMCP, our approach also provides anytime bounds on the resulting performance. 1 Diagnose and decide model We denote a diagnose-and-decide (DAD) model as a tuple consisting of the following components: • Actions: AT × AD. AT is the set of possible tests (|AT | = T ). Each test can only be performed once. AD (|AD| = D) is the set of possible final decisions. • States: ST × SC , sD. ST is a vector representing the outcome (or not yet been taken status) of each test. ST is fully observable. SC (|SC | = Y ) is a finite set of classes with the underlying class hidden. sD is an absorbing terminal state.