  Computing value of information (VOI) is a crucial task in various aspects of
decision-making under uncertainty, such as in meta-reasoning for search; in
selecting measurements to make, prior to choosing a course of action; and in
managing the exploration vs. exploitation tradeoff. Since such applications
typically require numerous VOI computations during a single run, it is
essential that VOI be computed efficiently. We examine the issue of anytime
estimation of VOI, as frequently it suffices to get a crude estimate of the
VOI, thus saving considerable computational resources. As a case study, we
examine VOI estimation in the measurement selection problem. Empirical
evaluation of the proposed scheme in this domain shows that computational
resources can indeed be significantly reduced, at little cost in expected
rewards achieved in the overall decision problem.
