Continual Computation Policies for Allocating Offline and Real-Time Resources

1 Introduction

Research on problem solving under bounded resources has focused primarily on real-time reason­ ing [7, 8, 1, 2, 10, 3, 12, 11, 9, 14]. In contrast, work on continual computation centers on developing methods for harnessing the resources available in periods tra­ ditionally viewed as "idle time" between challenges [4, 13]. Such policies have application to a variety of tasks ranging from generating contingency plans to prefetching web pages and computing ideal observa­ tions to make next in situation assessment or diagno­ sis. In this paper, we explore continual-computation policies that take into consideration both idle and real-time resources. The methods center on a con­ sideration of the expected value flux generated by problem-solving strategies.

We first present several utility models that describe how strategies generate results of partial value with computation. For background and clarity, we shall review results described previously on ideal continual­ computation policies for these utility models. Then we present a new class of precomputation policies by integrating a consideration of future real-time refine­ ment that may follow the identification of a challenge. Finally, we examine the case of generalizing the meth­ ods to consider issues with trading the efficacy of real­ time problem solving for enhanced future responses.

Assume we have access to probabilities, p(IIE), of seeing different problem instances I in the next pe­ riod, given some evidence E that has been observed. Inferring the likelihood of future instances can range from trivial to difficult depending on the application. We will not focus in this paper on the means for build­ ing probabilistic models or collecting statistical data for inferring or accessing the likelihood of problem instances (see [5] for examples of learning probabilis­ tic models for continual computation and [4] for a discussion of methods for computing likelihoods of future problem instances). Instead, we focus on the derivation of ideal policies that take as input like­ lihood information of any degree of precision about the occurrence of future problems. We seek to op­ timize the expected value of a system's response for the case where we have access to one or more flexible algorithms with the ability to generate partial results that have value to a user before a final, precise answer is reached.

A flexible or anytime reasoning strategy S hC;\8 the ability to refine an initial problem instance I or fur­ ther refine a partial result 1r(I) that has been previ­ ously generated [6, 2]. The expected value of compu­ tation (EVC) is the change in utility with computa­ tion [8, 11]. EVC is computed as follows:

where 1r'(I) represents a refinement of 1r(I), and u0 (1r(I)) represents the object-level value of the ini­ tial or previously refined partial result 1r(I), without consideration of the cost of computation. For the case where cost is deterministic and separable from the value of computation, the net EVC (NEVC) is just

where C(t) represents the cost of delay associated with the computation.

We distinguish offline, precomputation processes from real-time computation, and use the phrase expected value of precomputation (EVP) to refer to the expected change in NEVC for actions taken to ad­ dress challenges in a future period. The EVP assoc­ iated with allocating offline resources, T, to refine the result associated with a potential future problem I is

We can characterize flexible computation strategies in terms of the rote at which they deliver future value with precomputation. We refer to the instantaneous rate at which EVP changes at point of allocating T seconds of precomputation time to solving problem I with strategy S, as the EVP flux, t/J(S, I, T),

The EVP flux is the slope of the curve describing the utility associated with a computed partial result over time. For simplicity, we shall leave out the ar­ guments of EVP and use t/J(I, T) as shorthand to refer to the expected EVP flux associated with the strategy~instance pair after T seconds of precompu­ tation. Let us assume for convenience that the se­ lection of a strategy or sequence of strategies S is predefined or optimized for each problem instance, and use S* to refer to these strategies. We shall not dwell in this paper on the problem of choosing ideal strategies; such work has been a focus of research on real-time reasoning under varying and uncertain resources (e.g., see [2]). The choice of strategy does not influence the fundamental results on policies for continual computation.

Assume that we have access to probabilities and performance profiles that provide a measure of the EVP flux, t/J(I, t), for each future problem instance I under consideration. Further, assume that a sys­ tem apportions fractions of the total available idle time It to refining results for several potential future challenges. The overall EVP associated with multi­ ple allocations can be computed by integrating the expected flux for resources allocated to each instance and summing together the EVP derived from each problem, ·

