
## 2 The Measurement Selection Problem

As our case study, we examine the following optimization problem. Given:
- A set of Ns items S = {s1, s2*, . . . , s*Ns }.

- A set of Nf item features Z = {z1, z2*, . . . , z*Nf
}. (Each feature zi has a domain D(zi).)
- A joint distribution over the features of the items in S. That is, a joint distribution over the random variables {z1(s1), z2(z1), . . . , z1(s2), z2(s2)*, . . .*}.

- A set of measurement types M = {(c, p)k k ∈ 1..Nm}, with potentially different intrinsic measurement cost c and observation distribution p, conditional on the true feature values, for each measurement type.

- A utility function u(z): R
Nf → R on features. In the simplest case, there is just one realvalued feature, acting as the item's utility value, and u is simply the identity function.

- A measurement budget C.
Find a policy of measurement decisions and a final selection that maximize the expected net utility of the selection (the expected reward):

$$\max\!:\!R=u({\bf z}(s_{\alpha}))-\sum_{i=1}^{N_{q}}c_{k_{i}}\quad\mbox{s.t.}:\sum_{i=1}^{N_{q}}c_{k_{i}}\leq C\tag{1}$$

where Q = {(ki, si) i ∈ 1..Nq} is the performed measurement sequence and sα is the selected item. A next measurement is selected on-line, after the outcomes of all preceding measurements are known.

The above selection problem is intractable, and is therefore commonly solved approximately using a greedy heuristic algorithm. The greedy algorithm selects a measurement mjmax with the greatest net value of information Vjmax . The *net value of information* is the difference between the intrinsic value of information and the measurement cost.

$$V_{j}=\Lambda_{j}-c_{k_{j}}$$
$$\left({\mathfrak{3}}\right)$$
Vj = Λj − ckj(2)
The *intrinsic value of information* Λj is the expected difference in the true utility of the finally selected item sα after and before the measurement.

$$\Lambda_{j}=\mathbb{E}(\mathbb{E}[u(\mathbf{z}(z_{\alpha^{j}}))]-\mathbb{E}[u(\mathbf{z}(s_{\alpha}))])$$
Λj = E(E[u(z(zαj ))] − E[u(z(sα))]) (3)
Exact computation of Λj is intractable, and various estimates are used, including the myopic estimate [Russell and Wefald, 1991] and semi-myopic schemes [Tolpin and Shimony, 2010].

The pseudocode for the algorithm is presented as Algorithm 1. At each step, the algorithm recomputes the value of information estimate of every measurement. The assumptions behind the greedy algorithm are justified when the cost of selecting a next measurement is negligible compared to the measurement cost. However, optimization problems with hundreds and thousands of items are common [Tolpin and Shimony, 2010]; and even if the value of information of a single measurement can be computed efficiently [Russell and Wefald, 1989], the cost of estimating the value of information of all measurements becomes comparable to and outgrows the cost of performing a measurement.

Recomputation of the value of information for every measurement is often unnecessary, especially when using the "blinkered" scheme [Tolpin and Shimony, 2010], a greedy algorithm which attempts to also compute VOI for *sequences* of measurements of the same type. When there are many different