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. However, it is hard to imagine a truly general, intelligent system that does not conceive of the world in terms of objects and their properties and relations to other objects. To this end, this book studies lifting Markov decision processes, reinforcement learning and dynamic programming to the first-order (or, relational) setting. Based on an extensive analysis of propositional representations and techniques, a methodological translation is constructed from the propositional to the relational setting. Furthermore, this book provides a thorough and complete description of the state-of-the-art. It surveys vital, related historical developments and contains extensive descriptions of several new model-free and model-based solution techniques.