Given uncertainty in the amount of idle time, we have,

The goal of an automated reasoner endowed with the ability to reason about EVP is to leverage resources that are currently available to strategy-problem in­ stance pairs so as to maximize the overall EVP. In the general case, identifying policies for allocating offline resources that yield the maximal future value, EVP*, requires a consideration of the details of the proba­ bility distribution over idle time, p(T), and the appli­ cation of search or closed-form optimization methods to choose the best set of ft. We seek precomputa­ tion principles, and associated policies, that forego the need for such optimization.

3 Policies for Prototypical Classes of Refinement

We shall review ideal policies for three classes of flexi­ ble procedures, defined by the functional form of util­ ity models that describe the incremental value pro­ vided as they refine partial results. These classes include algorithms that refine results with constant flux, piecewise linear flux with decreasing returns, and smoothly increasing utility with decreasing returns. The utility models representing the performance pro­ files of these algorithms are displayed as representa­ tive curves in Figure 1.

3.1 Constant Flux

We first review ideal precomputation policies for the case of procedures that provide constant flux de­ scribed previously in [4).

Theorem 1 Idle-Time Partition for Linear EVP Flux. Given future problem instances I, that may challenge a system in the next period, and an EVP flux t/J(I,, t) for the solution of each instance that is constant with time, the idle-time resource partition policy that maximizes the expected value at the start of the next period is to apply all resources to the prob­ lem with the maximal EVP flux. That problem should be refined until a final result is reached, followed by the result with the next highest product should be an­ alyzed, and so on, until the cessation of idle time or solution of all problems possible in the next period.

Proof: By definition, the allocation of time to each instance for strategies S applied to problem instances provide constant EVP fluxes t/J(I;, T) = C; for each instance based on the refinement of a sequence of par­ tial results. The total EVP can be rewritten as,

For any amount of idle time T, the ideal policy is to apply all resources to the instance with the highest value of C;. Any amount of time x re-allocated to an­ other instance would diminish the total EVP because it would be multiplied with smaller valued products.

When problem instance I associated with the largest product, is solved completely, it is removed from consideration and the same argument is made with the remaining n - 1 problems. ·

3.2 Prototypical Nonlinear Models

Policies for procedures yielding flux described by piecewise linear and smoothly increasing utility mod­ els can be viewed as a generalization of the case of constant flux. Instead of associating problem in­ stances with constant levels of expected flux, we con­ sider the flux associated with subcomponents of prob­ lems, and consider ideal strategies for solving these components. Continual computation policies for such models with a focus on the application of prefetching documents are described in [5]. We review the earlier results generalized to the case of real-time reasoning, before moving on to consider new policies that include a consideration of real-time resources.

Theorem 2 Idle-Time Partition for Piecewise Lin­ ear Utility with Decreasing Rate. Given problem instances I;, that may be accessed in the next pe­ riod, and EVP flux described by tjJ(I;, T) that is piece­ wise linear and where successive segments have posi­ tive slope but progressively smaller flux, the resource partition policy that maximizes the expected value at the start of the next period is to continue to allocate resources to the linear segment drawn from the set of next available linear segments of instances that has the maximal expected flux, and to continue to refine the problem associated with that segment, and then to move to the segment with the next highest expected value flux until all segments of all problems are solved or the cessation of idle time.

Proof: We extend Theorem 1 on the ideal alloc­ ation of resources for constant flux to each piecewise linear segment associated with the current state of refinement of a problem. We now consider portions of problem solving associated with each segment of the piecewise linear utility function model instead of the entire problem. We know that the instance that offers the maximal instantaneous expected flux will add the most to the overall expected utility and that all other instances will deliver less value now and-by definition of decreasing returns-at all other times in the future. Including any other segment in the in­ tegration represented by Equation 6 would lead to a smaller total EVP for any amount of idle time. Thus, we need only to check the next available segment for each incompletely solved problem to identify the best sequence of segments. Choosing any other segments would lead to a diminishment of the overall expected value at the start of the next period as compared with this policy. ·

