Reflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study

1 Reflection and Flexibility

Reflection about the course of problem solving and about the interleaving of problem solving and physical activity is a hallmark of intelligent behavior. Applying a portion of available reasoning resources to consider the utility of alternative inference strategies or the value of continuing to refine a result before acting enables a computational agent to generate custom-tailored approaches to a wide variety of problems, under different time pressures. Such flexibility can be especially useful in light of uncertain deadlines and challenges. Uncertainty about problems and problem solving plagues simple agents immersed in complex environments . Constraints on an agent's rea­ soning and representation resources lead to inescapable uncertainties about the problems that may be faced and about the value offuture reasoning in solving those prob­ lems.

The Protos project has pursued the use of deci­ sion theory for real-time control and offiine problemsolving design. The work has highlighted opportunities for the principled control of reasoning under scarce re­ sources with problems in sorting and searching and with decision-theoretic inference itself [Horvitz, 1987a]. We have particularly dwelled on the decision-theoretic con­ trol of decision-theoretic inference as a model of rational computational inference under resource constraints. In this paper, we present a component of this work cen­ tering on the use of incomplete characterizations of the progression of probabilistic inference to reason about the value of continuing to reflect about a problem versus tak­ ing action in the world. This methodology uses knowl­ edge that partially characterizes relevant dimensions of problem-solving performance. Such knowledge can be learned and refined with experience. We shall introduce components of utility for computational or real-world actions, and define the expected value of computation in terms of the likelihood of future probability distribu­ tions over the truth of relevant propositions about the state of the world. After discussing the theoretical prin­ ciples and empirical results, we describe a component of research centering on the offiine analysis of problem­ solving trajectories. Such offiine musing, weighted by expected challenges, can be important in real-time re­ flection about problem solving.

·This work was supported by a NASA Fellowship under Grant NCC-220-51, by the National Science Foundation un­ der Grant IRI-8703710, by the National Library of Medicine under Grant ROILM0429, and by the U.S. Army Research Office under Grant P-25514-EL. Computing facilities were provided by the SUMEX-AIM Resource under NIH Grant RR-00785.

2 Decision-Theoretic Valuation

Decision theory provides the foundations for a princi­ pled approach to metalevel decision making under un­ certainty. Decision-theoretic metareasoning can be es­ pecially useful in reasoning about the selection, and op­ timal halting time, of reasoning strategies that incre­ mentally refine results as scarce resources are expended [Horvitz, 1987b, Dean and Boddy, 1988].

We use comprehensive value, uc, to refer to the util­ ity associated with the value attributed to the state of an agent in the world. This value is a function of the problem at hand, of the agent's best default action, and of the stakes of a decision problem. We call the net change expected in the comprehensive value, in return for some allocation of computational resource, the ex­ pected value of computation (EVC). It is often useful to view the comprehensive utility, at any point in the reasoning process, as a function of two components of utility: the object-level utility, u 0 , and the inferencerelated cost, u;. 1 The object-level utility of a strategy is the expected utility associated with a computer re­ sult or state of the world. We say that the object-level utility is a function of a vector of attributes, v. For example we may assign an object-level utility to an in­ completely sorted file of records, based on several differ­ ent dimensions of incompleteness. The inference-related component is the sum of the expected disutility intrin­ sically associated with, or required by, the process of problem solving. This cost can include the disutility of delaying an action while waiting for a reasoner to infer a recommendation. In general, the inference-related cost is a function of a vector of resource attributes, r, rep­ resenting the quantity that has been expended of such commodities as time and memory.

There is generally uncertainty in the object-level state resulting from the expenditure of computational re­ sources. Thus, in the generar case, we must sum over a probability distribution of object-level attributes to generate an expected comprehensive utility. If v and rare the vectors representing object-level and inference­ related attributes without additional computation, re­ spectively, and the v 1 and r 1 are the revised vectors, ex­ pected with additional computation, the net , or change in, comprehensive utility, given some allocation of re­ sources IS

