Reasoning about beliefs and actions under computational resource constraints

By Eric Horvitz. 1987

Although many investigators affirm a desire to build reasoning systems that behave consistently with the axiomatic basis defined by probability theory and utility theory, limited resources for engineering and computation can make a complete normative analysis impossible. We attempt to move discussion beyond the debate over the scope of the problems that can be handled effectively to cases where it is clear that there is insufficient computational or engineering resource to perform an analysis deemed to be complete. Under these conditions, we stress the importance of considering the expected costs and benefits of applying alternative approximation procedures and heuristics for computation and knowledge-acquisition. We discuss bow knowledge about the structure of user utility can be used to control value tradeoffs for tailoring inference to alternative contexts. We finally address the notion of real-time rationality, focusing on the application of knowledge about the expected timewise-refinement abilities of reasoning strategies to balance the benefits of additional computation with the costs of acting with a partial result.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Research Priorities for Robust and Beneficial Artificial Intelligence (2015, background): “Example research topics in this area include reasoning and decision under bounded computational resources `a la Horvitz and Russell [58, 59], how to take into account correlations between AI systems’ behaviors and those of their environments or of other agents [60–64], how agents that are embedded…”
Learning model-based planning from scratch (2017, methodology): “pture the world dynamics, and was only applied to learning Markov reward processes rather than solving Markov decision processes (MDPs). Our approach is also related to classic work on meta-reasoning [18, 13, 10], in which an internal MDP schedules computations, which carry costs, in order to solve ”
Distillation-Based Training for Multi-Exit Architectures (2019, background): “The roots of anytime computation go back to the work of [6, 16].”
Perception, Action, and Utility: The Tangled Skein (2012, background): “For example, an extremely rich research tradition in artificial intelligence has examined how to incorporate computational costs into decision-making systems (e.g., Horvitz, 1988; Russell and Wefald, 1991; Zilberstein, 1995).”
Bounded Rationality (1999, unknown): “Boddy and Dean (Boddy & Dean 1989), and Horvitz (Horvitz 1987), independently developed an approach to meta-reasoning for a special class of decision procedures, known as exible computations, or anytime algorithms.”
I Don't Want to Think About it Now: Decision Theory with Costly Computation (2010, unknown): “In a sequence of papers (see, for example, [Horvitz 1987; Horvitz 2001] and the references therein), Horvitz continues this theme, investigating various policies that trade off deliberation and action, taking into account computation costs.”
Learning Bayesian Networks: Search Methods and Experimental Results (1995, background): “[Horvitz, 1987] Horvitz, E. (1987).”
Decision Theory with Resource-Bounded Agents (2013, background): “The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the US government.”
Information-Theoretic Bounded Rationality (2015, background): “In contrast, the notion of bounded optimality deﬁnes the optimal policy as the program that achieves the highest utility score on a particular machine given complexity constraints, and oftentimes relies on meta-reasoning for practical implementations [Horvitz, 1989, Russell and Subramanian, 1995].”
Using Anytime Algorithms in Intelligent Systems (1996, methodology): “ Horvitz (1987) used a similar construct to describe the object-related value of flexible computation.”