Thus, the policy for maximizing the contribution to the expected value iii the next period will be to look at all linear segments of all problems under consider­ ation and to continue to solve the segment associated with the highest flux, then refine the problem assoc­ iated with the segment with the next highest expected flux.

Figure 2 summarizes the approach for creating ideal EVP policies for the case of piecewise linear and smoothly increasing utility. We transform the fluxes associated with the computing each problem instance into expected fluxes for solving future problems given uncertainty in their occurrence. An ideal policy is identified by continuing to expend all resources to solve the instance that delivers the greatest instanta­ neous flux.

3.3 Smoothly Increasing Utility with Decreasing Returns

We can easily generalize Theorem 2 to the case of util­ ity models represented as smoothly increasing func­ tions by taking the size of segments in the piecewise linear models to zero in the limit.

Theorem 3 Partition of Resources for Smoothly De­ creasing Flux. Given problem instance-strategy pairs that may need to be addressed in the next period, and a value flux described by t/J(I;, T) for the solution of each instance associated with d'f/J(l;, T)jdt < 0 for the solution of each instance associated, the resource par­ tition policy that maximizes the expected value at the start of the next period is to allocate resources to the problem with the maximal product of probability and instantaneous value flux, until all problems are solved or until the cessation of idle time.

Proof: For situations where the expected flux is monotonically decreasing for all instances, the policy for maximizing the contribution to the expected value in the next period will be to continually pick the prob­ lem associated with the highest mean expected flux for any small quantity of expenditure. Because each instance has an expected flux that is monotonically decreasing with allocation of resources, the greatest currently available flux must be greater than the fu­ ture expected flux associated with this or any other instance. Thus, any other order of analysis with in­ finitesmal amounts of resource will result in a lower overall EVP. ·

4 Influence of Future Real­ Time Refinement

The EVP policies described above center on an opti­ mization of the expected value of the system at the time a new challenge is received. We now extend the policies to consider real-time computation. We start with a consideration of the prototypical real­ time problem of reasoning with a procedure that pro­ vides smoothly increasing utility with decreasing re­ turns in the context of cost that increases constantly with time. A graphical representation of this prob­ lem is displayed in Figure 3. As displayed in the fig­ ure, the strategy provides increasing value, but with decreasing marginal returns for the same amount of computation at increasingly greater levels of refine­ ment, until a final result is generated. We refer to this class of real-time reasoning problem as decreas­ ing return, constant cost scenarios. We first identify the ideal quantity of real-time deliberation for these problems.

Theorem 4 Ideal Deliberation for Decreasing Re­ turns, Constant Cost Scenarios. For scenarios of de­ creasing returns and constant cost, action should be taken immediately if the net EVC flux at the outset of a challenge is nonpositive; otherwise, real-time re­ finement should continue until the EVC flux is equal to the cost.

A graphical depiction of the ideal halting time is represented in Figure 3. An instance is refined into partial results 1r(I) with computation or precomputa­ tion time T, eventually reaching the final, completely solved result, r/>(I) . The EVC flux is equal to the rate at which cost is incurred at the ideal halting, t*. At this time, the algorithm generates an ideal result, 1r*(I). Figure 3 shows the tangent to the utility curve at this point of refinement, representing the EVC flux at the ideal halting time. As displayed in the figure, the rate at which value is generated is balanced at this point of refinement by the rate at which cost is accrued. Continuing to perform real-time computa­ tion after this level of refinement is achieved would incur costs faster than gains in value.

Let us now consider EVP and continual­ computation policies for problem solving captured by such decreasing returns, constant cost situations. We refer to the partial result generated at the ideal time indicated for halting, t*, for a particular cost function c, strategy S, and instance I, per Theorem 4 as the ideal real-time result, 1r*(I). The ideal real-time re­ sult is insensitive to the amount of resources allocated to precomputation of a problem instance because the rate at which cost is accrued is constant.

