Bounded optimality
Bounded optimality refers to optimizing the expected utility of a reasoning system, given the constraints of computational hardware and distribution of challenges in 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:
- E. Horvitz, Reasoning about Beliefs and Actions under Computational Resource Constraints, Proceedings of the Third Conference on Uncertainty in Artificial Intelligence, Seattle, Washington. July 1987. Association for Uncertainty and Artificial Intelligence. Conference on Uncertainty and Artificial Intelligence (UAI-87), July 1987, pp. 429-444.
Book chapter published under same title published in: L. Kanal, et al. ed., Uncertainty in Artificial Intelligence 3, Elsevier, 1989, pp. 301-324.
Other work examining aspects of rationality under bounded resources and bounded optimality is described in:
- 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.)
- E. Horvitz. Principles and Applications of Continual Computation, Artificial Intelligence Journal, 126:159-196, Elsevier Science, February 2001.
- 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).
- 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 bounded optimality for metareasoning versus base=level problem solving: Identifying the ideal amount of time partitioned for metareasoning versus base-level problem solving. Early analysis of use of differentiation to solve for optimal reasoning performance.)
- E. Horvitz. Computation and Action under Bounded Resources. PhD Dissertation, Stanford University, 1990 (pdf).
- S.J. Gershman, E.J. Horvitz, J.B. Tenenbaum. Computational Rationality: A Converging Paradigm for Intelligence in Brains, Minds, and Machines, 16 July 2015, Science 349. 273-278 (2015).
- 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 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. 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, 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 the goal of optimizing different classes of control; strategic versus fine-grained control of computation.).
Accessing Relevant Papers
Back to Eric Horvitz's home page.