The plot in Figure 1 is computed according to belief update formulas for normally distributed beliefs and presents dependency of the intrinsic value estimate on the number of observations in a single step. The straight line corresponds to the measurement costs.

![0_image_0.png](0_image_0.png)

Under these conditions, the algorithm with one measurement per step will terminate without gathering evidence because the value estimate of the first step is negative, and will return item s1 as best. However, observing s2 several times in a row has a positive value, and the updated expected utility of s2 can eventually become greater than u(s1). Figure 1 also shows the intrinsic value growth rate as a function of the number of measurements: it increases up to a maximum at 3 measurements, and then goes down. Apparently, the myopic scheme does not "see" as far as the initial increase.

## 3 Semi-Myopic Voi Estimates

The above pathological example was inspired by a phenomenon we encountered in a real-world problem, optimizing parameter in setups of imaging machines. On data with varying prior beliefs, the myopic scheme almost never measured an item with high prior variance even when it was likely to become the best item after a sufficient number of measurements.

Keeping the complexity manageable (the number of possible sensing plans over continuous variables is uncountably infinite, in addition to being multidimensional) while overcoming the premature termination is the basis for the *semi-myopic* value of information estimate. Consider the set of all possible measurement actions M. Let C be a constraint over sets of measurements from M. In the semi-myopic framework, we consider all possible subsets B of measurents from M that obey the constraint C, and for each such subset B compute a "batch" VOI that assumes that all measurements in B are made, followed by a decision (selection of an item in our case). Then, the batch B∗ with best estimated VOI is chosen. Once the best batch B∗ is chosen, there are still several options:
1. Actually do all the measurements in B∗.

2. Attempt to optimize B∗ into some form of conditional plan of measurements and the resulting observations.

3. Perform the best measurement in B∗.
In all cases, after measurements are made, the selection is repeated, until no batch has a positive net VOI,
at which point the algorithm *terminates* and selects an item. Although we have experimented with option 1 for comparative purposes, we did not further pursue it as empirical performance was poor, and opted for option 3 in this paper1. Observe that the constraint C is crucial. For an empty constraint (called the *exhaustive* scheme), all possible measurement sets are considered.

Note that this has an exponential computational cost, while *still* not guaranteeing optimality. At the other extreme, the constraint is that only singleton sets be allowed, resulting in the greedy single-step assumption, which we call the *pure myopic* scheme.

The myopic estimate can be extended to the case when a single step consists of k ≥ 1 measurements of a single item si. We denote the estimate of such a kmeasurements step by *MV I*k i
. Our main contribution is thus the case where the constraint is that all measurements be for the same item, which we call the blinkered scheme. Yet another scheme we examine is where the constraint allows at most one measurement for each item (thus allowing from zero to n measurements in a batch), called the *omni-myopic* scheme.

## 3.1 Blinkered Value Of Information

As stated above, the blinkered scheme considers sets of measurements that are all for the same item; this constitutes unlimited lookahead, but along a single "direction", as if we "had our blinkers on". That is, the VOI is estimated for any number of independent observations of a single item. Although this scheme has a significant computational overhead over pure-myopic, the factor is only linear in the maximum budget. 2 We define the "blinkered" value of information as:
1Option 2 is intractable in general, and while limited efficient optimization may be possible, this issue is beyond the scope of this paper.

2This complexity assumes either normal distributions, or some other distribution that has compact statistics. For general distributions, sets of observations may provide information beyond the mean and variance, and the resources required to compute VOI may even be exponential in the number of measurements.