2019-09-18
Efficient algorithms for minimax decisions under tree-structured incompleteness
Publication
Publication
Presented at the
European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (September 2019), Belgrade, Serbia
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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/978-3-030-29765-7_28 | |
| Lecture Notes in Computer Science | |
| European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
van Ommen, T., Koolen-Wijkstra, W., & Grünwald, P. (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 |
|