In cases where the inference-related and object-level util­ ities can be decomposed, and are related through addi­ tion, the EVC is just the difference between the increase in object-level utility and the cost of the additional com­ putation,

In another study, we considered the refinement of multi­ dimensional attributes of partial results with computa­ tion [Horvitz, 1988] . Here, we will simplify our object­ level focus to a probability of a state in the world, H, and the quality of an associated decision to act, A, given uncertainty about the truth of the state. We will sim­ plify the inference-related component to a consideration of computation time.

The decision-theoretic approach to metareasoning in difficult machine intelligence problems was introduced by I.J . Good over 2 decades ago, in the context of the control of game-playing search [Good, 1968]. Good had earlier discussed the explicit integration of the costs of inference within the framework of normative rationality, defining Type I rationality as inference that is consistent with the axioms of decision theory, regardless of the cost of inference, and Type II rationality as behavior that takes into consideration the costs of reasoning [Good, 1952] . Related work in decision science has focused on the likely benefit of expending effort for decision analyses [Matheson, 1968, Watson and Brown, 1978] . Our group researched the general applicability of decision-theoretic control of computation, with an emphasis on metarea­ soning problems with probabilistic inference and knowl­ edge representation [Horvitz, 1987b]. Early investiga­ tion demonstrated that multiattribute decision-theoretic control of reasoning had promise for guiding the so­ lution of a variety of tasks, including such fundamen­ tal problems as sorting a file of records or search­ ing a large tree of possibilities [Horvitz, 1987a]. In­ deed, there have been recent studies of the value of computation in the control of sorting [Horvitz, 1988] and of game-playing search [Russell and Wefald, 1988, Hansson and Mayer, 1989]. In related research on the control of logical inference, Smith, and Treitel and Gene­ sereth, have explored the use of decision theory for select­ ing alternative logical reasoning strategies [Smith, 1986, Treitel and Genesereth, 1986].

1 More comprehensive notions of the value of a reasoning system in an environment are discussed in (Horvitz, 1987b).

3 Complexity of Inference

In reasoning about real-world actions under uncertainty, an agent generally must consider alternative decisions and outcomes, preferences about the possible outcomes, and the uncertain relationships among actions and out­ comes. We have been investigating the use of influ­ ence diagrams [Howard and Matheson, 1981] for repre­ senting and solving automated reasoning problems. The influence diagram is an acyclic directed graph containing nodes representing propositions and arcs representing in­ teractions between the nodes. Nodes represent a set of mutually exclusive and exhaustive states; arcs capture probabilistic relationships between the nodes. Influence diagrams without preference or decision information are termed belief networks. A belief network defines a model for doing probabilistic inference in response to changes in information.

The problem of probabilistic inference with belief net­ works is NP-hard [Cooper, 1987]. Thus, we can expect algorithms for doing inference to have a worst-case time complexity that is exponential in the size of the problem (e.g., the number of hypotheses and pieces of evidence) . Some methods for inference in belief networks attempt to dodge intractability by exploiting independence re­ lations to avoid the explicit calculation of the joint­ probability distribution. A variety of exact methods has been developed, each designed to operate on particu­ lar topologies of belief networks [Horvitz et al., 1988a] . Other methods forego exact calculation of probabilities; these approximation techniques produce partial results as distributions or bounds over probabilities of interest . The complexity of precise inference and the availability of alternative reasoning approaches highlight the need for robust approximation strategies and intelligent con­ trol techniques. We have sought to develop and con­ trol decision-theoretic inference for reasoning under un­ certainty in high-stakes and time-pressured applications , ·such as medical decision making.

4 Decisions Under Scarce Resources

