Estimating the Value of Computation in Flexible Information Refinement
This work addresses the trade-off between computational cost and value for decision-making algorithms, but it appears incremental as it builds on existing anytime methods for a specific domain.
The paper tackles the problem of estimating the value of computation for flexible algorithms, using an empirical model to balance cost and value, and applies it to policy construction in influence diagrams, showing that features of their anytime algorithm provide reasonable estimates.
We outline a method to estimate the value of computation for a flexible algorithm using empirical data. To determine a reasonable trade-off between cost and value, we build an empirical model of the value obtained through computation, and apply this model to estimate the value of computation for quite different problems. In particular, we investigate this trade-off for the problem of constructing policies for decision problems represented as influence diagrams. We show how two features of our anytime algorithm provide reasonable estimates of the value of computation in this domain.