
$$\mathbf{x}\,M V I^{k}$$

Driven by this estimate, the blinkered scheme selects a single measurement of the item where *some* number of measurements gain the greatest VOI. A single step is expected not to achieve the value, but to be just the first one in the right direction. Thus, the estimate relaxes the *single-step* assumption, while still underestimating the value of information. For finite budget m the time to compute the estimate T*BV I* is: TBV I = O (T*MV I*m). If *MV I*kis a unimodal function of k, which can be shown for some forms of distributions and utility functions, the time is only logarithmic in m using bisection search.

## 3.2 Theoretical Bounds

We establish bounds on the blinkered scheme for two special cases, beginning with the termination condition for the case of only 2 items.

Theorem 1. Let S = {s1, s2}, where the value of s1 is known exactly. Let mb *be the remaining budget of measurements when the blinkered scheme terminates, and* C *be the (positive) cost of each measurement. Then the* (expected) value of information that can be achieved by an optimal policy from this point onwards is at most mbC.

Proof. The intrinsic value of information of the remaining budget when the blinkered scheme terminates is V
int b ≤ mbC, since otherwise it would not have terminated. Since there is only one type of measurement, the intrinsic value of information V
int o achieved by an optimal policy must be at most equal to making all the measurements, thus V
int o ≤ V
int b ≤ mbC. Since measurement costs are positive, the net value of information V
net o achieved by the optimal policy must therefore also be at most mbC.

This bound is asymptotically tight. This can be shown by having a measurement model with dependencies such that the first measurements do not change the expected utilities of the item, but provide information on whether it is worthwhile to perform additional measurements.

The second bound is related to a common case of a finite budget and free measurements. It provides certain performance guarantees for the case when dependencies between items are sufficiently weak.

Definition. Measurements of two items s1, s2 are mutually submodular if, given sets of measurements of each item M1 and M2*, the intrinsic value of information of the union of the set is not greater than the*

$\left(7\right)$. 
sum of the intrinsic values of each of the sets, i.e.:
V
int(M1 ∪ M2) ≤ V
int(M1) + V
int(M2)
Theorem 2. For a set of n *items, measurement cost* C = 0, and a finite budget of m measurements, if measurements of every two items are mutually submodular, the value of information collected by the blinkered scheme is no more than a factor of n *worse than the* value of information collected by an optimal measurement plan.

Proof. Since the measurement cost is 0, V
net = V
int, we omit the superscript in the proof. Expected value of information cannot decrease by making additional measurements, therefore the value of any set of measurements containing the set of measurements in an optimal plan is at least as high as the value Vo of an optimal plan. Consider an exhaustive plan containing m measurements of each of the n items, mn measurements total with value Ve. The exhaustive plan contains all measurements that can be made by optimal plan within the budget, thus Vo ≤ Ve.

Let si be the item with the highest blinkered value for m measurements, denote its value by V*bimax* = maxi Vb,i. Since measurements of different items are mutually submodular, Ve ≤ nV*bimax*, and thus V*bimax* ≥
Vo n
.

The blinkered scheme selects at every step a measurement from a plan with value of information which is at least as high as the value of measurements of si for the rest of the budget. Thus, its value of information Vb ≥ V*bimax* ≥
Vo n
.

The bound is asymptotically tight. Construct a problem instance as follows: n items, with expected values of information vj (i), for i measurements, respectively, defined below. Value of information of a combination of the measurements is the sum of the values for each item, v(i) = Pn j=1 vj (ij ), with the following value of information functions:

$$v_{1}(i)={\sqrt[k]{\frac{i}{m}}}$$  $$v_{j>1}(i)={\left\{\begin{array}{l l}{0}&{{\mathrm{~if~}}i<{\frac{m}{n}}}\\ {{\sqrt[k]{\frac{1}{n}}}}&{{\mathrm{~otherwise~}}}\end{array}\right.}$$

Here, the optimal policy is to measure each item m n times. The resulting value of information for m measurements is:

$$V_{o}=v_{1}\left({\frac{m}{n}}\right)+(n-1)v_{j>1}\left({\frac{m}{n}}\right)=n{\sqrt[k]{\frac{1}{n}}}$$