Let us explore concerns that arise in automated decision making under scarce resources . The graph in the lower portion of Figure 1 depicts an object-level influence­ diagram representation of a time-pressured problem that might face an automated physician's assistant: A 75year-old woman in the intensive-care unit suddenly shows signs of breathing difficulty. The patient may be merely showing signs of mild respiratory distress or may be in the more serious situation of respiratory failure. In this context, the primary decision is whether or not to recommend that the patient be placed on a mechanical ventilator. The decision (square node) depends on the probability ofrespiratory failure, which, in turn, depends on the probabilities of propositions in a large belief net­ work serving as a medical knowledge base (represented by the graph above the object-level problem in Figure 1). The large oval nodes in the base decision problem rep­ resent uncertain states associated with placing an older person on a ventilator . The diamond represents the util­ ity associated with different outcomes. Factors to con­ sider in a decision to act include the possibility that it may take a long time to wean a patient with severe lung disease from a ventilator that is applied needlessly; thus, the patient may face a long hospital stay and be placed at high risk of mortality from a disease such as pneumo­ nia. However, if the patient turns out to be in respira­ tory failure, and is not treated immediately, she faces a high risk of cardiac arrest based on the disrupted phys­ iology associated with abnormal blood levels of oxygen and carbon dioxide.

4.1 Actions and Outcomes in the World

In our simple example, there are only four different fun­ damental outcomes. The patient either is in respiratory failure (H) or is not in respiratory failure (..,H), and we either will place the patient on a ventilator (A) or will not do so (..,A). Thus, we may erroneously decide not to treat a patient who is suffering from respiratory fail­ ure (..,A, H), we may correctly treat a patient who is suffering from respiratory failure (A, H), we may erro­ neously treat a patient who is not suffering from respira­ tory failure (A, -,H), or we may correctly forego treating a patient who is not suffering from respiratory failure (..,A, -,H). The expected object-level utilities of action [u(A)] and of no action [u( -,A)] in terms of the proba­ bility of respiratory failure, p(H), are described by the following equations:

The lines described by these equations intersect at a probability of H denoted p*. The desired action (the decision with the highest expected utility) changes as the utility lines cross at p* . A utility analysis dictates that a patient should not be treated unless a decision maker's belief in the truth of H is greater than p*.

4.2 Decisions About Computation

Let us now integrate explicit knowledge about the pro­ cess of reasoning into the decision problem. In answer to a query for assistance, our automated reasoner must propagate observed evidence about the patient's symp­ tomology through a complex belief network. The results of an approximate probabilistic-inference scheme may be a probability distribution over a final probability. This probability is the value that a computer will calculate from a belief network, given sufficient time to finish its computation. Assume that our reasoner may apply one of several incremental-refinement algorithms that can it­ eratively tighten the distribution on the probability of interest over time. We wish the system to make a ratio­ nal decision about whether to make a treatment recom­ mendation immediately, or to defer its recommendation and continue to reason, given its knowledge about the costs of time needed for computation.

4.2.1 Costs of Inference-Based Delay

The example of a patient gasping for breath, facing the risk of a long hospitalization or a cardiac arrest depend­ ing on our decision, poignantly demonstrates the salience of reasoning-resource constraints in a high-stakes situa­ tion. So far, we have considered the utilities of alter­ native outcomes to be independent of time. Assume that the utility of treating a patient in respiratory fail­ ure depends on how long the patient has been in failure . Assume, also, that the initial presentation of respira­ tory symptoms oc.curs in the presence of the reasoner and that analysis of the problem begins at this time, t0 . We represent the cost of delaying treatment, when that treatment is needed, by considering a continuum of mutually exclusive decisions to treat at different times, A(t), where t = to + L:it. A cost function can capture the decay of utility of action with time. At some time t, the utility of acting in the presence of respiratory failure reverts to the utility of not acting at all. We substitute the static utility equation for u(A), defined previously, with a time-dependant equation:

where u[A(t), H] reverts to u(·A, H) as some function of time 2 · In this example, we assume that delay of action will not affect the utility of a patient that does not re­ quire the intervention. With the time-dependent utility function, our p· threshold will change with time.

As indicated by the network in the upper portion Fig­ ure 1, a more complete representation of the respiratory decision problem includes knowledge about the costs and benefits of applying different inference strategies. This influence diagram represents the metareasoning prob­ lem. The node labeled U 0 in the metareasoning network is just the value node from the object-level decision prob­ lem represented at the bottom of Figure 1. Rather than seek to optimize the object-level value, our agent's goal is to optimize the utility associated with the value node in the metareasoning problem, labeled Uc. As demon­ strated by the relationships among propositions in the metareasoning problem, Uc is a function of the object­ level value and the inference-related cost, U;, which in turn depends on computational delay, time availability, and the context. The integration of inference-related and object-level utility allows agents to treat decisions and outcomes regarding the control of reasoning just as it does decisions about action in the world.

