Affiliations: Computer Science Department, Ben Gurion University of the Negev, Beer-Sheva, Israel | [x] University of Coimbra and INESC Coimbra, Coimbra, Portugal | [y] Royal Academy of Sciences, Madrid, Spain
Abstract: Computing value of information (VOI) is a crucial task in various aspects of decision-making under uncertainty, such as in meta-reasoning for search; in selecting measurements to make, prior to choosing a course of action; and in managing the exploration vs. exploitation tradeoff. Since such applications typically require numerous VOI computations during a single run, it is essential that VOI be computed efficiently. We explore the tradeoff between the accuracy of estimating VOI and computational resources used for the estimation, and extend the known greedy algorithm with selective estimation of VOI based on principles of limited rationality. As a case study, we examine VOI estimation in the measurement selection problem. Empirical evaluation of the proposed extension in this domain shows that computational resources can indeed be significantly reduced, at little cost in expected rewards achieved in the overall decision problem.
Keywords: Search, metareasonling, value of information, sequential decision making
