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

Eric Horvitz, Gregory Cooper, David Heckerman

Abstract:

We define and exercise the expected value of computation as a fundamental component of reflection about alternative inference strategies. We present a portion of Protos research focused on the interlacing of reflection and action under scarce resources, and discuss how the techniques have been applied in a high-stakes medical domain. The work centers on endowing a computational agent with the ability to harness incomplete characterizations of problem-solving performance to control the amount of effort applied to a problem or subproblem, before taking action in the world or turning to another problem. We explore the use of the techniques in controlling decision-theoretic inference itself, and pose the approach as a model of rationality under scarce resources.

Keywords: Decision-theoretic metareasoning, bounded optimality, flexible computation, Bayesian networks, rationality under bounded resources, automated reasoning, influence diagrams, decision-theoretic inference.

Published in: Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI, pages 1121-1127. Morgan Kaufmann, San Mateo, CA, August 1989.. Also, Stanford CS Technical Report KSL-89-1.

Author Email: horvitz@microsoft.com

Related articles

E.J. Horvitz, Computation and Action Under Bounded Resources, PhD dissertation. Stanford University, 1990.
E. Horvitz, Reasoning about Beliefs and Actions under Computational Resource Constraints, Third Workshop on Uncertainty in Artificial Intelligence, Seattle, Washington. July 1987. Association for Uncertainty and Artificial Intelligence. pp. 429-444. Also in L. Kanal, et al. ed., Uncertainty in Artificial Intelligence 3, Elsevier, 1989, pps. 301-324. Click here to access postscript.
E.J. Horvitz, Reasoning under varying and uncertain resource constraints. Proceedings of the Seventh National Conference on Artificial Intelligence, Minneapolis, MN. August 1988. Morgan Kaufmann, San Mateo, CA. pp. 111-116. (An analysis of ideal decisions about computation for urgent, deadline, and uncertain deadline situations, conditioned on available reasoning strategies). Click here to access postscript.
E. Horvitz and G. Rutledge. Time-Dependent Utility and Action Under Uncertainty. Uncertainty in Artificial Intelligence, Los Angeles, 1991, Morgan Kaufman, pp. 151-158. On the assessment, representation, and inference with time-dependent utility in high-stakes, time-critical situations.
J.S. Breese and E.J. Horvitz. Ideal Reformulation of Belief Networks , Proceedings of Sixth Conference on Uncertainty in Artificial Intelligence, Cambridge, MA, Association for Uncertainty in Artificial Intelligence, Mountain View, CA. July 1990. pp 64-72. (On strategic bounded optimality--the ideal control of flexible algorithms that are applied in sequence to compute actions.)
E. Horvitz. Models of Continual Computation. Proceedings of the Fourteenth National Conference on Artificial Intelligence, Providence, RI, July 1997. AAAI Press: Menlo Park. (Introduces concept and illustrative models for the ideal allocation of idle resources for precomputing future problem challenges.)
E. Horvitz. Continual Computation Policies for Utility-Directed Prefetching. Proceedings of the Seventh ACM Conference on Information and Knowledge Management, Bethesda MD, November 3-7 1998, pp. 175-184. ACM Press: New York. (On policies for continual computation--the ideal use of idle computational or networking resources-- for prefetching and caching content over limited bandwidth lines.)
E. Horvitz. Principles and Applications of Continual Computation. Artificial Intelligence Journal, 126:159-196, Elsevier Science, February 2001.
E. Horvitz and S. Zilberstein, Computational Tradeoffs Under Bounded Resources, Artificial Intelligence Journal, 126:1-4, Elsevier Science, February 2001.
E. Horvitz, Y. Ruan, C. Gomes, H. Kautz, B. Selman, D. M. Chickering. A Bayesian Approach to Tackling Hard Computational Problems. Proceedings of the Seventeenth Conference on Uncertainty and Artificial Intelligence, July 2001.
E.J. Horvitz, H.J. Suermondt, G.F. Cooper. Bounded conditioning: Flexible inference for decisions under scarce resources. In: Proceedings of Conference on Uncertainty in Artificial Intelligence, Windsor, ON. August 1989. Association for Uncertainty in Artificial Intelligence, Mountain View, CA, pp. 182-193. (On the control of flexible computation for probabilistic inference.)
E.J. Horvitz and J.S. Breese, Ideal Partition of Resources for Metareasoning. Technical Report KSL-90-26, Knowledge Systems Laboratory, Stanford University, February 1990. (On strategic bounded optimality--the ideal control of a set of available flexible algorithms applied in sequence.)
E.J. Horvitz, Rational Metareasoning and Compilation for Optimizing Decisions Under Bounded Resources. Proceedings of Computational Intelligence '89, Milan, Italy, September 1989. Association for Computing Machinery. (On the role of compilation in bounded-optimal architectures, and the value of partial compilation and platform results).
D. Heckerman, J.S. Breese, E. Horvitz, The Compilation of Decision Models, Proceedings of the Conference on Uncertainty in Artificial Intelligence, Association for Uncertainty in Artificial Intelligence, July 1989, pages 162-173.
E.J. Horvitz, Problem-Solving Design: Reasoning about Computational Value, Tradeoffs, and Resources. Proceedings of the 1987 NASA Artificial Intelligence Forum, Palo Al to, CA, October 1987, pp. 26-43. National Aeronautics And Space Administration: Mountain View, CA. (On different classes of control; strategic versus fine-grained control of computation.).

Back to Eric Horvitz's home page.