Exploiting Structure in Decision Making under the Lens of Recent Advances in StaRAI
A tutorial by Marcel Gehrke, Nazlı Nur Karabulut, Florian Marwitz, and Tanya Braun at KI 2024
Introduction
The world surrounding us is inherently uncertain and relational. To account for both in probabilistic graphical models, the field of Statistical Relational AI (StaRAI) has emerged. StaRAI explicitly encodes objects and relations in probabilistic models, which enables algorithms to exploit repeated structures for efficiency gains during inference.
Probabilistic modelling and inference is also at the heart of decision making. For example, when changing the state of an environment through an action, probabilistic inference is performed to predict the effect of the action. Given the intricacies between probabilistic inference and decision making, they suffer from similar problems. E.g., given a naive representation, the state space can explode, i.e., the representation is ex ponential w.r.t. the number of objects in the state and the features to describe them. One way to deal with this problem is factorisation. Here, decision making adapted ideas of probabilistic inference. For example, factored Markov decision processes aim to factorise components of a Markov decision process, a standard formalism to represent a decision making problem. Some approaches also try to identify equivalent states to compactify the underlying representation even further. StaRAI also compactifies probabilistic re lation models by exploiting symmetries emerging from having indistinguishable objects in an environment. There are also already formalisms combining StaRAI and decision making. Firstorder Markov decision processes compute policies on a firstorder level. Probabilistic relational models have been extended with actions and utilities to support decision making. Even multiagent systems have been extended with methods of StaRAI and it has been investigated under which circumstances underlying symmetries can be exploited.
Therefore, this tutorial provides a look at recent advances in decision making within the realm of StaRAI, looking at online and offline decision making the singleagent setting as well as offline decision making in the multiagent setting applying techniques from the field of StaRAI.
Presenters
A collaborative effort between members of the University of Hamburg and the University of Münster
Target Audience, Prerequisite Knowledge, and Learning Goals
The tutorial will be mostly selfcontained. While we assume familiarity with probabilistic graphical models, like Bayesian networks, and Markov decision processes, we will revisit all necessary definitions. The tutorial is therefore potentially interesting for all researchers interested in decision making under uncertainty.
The goal of this tutorial is twofold:
 to provide an overview of recent developments in probabilistic relational modelling as well as correspondences to decision making and

to discuss interesting outcomes of the combination of StaRAI and decision making as well as new directions for investigation.
Agenda (preliminary)
 Introduction [Marcel]
 Relational models under uncertainty
 Probabilistic inference and decision making
 Online Decision Making [Tanya]
 Lifted inference in episodic decisiontheoretic models
 Temporal extensions
 Offline decision making [Florian]
 Lifting factored Markov decision processes
 Firstorder Markov decision processes
 Multiagent decision making [Nazlı]
 Lifting decentralised partially observable Markov decision processes
 Lifting partially observable stochastic games
 Summary [Marcel]
Slides will be linked here once they are available.
 Introduction [Marcel]
Related Publications
 Tanya Braun, Marcel Gehrke, Florian Lau, and Ralf Möller. Lifting in multi agent systems under uncertainty. In 38th Conference on Uncertainty in Artificial Intelligence (UAI 2022), 2022
 Marcel Gehrke, Tanya Braun, Ralf Möller, Alexander Waschkau, Christoph Strumann, and Jost Steinhäuser. Lifted Maximum Expected Utility. In Artificial Intelligence in Health, 2019
 Marcel Gehrke, Tanya Braun, and Ralf Möller. Lifted Temporal Maximum Expected Utility. In Proceedings of the 32nd Canadian Conference on Artificial Intelligence, Canadian AI 2019. Springer, 2019
 Marcel Gehrke, Ralf Möller, Tanya Braun: Taming Reasoning in Temporal Probabilistic Relational Models. In ECAI20 Proceedings of the 24th European Conference on Artificial Intelligence, 2020.

Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman: Efficient Solution Algorithms for Factored MDPs. In Journal of Artificial Intelligence Research, 2003.
 Florian Andreas Marwitz, Ralf Möller, and Marcel Gehrke. PETS: Predicting Efficiently using Temporal Symmetries in Temporal PGMs. In Proceedings of the Seventeenth European Conference on Symbolic and Quantitative Ap proaches to Reasoning with Uncertainty (ECSQARU23). Springer, 2023
 Aniruddh Nath and Pedro Domingos. A Language for Relational Decision Theory. In Proceedings of the International Workshop on Statistical Relational Learning, 2009
 David Poole. Firstorder Probabilistic Inference. In IJCAI03 Proceedings of the 18th International Joint Conference on Artificial Intelligence, 2003
 Matthew Richardson and Pedro Domingos. Markov Logic Networks. In Machine Learning, 2006
 Scott Sanner and Craig Boutilier. Practical Solution Techniques for Firstorder MDPs. In Artificial Intelligence Journal, 2005
 Scott Sanner and Kristian Kersting. Symbolic Dynamic Programming for Firstorder POMDPs. In AAAI10 Proceedings of the 24th AAAI Conference on Artificial Intelligence, 2010
 Guy Van den Broeck, Ingo Thon, Martijn van Otterlo, and Luc De Raedt. DTProbLog: A DecisionTheoretic Probabilistic Prolog. In AAAI10 Proceedings of the 24th AAAI Conference on Artificial Intelligence, 2010