Efficient deterministic approximation algorithms for non-myopic value of information in graphical models

Abstract — Agents operating in the real world need to handle both uncertainty and resource constraints. Typical problems in this domain are optimization of sequences of observations, and optimal allocation of computation tasks during reasoning and search (also known as meta-reasoning). In both domains, a crucial issue is value of information, a quantity hard to compute in general, and thus usually estimated using severe assumptions, such as myopic and independence of information sources. This paper extends recent work on nonmyopic value of information in graphical models, that assumed a chain-shaped graph and exact measurements. Suitably relaxing the assumption of exact measurements still allows for a provably close approximation of the optimal subset (of observations) selection, and for approximating the optimal conditional plan. The method is shown to be efficient and to provide a significant advantage in expected reward over the myopic and greedy value of information scheme. I