4.2.2 Reflection About Future Belief

Our agent's attention is centered on the calculation of p(H), the probability of respiratory failure. We define </> to be the probability that the agent would compute if it had sufficient time to finish its computation. That is, </> is value of p(H) that the reasoner will report after com­ plete computation. At the present moment-before the inference is completed--our automated reasoner may be uncertain about what the value of</> will be. The current uncertainty is described by some probability distribution over¢. We denote the uncertainty about </> at the present moment by p(¢). Although this distribution can change with reasoning, investigators [Howard, 1970] have shown that the belief a decision maker should use for decision making, if she has to act immediately, is the mean of p( </>), denoted by < </> >. After spending additional time t on inference about </>, our reasoner may have a new distribution over</>, denoted by p1(</>).

An automated reasoner may have useful knowledge about how a distribution over a belief-and thus how the new mean of the distribution-will change with ad­ ditional computing. An important class of knowledge about </> is of the form, p(p1 ( </>)). This measure refers to belief at the present time about the likelihood of alterna­ tive belief distributions over </> that might be generated after computation for additional time t. This notion is central in reflection about the value of initiating or con­ tinuing decision-theoretic inference, as opposed to that of acting with the current best decision.

2 In this domain, we could capture the cost of delay with a stochastic model describing the probability of a cardiac arrest as a function of the time we delay therapy; cost models can be useful summaries of the utility of a large number of outcomes.

Expected Value of Perfect Computation Suppose that, after thinking for only a few milliseconds, an auto­ mated reasoner has generated a probability distribution over </> . We first introduce the expected value of perfect computation on </>, denoted by EV PCI/>. The EVPCI/> may be viewed as the value of instantaneous complete computation of the target probability in a decision set­ ting. Instantaneous complete thinking would collapse the current probability distribution over </> into an im­ pulse. Given the current probability distribution p( </>) over</>, we define EV PC I/> as follows:

where maxD uc[D < </> 0 >]is the utility, associated with the best decision D, based on taking an immediate action using the current mean belief, < </>0 >. This measure tells us that the value of computing the final answer is just the difference in utility between the current best ac­ tion and the summation of future best actions weighted by the probability of different final beliefs.

Belief About Changes in Belief Real-world com­ puters rarely deliver the full expected value of perfect computation on difficult problems because they must expend valuable resources in the reasoning process. As­ sume that our agent in the intensive-care unit, faced with determining the probability that our elderly patient is in respiratory failure, has incomplete knowledge about what p(</>) will be at some future time t, which were­ fer to as p(p1(</>)). For example, the system may have a probability distribution over the future bounds on </> with additional computation. Such knowledge may have been acquired through an empirical analysis of a network in addition to an upper bound that has been proved the­ oretically. Our reasoner could apply this type of knowl­ edge by considering the EVC(t) based on the information about probability distributions over p( </> ), obtained with computation for an additional timet, as

That is, we sum over the new probability distributions on</> expected at timet, weighted by the current belief, P(Pt ( </>)), that thinking until t will lead to each of the revised distributions. In terms of the mean, < </>1 > of the future distributions, p1(</>),

When, for all t, the cost of computation, embod­ ied within our comprehensive utility function, becomes greater than the benefit of computing (EVC ~ 0), an agent should cease reflection and act. The EVC formula can be used to study the value of alternative inference schemes. Of course, there can be significant overhead in the real-time application of an EVC-based control strategy. Thus, a central goal of research on decision­ theoretic control is to identify tractable solutions to the EVC evaluation problem. Alternatively, offline analysis and compilation of control strategies may be useful in situations where the complexity of meta-analysis limits the gains of real-time decision-theoretic control.

