Learning and reasoning in large, structured, probabilistic worlds is at the heart of artificial intelligence. Markov decision processes have become the de facto standard in modeling and solving sequential decision making problems under uncertainty. Many efficient reinforcement learning and dynamic programming techniques exist that can solve such problems. Until recently, the representational state-of-the-art in this field was based on propositional representations.