Reasoning under Varying and Uncertain Resource Constraints

Eric HorvitzAAAI 1988 · OpenReview

Abstract

We describe the use of decision-theory to optimize the value of computation under uncertain and varying resource limitations. The research is motivated by the pursuit of formal models of rational decision making for computational agents, centering on the explicit consideration of preferences and resource availability. We focus here on the importance of identifying the multiattribute structure of partial results generated by approximation methods for making control decisions. Work on simple algorithms and on the control of decision-theoretic inference itself is described.

Introduction: The Challenge of Resource-Boundedness

Traditional computer science often evaluates algorithms based on their worst-case or average-case complexity to reach a final, "correct" state. However, in real-world, high-stakes environments—like a medical emergency or an autonomous vehicle—an agent may not have the luxury of waiting for a complete execution. Most traditional systems are "all-or-nothing": they either provide a perfect answer or no answer at all if interrupted.

This paper proposes a decision-theoretic framework for "computational rationality," where AI agents optimize their reasoning strategies when faced with limited or uncertain resources, such as time and memory. Rather than focusing solely on final answers, agents should manage a spectrum of "partial results" to maximize the expected utility of their computation.

A Decision-Theoretic Framework for Computation

The core of the proposed methodology is the application of decision theory to the "meta-level" of computation. The agent acts as a "believer" rather than a "knower," using probabilistic beliefs about an algorithm's performance to decide whether to keep thinking or to act. Key components include:

  • Computational Utility ($u_c$): Defined as the net value of a strategy, decomposed into Object-level utility ($u_o$)—the benefit of the information generated—and Inference-related utility ($u_i$)—the cost or "disutility" of the time and resources spent.
  • Multiattribute Utility: Results are evaluated across multiple dimensions, such as precision, certainty, or specific sub-goals, rather than a single accuracy score.

Analyzing Refinement Trajectories

To understand how utility evolves, the author analyzes "refinement trajectories." These trajectories describe how different algorithms improve a result over time. Some algorithms might improve accuracy linearly, while others might stay at zero value until a sudden "aha moment" at the very end.

A linear refinement trajectory representing steady progress in utility over time.

In the Protos/Algo system, the author used sorting algorithms (Selection Sort vs. Shellsort) as a proxy for more complex reasoning. A "slow" algorithm (like Selection Sort, $O(N^2)$) might actually be superior to a "fast" one (like Shellsort) if the user specifically values "low-end completion" (having the first few items correctly sorted early) and there is a high probability of a sudden deadline.

Metareasoning and Strategy Selection

The framework successfully formalizes the optimization problem for choosing a strategy $S^*$ that maximizes expected utility under uncertain deadlines. This involves comparing the expected utility of different strategies against a probability distribution of potential deadlines ($t_h$).

The decision-theoretic selection of a computational strategy based on the expected utility of partial results and a probability distribution of deadlines ($t_h$).

As shown in the figure above, the system evaluates the partial results (visualized as scatter plots of Key vs. Position in a sorting task) to determine which strategy ($S^A$ or $S^B$) offers higher utility given the urgency and the likelihood of interruption. Rational agents must choose strategies that fit the specific "cost-of-delay" function of their environment, distinguishing between constant "Urgency" and hard "Deadlines."

Key Insights and Results

  • The Value of Partial Results: Computation should be viewed as a continuous refinement process. A rough estimate often has significant utility if a hard deadline hits.
  • Algorithm Dominance is Context-Dependent: The "graceful" refinement of certain algorithms makes them superior in urgent-deadline situations, even if they have worse asymptotic complexity than traditional $O(N \log N)$ algorithms like Quicksort.
  • Complexity Awareness: Because probabilistic inference in belief networks is NP-hard, meta-level decision-making is not just an optimization but a requirement for practical AI.

Conclusion

While the model primarily treats resources as a scalar (time), it lays the groundwork for balancing memory, power, and bandwidth. The author acknowledges the "infinite regress" of metareasoning—the meta-decision itself consumes resources—and suggests moving toward granular "micro-control" of inference, where the system adjusts its reasoning path at every step based on the evolving context.

Summary updated

Abstract

We describe the use of decision-theory to optimize the value of computation under uncertain and varying resource limitations. The research is motivated by the pursuit of formal models of rational decision making for computational agents, centering on the explicit consideration of preferences and resource availability. We focus here on the importance of identifying the multiattribute structure of partial results generated by approximation methods for making control decisions. Work on simple algorithms and on the control of decision-theoretic inference itself is described.
BibTeX
@inproceedings{horvitz1988reasoning,
  author = {Eric Horvitz},
  title = {{Reasoning under Varying and Uncertain Resource Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
  url = {https://openreview.net/forum?id=H1b4QeWdWS},
}
Figure