Analogous value-of-computation approaches can be used to valuate and control other problem classes. For example, we can use an EVC(t) calculation for control­ ling the nature and extent of a search or sort problem; we associate a cost with the time required to expand another node in a tree, or to perform a set of tests and swaps in a partially sorted file, and consider a probability distribution over the expected object-level gains, given the allocated time. The development of tractable EVC approximations for these and other problems, make pos­ sible useful normative control through iterative testing of the value of continuing to reason.

5 Value of Probabilistic Bounding

We have pursued tractable solutions to the EVC through examining parameterized families of distributions. For example, we have explored the use of the EVC approach to control probabilistic bounding methods. Assume that our automated reasoner has, with some initial amount of computation, computed upper and lower bounds on </>, with an upper bound at b and lower bound at a. If our reasoner does not have any information about where 4> is-except that the final computed result will be between the current bounds-then it is reasonable to assume a uniform distribution over </> between the bounds. A uni­ form distribution within bounds is consistent with an agent being ignorant of the final belief, except for the bounds information. Detailed knowledge about conver­ gence could change this distribution. Let us focus on the value structure of assuming uniformity at both cur­ rent and future distributions about belief. We denote the problem by EVC/BU, the expected value of compu­ tation for a bounding algorithm given an assumption of uniformity.

An agent may have useful knowledge about Pt ( </>) with­ out having information about how the mean < <Pt > will change, except for knowing that 4> will be constrained to tighter bounds. As an example, a system could make use of certain or uncertain knowledge about the rate of bounds convergence to valuate a decision to continue to compute. We have analyzed how a system can apply knowledge that the bounds on the belief for a node in a belief network will converge at a rate dictated by a frac­ tion, C, which, when multiplied by the current bounds interval at t0 , dictates the interval at t. That is,

where int is just the interval, or the difference between the upper and lower bounds. If we were uncertain about the convergence, we would have a probability distribu­ tion over this convergence fraction.

We have applied the EVC equation to the bounding problem, considering future distributions expected with additional computation. Given a convergence fraction that allows us to calculate the future bounds, we must consider all possible configurations of the new bounds given the current constraints. As we sweep the expected future interval over the current interval, the mean of the future distribution sweeps between positions within the current bounds. When the mean is above p·, we sum over the utility of acting for all states of belief greater than that threshold; when the mean is below p·, we simi­ larly consider the utility of not acting. Given our current bounds and a convergence fraction, we sum the utilities of the best decision at the future means and subtract the utility of the best action without additional compu­ tation. Solving the uniform distribution case for different possible p· boundary conditions yields functions that re­ port the EVC as a function of (1) the utilities for each of the four outcomes, (2) the current bounds on </>, (3) a function describing the expected convergence of bounds (e.g., a C) with time, and ( 4) the cost of delay. Under un­ certain performance, a rational agent's reflection based on the EVC formalism involves the interlacing of probes for positive EVC(t) and continued inference. Computa­ tion should continue until action is indicated by a non­ positive EVC. This volley of reflection and inference is demonstrated in Figure 2.

5.1 Partial Characterization of Inference

We have experimented with decisions about computation and action within alternative utility contexts. We have particularly explored the behavior of recently-developed graceful approximation methods for probabilistic infer­ ence. These strategies include a flexible variant of Pearl's method of conditioning [Pearl, 1986], called bounded con­ ditioning [Horvitz et al., 1988b].

In the method of conditioning, a multiply connected network is reformulated to a set of singly connected net­ works by locating a set of nodes that break cycles. The complete set of cycle-breaking nodes is called the loop cutset. The nodes of the loop cutset are instantiated with each possible value (or combination of values) and the resulting joint probabilities of each instance ~re calcu­ lated as prior probabilities of the instantiated variables. Algorithms for solving the singly connected network sub­ problems can be applied to the solution of each network instance. In bounded conditioning, instances are ana­ ly~ed in order of their expected contribution to the tight­ enmg of bounds. The instances are sorted according to their prior probability, and are solved in sequence. A bounding calculus generates logical bounds on the final probability of interest by considering the maximum and minimum contributions of the unexplored subproblems.

