Scaling Decision-Theoretic Probabilistic Programs Through Factorization
We present dappl, a new probabilistic programming language to model decision making and exactly solve maximum expected utility problems (MEU). dappl is a functional language with support for first-class decision-making, rewards, and probabilistic uncertainty. Our goal in designing dappl is to (1) support scalable MEU reasoning, and (2) provide a flexible and expressive programming environment capable of representing complex real-world decision-making tasks. To accomplish these two goals we develop a new reasoning-via-compilation strategy for dappl. We reduce dappl MEU computation to a flexible branch-and-bound algorithm over compiled Boolean formulas weighted by the expectation semiring, then prove this reduction correct with respect to a denotational semantics. Furthermore, we demonstrate that our language is as expressive as known decision–theoretic probabilistic graphical models such as influence diagrams.