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. First-order Markov decision processes compute policies on a first-order level. Probabilistic relational models have been extended with actions and utilities to support decision making. Even multi-agent 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 single-agent setting as well as offline decision making in the multi-agent 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

  • Marcel Gehrke
  • Nazlı Nur Karabulut
  • Florian Marwitz
  • Tanya Braun

• Target Audience, Prerequisite Knowledge, and Learning Goals

  The tutorial will be mostly self-contained. 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 two-fold:

  1. to provide an overview of recent developments in probabilistic relational modelling as well as correspondences to decision making and

  2. to discuss interesting outcomes of the combination of StaRAI and decision making as well as new directions for investigation.

• Agenda (preliminary)

  1. Introduction [Marcel]
     1. Relational models under uncertainty
     2. Probabilistic inference and decision making
  2. Online Decision Making [Tanya]
     1. Lifted inference in episodic decision-theoretic models
     2. Temporal extensions
  3. Offline decision making [Florian]
     1. Lifting factored Markov decision processes
     2. First-order Markov decision processes
  4. Multi-agent decision making [Nazlı]
     1. Lifting decentralised partially observable Markov decision processes
     2. Lifting partially observable stochastic games
  5. Summary [Marcel]

  Slides will be linked here once they are available.

• 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 ECAI-20 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 (ECSQARU-23). 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. First-order Probabilistic Inference. In IJCAI-03 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 First-order MDPs. In Artificial Intelligence Journal, 2005
  • Scott Sanner and Kristian Kersting. Symbolic Dynamic Programming for First-order POMDPs. In AAAI-10 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 Decision-Theoretic Probabilistic Prolog. In AAAI-10 Proceedings of the 24th AAAI Conference on Artificial Intelligence, 2010