Applying idle-time resources to scenarios of de­ creasing returns with constant cost can be viewed as a means of achieving cost-free refinement. Consider the value of precomputation for the case where a sys­ tem knows that it will face a problem with probability 1.0. The NEVC at the time the ideal real-time result is computed is simply the expected utility associated with an action in the world associated with 1r· (I), eu(1r*(I)), less the total cost accrued so far in com­ puting the result. The total cost is simply the product of the rate at which cost is accrued and the amount of real-time resources expended on the problem prior to generating the ideal real-time result.

We can now analyze the value of precomputation in light of the prospect of future real-time reasoning to further refine a result. Precomputing a result of the quality represented by 1r*(I) removes the cost func­ tion for the time allocated to precomputing the result. Thus, the precomputation adds value to the ultimate utility that will be achieved when the result reaches the level of refinement represented by 1r*(I) with a flux equal to the rate at which real-time cost would have been accrued without precomputation. This flux is computed as the product of the probability of the instance and the cost.

Figure 4 displays graphically the impact of precom­ putation on the value of the result. The updated rea­ soning problem is represented by the solid lines por­ trayed in contrast to the broken lines, representing the situation before precomputation. As displayed in the figure, the cost function only begins to "tug" down on the net value of the result when real-time reasoning begins. Precomputation reduces the re­ quired real-time computation and raises the ultimate . value of the ideal real-time result by the total amount of cost saved. Two small vertical arrows in Figure 4 represent the source and quantity of the jump in util­ ity achieved with precomputation.

We now consider the case of continuing to refine the result with precomputation beyond the ideal real-time result. Additional precomputation applied to refining a result beyond 7r* (I) adds additional value to the ultimate result at the cost-free rate associated with the instantaneous flux provided by the strategy in return for resources allocated beyond those required to achieve the ideal real-time result. Figure 4 demon­ strates graphically how refining a result with precom­ putation beyond the ideal real-time result adds value in accordance with the flux delivered by the strategy in these regimes.

In summary, we must consider two situations for computing the EVP associated with precomputing in­ stances for scenarios of decreasing returns, constant cost: H the level of refinement of a result reached with precomputation is less than the value represented by 1r*(I), the value flux is the product of the rate at which cost is accrued and the probability of being challenged with the instance. For refinement of a result by precomputation beyond the quality repre­ sented by 1r* (I), the value flux is the product of the probability of seeing the problem instance and the EVC flux associated with the strategy for increas­ ing amounts of precomputation time following the achievement of 1r* (I).

Given our analyses of these two situations, we can develop policies for the general case of multiple prob­ lem instances and uncertainty. Given a set of po­ tential future problem instances under uncertainty, we can adapt Theorem 4 to provide a policy for pre­ computation that takes into consideration future real­ time reasoning. The policies consider all instances under uncertainty, noting for each instance whether the partial result achieved so far with precomputation falls short of the quality of the associated 1r* (I).

Theorem 5 Continual Computation Policy for De­ creasing Returns, Constant Cost Scenarios. For scenarios characterized by decreasing returns in a constant cost context, it is ideal to allocate offiine computational resources to solving instances in order of the product of the probability of the instance and the cost of delay when refinement is below the utility associated with 1r*(I) and the product of the instan­ taneous rate of refinement and the probability of the instance when the value is greater than 1r*(I).

Proof: For a constant probability of being challenged by an instance, the EVP flux for results of lesser qual­ ity than 1r* (I) is a constant determined as the product of the probability of the instance and the cost of delay. The EVP flux for results refined beyond the quality of 1r*(I) is the product of the probability and the instan­ taneous fltix provided by precomputation. The EVP flux in regimes where quality is higher than 7r* (I) is smoothly decreasing and is smaller than the flux for refinement up to 1r*(I). Drawing upon Theorems 1 and 4, the maximal total EVP, will be obtained by continuing to select available instances with the highest expected EVP flux. Given that the EVP flux associated with strategies either provide constant or decreasing EVP flux with the allocation of precompu­ tation time, any other order will lead to a suboptimal EVP. ·

