Inference and Learning in Dynamic Decision Networks Using Knowledge Compilation

Gabriele Venturato, Vincent Derkinderen, Pedro Zuidberg Dos Martires, Luc De Raedt

Abstract

This paper introduces mapl-cirup, a novel algorithm that utilizes knowledge compilation to transform the Bellman update of a Markov Decision Process (MDP) into a reusable, differentiable arithmetic circuit. By compiling the transition logic once, the approach enables both efficient exact planning and gradient-based learning of reward parameters from observed trajectories. Experimental results on standard benchmarks demonstrate significant reductions in symbolic representation size and the ability to accurately recover reward functions through backpropagation.

Introduction

Decision-making in uncertain, dynamic environments is frequently modeled using Markov Decision Processes (MDPs). While Dynamic Decision Networks (DDNs) provide a compact way to represent these processes, solving them (planning) and learning their parameters from data remains computationally expensive.

Traditional symbolic approaches, such as the SPUDD algorithm, use Algebraic Decision Diagrams (ADDs) to perform value iteration. However, SPUDD must manipulate and recompile these diagrams at every iteration of the algorithm. Furthermore, these traditional symbolic methods are generally not differentiable, making it difficult to learn model parameters, such as rewards or probabilities, directly from data using modern gradient-based optimization.

A Dynamic Decision Network (DDN) illustrating state transitions and reward structures.

Methodology: mapl-cirup

The researchers bridge the gap between symbolic logic and probabilistic planning using Knowledge Compilation (KC). The proposed framework, mapl-cirup, involves several key steps:

  1. Dynamic Decision Circuits (DDCs): The DDN's transition logic, rewards, and utilities are encoded into a propositional logic formula.
  2. Algebraic Model Counting (AMC): This formula is compiled into a circuit. By evaluating this circuit using a specific "Maximum Expected Utility" ($S_{meu}$) semiring, the evaluation becomes equivalent to performing a Bellman update.
  3. Amortized Compilation: Unlike previous methods that re-calculate the symbolic structure at each step, mapl-cirup compiles the transition logic exactly once. During value iteration, it simply re-evaluates the same circuit with updated utility values.
  4. Differentiable Learning: Because the resulting circuit is a directed acyclic graph (DAG) of arithmetic operations (sum, product, and max), it is inherently differentiable. The authors use this property to define a Mean Squared Error (MSE) loss between expected and observed rewards, allowing them to learn unknown reward parameters via backpropagation.
The progression from (a) explicit enumeration to (b) knowledge compilation and finally to (c) an arithmetic circuit.

Evaluation and Results

The authors evaluated their approach on several benchmarks, including standard MDP problems like elevator, coffee, and factory, as well as synthetic cross-stitch and chain structures designed to test scaling.

Key Results

  • Circuit Size: mapl-cirup produces significantly smaller symbolic representations than SPUDD. For the coffee domain, SPUDD's diagram had over 142,000 nodes, while mapl-cirup's circuit had only 2,542.
  • Planning Performance: On the tested benchmarks, mapl-cirup was often faster or competitive with SPUDD in terms of time-to-convergence, despite being implemented in Python versus SPUDD's C++.
  • Learning Accuracy: In the coffee domain, the algorithm successfully learned reward parameters from 100 trajectories, reducing the relative state error from 2.94 down to 0.41.

Discussion

The "aha moment" of this work is the realization that if transition rules are stationary, the logic only needs to be compiled once. This shifts the heavy lifting to an offline phase, making online value iteration much leaner. Furthermore, by treating the Bellman update as a circuit evaluation, planning is no longer a "black box" optimization; it becomes a differentiable program.

Limitations and Future Work

While the circuit represents the transition compactly, the current version of mapl-cirup still explicitly iterates over all states in the outer loop of value iteration, limiting scalability for problems with a very large number of state variables. Future work suggests integrating ADD-like operations directly into the circuit evaluation to handle larger state spaces more natively without losing the benefits of a single compilation step.

Summary updated

Abstract

Decision making under uncertainty in dynamic environments is a fundamental AI problem in which agents need to determine which decisions (or actions) to make at each time step to maximise their expected utility. Dynamic decision networks (DDNs) are an extension of dynamic Bayesian networks with decisions and utilities. DDNs can be used to compactly represent Markov decision processes (MDPs). We propose a novel algorithm called mapl-cirup that leverages knowledge compilation techniques developed for (dynamic) Bayesian networks to perform inference and gradient-based learning in DDNs. Specifically, we knowledge-compile the Bellman update present in DDNs into dynamic decision circuits and evaluate them within an (algebraic) model counting framework. In contrast to other exact symbolic MDP approaches, we obtain differentiable circuits that enable gradient-based parameter learning.
BibTeX
@inproceedings{venturato2024inference,
  author = {Gabriele Venturato and Vincent Derkinderen and Pedro Zuidberg Dos Martires and Luc De Raedt},
  title = {{Inference and Learning in Dynamic Decision Networks Using Knowledge Compilation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30042},
}
Figure