Value of Information under Imprecise Probabilities: Decision-Rule-Specific Values and Fixed-Measure Envelopes on a Credal Set
Authors: Rowan Iskandar
Organizations: Medtronic Trading Sàrl, Tolochenaz, VD, Switzerland · Center for Evidence Synthesis in Health, Brown University School of Public Health, Providence, RI, USA
Abstract
Value-of-information (VOI) analysis is usually conducted under a single probability measure. However, in practice, the available evidence often pins the measure down only to a set. Consequently, under a set of probability measures, VOI requires different formulations. First, we explicate a rule-specific VOI that fixes a decision rule for acting under imprecision (such as Gamma-maximin) and measures what the information is worth to a decision maker who uses that rule. Second, we derive a fixed-measure envelope that evaluates the classical VOI functional over all admissible precise measures. We formalize this distinction and explicate its consequences for the expected perfect, partial, and sample information. The expected value of perfect information is concave over the credal set. Hence, when the set is generated by finitely many measures, its lower envelope endpoint is obtained exactly from the generators, while its upper endpoint may be interior and is computed by a finite linear program. The Gamma-maximin value, in contrast, can exceed the entire envelope, so a rule-specific value is not recovered from the envelope's endpoints. A continuity bound limits how much the VOI can change as the measure varies, and we identify when the partial- and sample-information endpoints can still be obtained from the generators. Because the single-measure VOI must itself be estimated, the procedure we give combines standard estimators for it with a search over the credal set. By using a worked decision problem, we show how the two quantities separate conclusions that hold across every admissible measure from conclusions that depend on one unidentified choice of measure.
Many algorithms spend an internal resource before returning a decision and are evaluated only by the quality of that terminal output. We formalize such procedures as terminal computation-allocation problems: costly computations produce observations, update beliefs about a latent environment, and matter only through terminal decision loss. Bellman equations characterize optimal allocation under fixed budgets, priced computation, and exact certification. We then relate value of computation (VOC) to information. Mutual information equals myopic VOC under log loss, whereas under simple regret VOC is a knowledge-gradient quantity; moreover, information gain can rank computations arbitrarily poorly, although it gives a one-sided upper bound on VOC. Bandit pulls, tree simulations, and node expansions illustrate the same model under different computation topologies. Finally, under an explicit frontier-resolution and heuristic-error model, maximizing approximate VOC recovers weighted A*, with A* and greedy best-first search as limiting cases. The theory identifies a shared decision problem without asserting that one acquisition rule is universally optimal.
Many signal processing systems ultimately exist to {act}. Whenever the state variable that determines the action to be taken by a decision maker, or agent, is uncertain, the way that uncertainty is represented decides how well the agent performs and how much its performance can be trusted. This lecture note develops, from first principles and within a single decision-theoretic setting, the link between the {objective} and the knowledge of an agent and the form of uncertainty representation that is sufficient to act optimally. To start, assuming a known environment distribution, we show that a risk-neutral agent needs the posterior distribution over the state, whereas a risk-averse agent can rely without loss of optimality on a {prediction set} and a worst-case decision rule. We then turn to the case in which the environment is unknown, and identify three complementary approaches to address the resulting epistemic uncertainty: calibration of a fixed predictor, credal (ambiguity) sets with distributionally robust optimization, and Bayesian inference over model parameters. The common thread is that reliable decisions require an uncertainty representation matched to the decision objective and to the knowledge profile of the agent, together with a guarantee that certifies the utility the agent will actually obtain.
We introduce Bellman-sufficient information complexity for minimax analysis of sequential decision problems. A Bellman-sufficient state retains enough of the history to close the controlled recursion, while an index Y=χ(Ω) specifies the decision-relevant information being charged. The upper bound is a log-penalized Bellman program; the lower bound is a Bellman--Fano comparison along an algorithm-dependent reference trajectory. If the two values match at a common localization scale and the stated admissibility, calibration, and growth conditions hold, they form an information-risk sandwich. UCB, E2D, and AMS/EBO control or relax the upper Bellman bracket in different ways. For the main application, we give a negative answer to a widely studied form of the GP--UCB minimax-optimality question. For every 0<α<1/4, we construct one bounded continuous kernel whose minimax regret is Θ(T1−α) along an infinite sequence of horizons, while two globally calibrated GP--UCB rules incur linear regret under one fixed truth. An epochwise finite-marginal action-index AIR Bellman policy, implemented through robust AIR/AMS/EBO control, attains the minimax order. The construction separates realized information from the cost of uniform optimism: many low-value directions inflate the exploration multiplier and change the trajectory. Through the canonical RKHS feature map, it also yields a finite-horizon polynomial minimax separation for the specified maximal-information-calibrated LinUCB rule. A reproducible experiment illustrates the mechanism.