  Existing decision-theoretic reasoning frameworks such as decision networks
use simple data structures and processes. However, decisions are often made
based on complex data structures, such as social networks and protein
sequences, and rich processes involving those structures. We present a
framework for representing decision problems with complex data structures using
probabilistic programming, allowing probabilistic models to be created with
programming language constructs such as data structures and control flow. We
provide a way to use arbitrary data types with minimal effort from the user,
and an approximate decision-making algorithm that is effective even when the
information space is very large or infinite. Experimental results show our
algorithm working on problems with very large information spaces.