We applied bounded conditioning to several random ne~~o~ks as ~ell ~ to a belief network describing prob­ abi~Istlc rela~wnships among findings and pathophyiso­ logic states m an mtensive-care unit. 3 The structure of. this belie~ network is captured by the graph in the middle of Figure 1. The network consists of 37 mul­ tiply connected nodes. We studied the performance of several loop cutsets for this network. A sample loop cut­ set consists of 5 nodes that leads to 144 different singly connected-network problems.

We sought to characterize the refinement of bounds with additional computation. Our analyses focused on updating belief in the intensive-care network with single pieces of evidence. We found that the convergence of the bounds :ould by approximated by an exponential decay of the size of the interval with time. This convergence was modeled approximately by the function

~dditional. discussion of bounded conditioning, includ­ mg analysis of the basis for such convergence is found in [Horvitz et .al., 1988b]. As an example, the conver­ gence of a typical update in the network is captured by an exponential decay with an approximate half-life of 36 seconds . That is, after 36 seconds of analysis by a Motorola-68020-based computer, running at a 17 MHz ~lock rate, the bounds converge to one-half of their orig­ mal bounds. At 72 seconds, the bounds are halved once again to an interval of approximately 0.25. This conver­ gence is modeled by the exponential decay with k = 0.02 . The convergence is displayed in Figure 3.

This convergence information can be used to calcu­ late an EVC associated with continuing to apply the bounding algorithm. Evaluating the EVC within our testbed intensive-care belief network has shown for sam­ ple updates and associated sets of utility estim~tes that a p* decision threshold can be crossed well befor'e the computation of final belief. Experimentation with ratio­ nal metareasoning to select among alternative inference strategies, and to control the length of time that they are applied is continuing on a variety of belief networks and decision contexts.

3 This network, called ALARM, was constructed by Ingo Beinlich [Beinlich et al., 1989].

5.2 Acquisition of Control Knowledge

Our formalism for the calculating the value of proba­ bilistic bounding operates on knowledge about conver­ gence on bounds. We have performed theoretical anal­ ysis of worst-case performance of bounded condition­ ing. We have also recorded empirically derived partial­ characterization information. Clearly, an agent could benefit by continually bolstering its knowledge about partial characterizations with extensive empirical study of problem-solving trajectories during idle-time. A com­ ponent of our research focuses on an offline analysis of the performance of reasoning strategies of different net­ works. The analyses are aimed at capturing useful par­ tial characterization of the expected performance of dif­ ferent strategies by performing Monte Carlo simulation to generate plausible patterns of evidence, and summa­ rizing and storing a set of performance indices. For ex­ ample, we are interested in the convergence of bounds in response to a state of evidence. This information can be extremely useful to a control reasoner that is attempt­ ing to valuate the EVC for a set of competing solution strategies. We are researching the automated acquisi­ tion of partial characterizations of stategy performance within the intensive-care unit application area.

6 Summary

We have described research on the rational interlacing of decision-theoretic inference ~ith action under scarce resources. We highlighted the use of partial characteriza­ tions of probabilistic inference to reason about the value of continuing to reason about a problem versus that of taking action in. the world. After defining the expected value of perfect computation, we explored the expected value of computation for reasoning about belief in a de­ cision context. We focused on the valuation of future computation, based on a consideration of future prob­ ability distributions over the truth of a proposition of interest. We described the use of normative metareason­ ing techniques for valuating and controlling probabilistic inference for time-pressured medical decisions. Prelimi­ nary empirical work has demonstrated that a probability bounding algorithm can deliver a large fraction of the expected value of perfect computation well in advance of complete inference. We are continuing to experiment with different distributions over belief and are working to characterize useful dimensions of algorithm performance. We foresee that advances in the application of decision­ theoretic reflection will play an important role in the development of effective normative reasoning systems.

7 Acknowledgments

We thank Ronald Howard, Edward Shortliffe, and Jacques Suermondt for their feedback on this work. Lyn Dupre provided comments on an earlier draft.