When decisions must be based on incomplete (coarsened) observations and the coarsening mechanism is unknown, a minimax approach offers the best guarantees on the decision maker’s expected loss. Recent work has derived mathematical conditions characterizing minimax optimal decisions, but also found that computing such decisions is a difficult problem in general. This problem is equivalent to that of maximizing a certain conditional entropy expression. In this work, we present a highly efficient algorithm for the case where the coarsening mechanism can be represented by a tree, whose vertices are outcomes and whose edges are coarse observations.

, , ,
Lecture Notes in Computer Science
European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty
Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands

van Ommen, M, Koolen-Wijkstra, W.M, & Grünwald, P.D. (2019). Efficient algorithms for minimax decisions under tree-structured incompleteness. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 336–347). doi:10.1007/978-3-030-29765-7_28