Continual Computation Policies for Allocating Offline and Real-Time Resources

Eric HorvitzIJCAI 1999 · OpenReview

Abstract

This paper introduces a formal decision-theoretic framework for "continual computation," a strategy where AI systems utilize idle time to precompute solutions for anticipated future challenges. By defining the Expected Value of Precomputation (EVP), the framework enables optimal resource allocation between current tasks and future preparations, maximizing long-term utility under bounded rationality constraints.

Introduction

In the field of artificial intelligence, research often prioritizes how an agent should act "in the moment" when faced with a challenge. However, many systems experience significant "idle time" between tasks. This paper explores continual computation: the strategic use of idle time to solve future problems before they arrive. The challenge lies in determining how to allocate these resources effectively, balancing the probability of a problem occurring with the potential utility gain through precomputation. This requires integrating "offline" efforts with the "real-time" refinement that occurs once a challenge begins.

Methods and Utility Models

The framework is built around several key decision-theoretic concepts:

  • Expected Value of Computation (EVC): The change in utility gained by refining a partial result.
  • Expected Value of Precomputation (EVP): The EVC of a future problem, weighted by the probability $p(I|E)$ that the problem will occur.
  • EVP Flux: The instantaneous rate at which precomputation adds value, represented by the slope of the utility curve.

The paper identifies three prototypical utility models for anytime algorithms: constant flux (linear), piecewise linear, and smoothly increasing with diminishing returns.

Prototypical utility classes: (a) smooth diminishing returns, (b) piecewise linear, and (c) linear utility.

The core method is a greedy allocation policy: to maximize total expected value, the system should always apply its resources to the problem (or segment of a problem) that currently offers the highest EVP flux.

Key Insights: The "Boost" Effect

A central insight is that precomputation acts as "cost-free" refinement. In real-time scenarios, computation carries a cost—the cost of delay. Precomputation is essentially free because it utilizes otherwise idle resources. This creates a "jump" in starting utility when a real-time challenge begins.

The "boost" effect of precomputation, showing how it removes cost penalties for pre-solved work segments.

Furthermore, precomputation changes the economics of real-time reasoning. By pre-solving the "easy" parts of a problem, the system can reserve its precious real-time resources for high-value refinements that occur after the initial solution is found. This leads to an "Ideal Halt" point where the rate of utility gain balances the cost of delay. Perhaps most provocatively, the framework suggests a system should sometimes stop working on a current task to start precomputing for a future one if the expected flux of the future problem is higher than the current task's marginal gain.

Key Results

The paper formalizes several theorems for optimal resource allocation:

  • Theorems 1 & 2: For linear and piecewise utility, the optimal policy is to solve problems in descending order of their EVP flux.
  • Theorem 5: Provides a unified policy for "decreasing returns" scenarios. It dictates that resources should be allocated based on the product of the probability of the instance and the cost of delay (when below a certain utility threshold) or the product of probability and the instantaneous rate of refinement (when above that threshold).

Limitations and Future Work

The framework's effectiveness relies heavily on accurate estimations of future problem probabilities ($p(I|E)$) and algorithm performance profiles, which can be difficult to obtain in real-world settings. Additionally, the current models focus on the immediate next period and assume a risk-neutral agent. Future research could extend these policies to multiple future periods and incorporate risk preferences regarding the uncertainty of future challenges.

Summary updated

BibTeX
@inproceedings{horvitz1999continual,
  author = {Eric Horvitz},
  title = {{Continual Computation Policies for Allocating Offline and Real-Time Resources}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=rkNGlHGdZS},
}
Figure