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.

Coarse data, Incomplete observations, Minimax decision making, Maximum entropy
Lecture Notes in Computer Science
European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty
Centrum Wiskunde & Informatica, Amsterdam, 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