Efficient algorithms for minimax decisions under tree-structured incompleteness
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|
|Organisation||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