Decisions under scarce resources and bounded optimality
Bounded optimality refers to the goal of optimizing the expected utility
of a reasoning system, given the environment in which the system is
immersed. This goal differs from the related work of investigators (including John March and Herbert Simon)
who have proposed heuristic approaches to rationality under bounded resources. To compute the expected utility of an agent's behavior at
design time, we must consider the set of responses a system makes to a
sequence of challenges over time. We must also identify the design
actions that are available for optimizing an agent's behavior by
considering the set of controllable parameters and invariant constraints in the hardware or software
architecture of the agent. Specifying different sets of constraints on
the constitution of a reasoning system defines different classes of bounded
optimality.
Bounded optimality, and the goal of optimizing the
expected utility of an agent given a sequence of challenges
over time (e.g., an agent's lifetime), was introduced in:
Click here to access a brief excerpt on bounded optimality from this article.
Other early work at Stanford examining aspects of rationality under bounded resources and bounded optimality is described in:
- 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 bounded-optimal decisions
for urgent, deadline, and uncertain deadline situations, conditioned on available reasoning strategies).
Click here to access postscript.
- E.J. Horvitz, G.F. Cooper, D.E. Heckerman, Reflection and action under scarce resources: Theoretical principles and empirical study. Proceedings of the Eleventh International
Joint Conference on Artificial Intelligence, Detroit, MI. August 1989. International Joint Conference on Artificial Intelligence. pp 1121-1127. (On decision-theoretic control of decision-theoretic reasoning---reasoning about probability and decision under time constraints.)
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.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.).
- E.J. Horvitz, Computation and Action Under Bounded Resources, PhD dissertation. Stanford University, 1990.
Accessing Relevant Papers
Back to Eric Horvitz's home page.