but also much more general schemes such as measurement batching, and exhaustive subset selection at the other extreme. Within this framework we propose the
"blinkered" VOI estimate, a variant of measurement batching, as one that is efficiently computable and yet performs much better than myopic VOI for the selection problem.

The rest of the paper is organized as follows. We begin with a formal definition of our version of the selection problem and other preliminaries. We then examine a pathological case of myopic VOI, and present our framework of semi-myopic VOI. The "blinkered" VOI is then defined as scheme within the framework, followed by theoretical bounds for some simple special cases. Empirical results, comparing different VOI
schemes to blinkered VOI, further support using this cheme in the selection problem. We conclude with a discussion of closely related work.

## 2 Background

We begin by formally defining the selection problem, followed by a description of the standard myopic VOI
approach for solving it.

## 2.1 The Optimization Problem

The selection problem is defined as follows. Given

- A set S = {s1, s2*, ..., s*n} of n items;
- initial beliefs (probability distribution) about item values Bel(S) = p(s1 = x1*, ..., s*n = xn);
- utility function u : *R → R*; - a cost function c : *N → R* defining the cost of a single measurement of item i;
- a budget or maximum allowed number of measurements m; - a measurement model, i.e. a probability distribution of observation outcome given the true value of each item po(y|x);
find a policy that maximizes expected net utility U
net of the selection - utility of the selected item less the cost of the measurements. Although in practice we allow different types of measurements (i.e. with different cost and measurement error model) we assume initially for simplicity that all measurements of an item are i.i.d. given the item value. Thus, if item siis chosen after measurement sequence (M1*, ..., M*m0 ), and the true value of siis xi, the net result U
net is:

$$U^{n e t}=u(x_{i})-\sum_{j=1}^{m^{\prime}}c(M_{j})$$
$$\quad(1)$$

We assume that the posterior beliefs p
+(s1 = x1, s2 =
x2*, ..., s*n = xn|y); and the marginal posterior beliefs p
+(si = x|y) about an item value can be computed efficiently. More specifically, we usually represent the distribution using a structured probability model, such as a Bayes network or Markov network. The assumption is that either the structure or distribution of the network is such that belief updating is easy, that the network is sufficiently small, or that the network is such that an approximate and efficient belief-updating algorithm (such as loopy belief updating) provides a good approximation. Observe that this assumption does not make the selection problem tractable, as even in a chain-structured network the selection problem is NP-hard [8]. In fact, even when assuming that the beliefs about items are independent (as we will do for much of the sequel), the problem is still hard.

## 2.2 Limited Rationality Approach

In its most general setting, the selection problem can be modeled as a (continuous state) indefinite-horizon POMDP [1], which is badly intractable. Following [9],
we thus use a greedy scheme that:

- Chooses at each step a measurement with the greatest value of information (VOI), performing belief updating after getting the respective observation,
- stops when no measurement with a positive VOI
exists, and
- selects item sα with the greatest expected utility:

$$E(U_{\alpha})=\int\limits_{-\infty}^{\infty}p_{\alpha}(x)u(x)d x$$
$$\left(2\right)$$

VOI of a measurement Mj is defined as follows: denote by E(U
j+
i) the expected net utility of item si after measurement j and a subsequent optimal measurement plan. Let sα− be the item that currently has the greatest expected net utility E(Uα− ). Likewise, let sαj+ be the item with the greatest expected utility E(U
j+
αj+ ) *after* a measurement plan beginning with observation j. Then:

$$V O I(M_{j})=E\left(U_{\alpha^{j+}}^{j+}\right)-E\left(U_{\alpha^{-}}^{j+}\right)\qquad\quad(3)$$