5 Redirecting Resources to Fu­ ture Problems

So far, we have considered the allocation of available idle time solely for solving future problems. We have assumed that real-time computation is fully dedicated to solving a current challenge until reaching an ideal halting time. We can generalize the continual com­ putation policies by considering the value of allowing real-time resources to be allocated to precomputa­ tion of future problems before a current problem is completed. Such a generalization considers trading a loss in the quality or timeliness of the response to current challenges for an enhanced expected response to future challenges. Such re-allocations can increase the overall expected value of a system's performance. It is worthwhile allocating resources from current to future problems when the EVP of potential future problems outweighs the EVC associated with solving the current problem.

The boost in EVP associated with the redirection of real-time problem solving to precomputing the so­ lution of potential future problems depends on the amount of idle time that will be available before the next challenge arrives. If there will be sufficient idle time to precompute a majority of important future problem instances, little may be gained by an imme­ diate transfer of real-time resources to precomputa­ tion. Thus, we must model the probability distribu­ tion over the available idle time, and use this infor­ mation to compute the expected value of the transfer of resources to the future problems.

Let us use EVP* (T) to refer to the expected value of precomputation derived by following an ideal EVP policy (i.e., a policy dictated by the results described earlier), given the availability of T seconds of idle time between the completion of the current problem and the arrival of the next challenge. Suppose we are in the process of computing a response to a cur­ rent challenge. The probability distribution over idle time, p(TIE), can be determined from the probabil­ ity distributions over the computation time required to complete the current analysis and over the time the next problem instance will be faced by the sys­ tem. Assume that we have access to such probabilis­ tic information, based on data collected on the per­ formance of reasoning procedures and on the rates at which different classes of problem instances are faced by an agent in an environment or specific setting. Given p(TIE), we compute the instantaneous change in EVP with computation of future challenges for dif­ ferent idle times T and sum over the uncertainty in idle time to generate an expected value flux at differ­ ent values of idle time, dEV J; (T) ,

where V represents a time-sensitive discount function that yields a discount rate, d :$ 1.

In real-time, we consider the instantaneous EVC flux associated with current problem solving with the instantaneous expected flux of solving future prob­ lems for small amounts of resource. If the current EVC flux is greater than the expected flux of solv­ ing future problems we continue to solve the current problem with the resource. However, if solving future problems has greater flux, we allocate the resource to computing future problems. We make the myopic as­ sumption at each step that the probability distribu­ tion over idle time is determined by the time required to finish the current analysis. Thus, at each step of the analysis we consider an estimate of the revised time required for solving the current problem in 8. We can now build an overall EVP policy for allocat­ ing resources to each problem by considering the flux associated with each problem instance and continuing to choose the instance with the highest instantaneous flux.

6 Summary

We presented continual-computation policies for har­ nessing idle resources to enhance the future expected value of computation. We reviewed policies for sev­ eral classes of refinement and developed an analysis and associated policy for folding in a consideration of additional refinement with future real-time resources. Finally, we described an approach to making decisions about redirecting resources being used solve a current challenge so as to precompute responses to potential future problems.

We are pursuing extensions to this work in several areas. Opportunities for ongoing research in contin­ ual computation include folding into the analyses a consideration of multiple periods in the future, rea­ soning about the explicit handling of sequences of challenges, and taking into consideration risk prefer­ ence for handling uncertainty about the probability of future challenges.

Acknowledgments

Jack Breese, Carl Kadie, Jed Lengyel, Chris Meek, Natalia Moore, and Mark Peot provided useful feed­ back on this work.