Algorithm 1 Greedy measurement selection 1: *budget* ← C
2: Initialize beliefs 3: loop 4: for all items si do 5: Compute E(Ui)
6: for all measurements mj do 7: if cj ≤ *budget* then 8: Compute Vj 9: else 10: Vj ← 0 11: jmax ← arg max jVj 12: if Vjmax > 0 then 13: Perform measurement mjmax ; Update beliefs; budget ← *budget* − cjmax 14: else 15: break 16: α ← arg max j E(Ui)
17: return sα measurements, the value of information of most measurements is unlikely to change abruptly due to just one other measurement results. With an appropriate uncertainty model, it can be shown that the VOI of only a few of the measurements must be recomputed after each measurement, thus decreasing the computation time and ensuring that the greedy algorithm exhibits a more rational behavior w.r.t. computational resources.

## 3 Rational Computation Of Value Of Information

For the selective VOI recomputation, the belief BEL(Λj ) about the intrinsic value of information of measurement mj is modeled by a normal distribution with variance ς 2 j
:

$$\mathrm{BEL}(\Lambda_{j})={\mathcal{N}}(\Lambda_{j},\varsigma_{j}^{2})$$
) (4)
After a measurement is performed, and the beliefs about the item features are updated (line 13 of Algorithm 1), the belief about Λj becomes less certain. Under the assumption that the influence of each measurement on the value of information of other measurements is independent of influence of any other measurement, the uncertainty is expressed by adding Gaussian noise with variance τ 2 to the belief:
ς 2 j ← ς 2 j + τ 2(5)
When Λj of measurement mj is computed, BEL(Λj ) becomes exact (ς 2 j ← 0). At the beginning of the algorithm, the beliefs about the intrinsic value of information of measurements are computed from the initial beliefs about item features. In the algorithm that recomputes the value of information selectively, the initial beliefs about the intrinsic value of information are computed immediately after line 2 in Algorithm 1, and lines 6–
11 of Algorithm 1 are replaced by Algorithm 2. While the number of iterations in lines 7–12 of Algorithm 2 is the same as in lines 6–10 of Algorithm 1, Wk is efficiently computable, and the subset of measurements for which the value of information is computed in line 15 of Algorithm 2 is controlled by the computation cost cV :

$$W_{k}=\frac{\varsigma_{k}}{\sqrt{2\pi}}e^{\left(-\frac{(V_{\gamma}-V_{k})^{2}}{2\varsigma_{k}^{2}}\right)}-|V_{\gamma}-V_{k}|\,\Phi\left(-\frac{|V_{\gamma}-V_{k}|}{\varsigma_{k}}\right)-c_{V}$$
$$(6)$$
