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.
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:
- Dynamic Decision Circuits (DDCs): The DDN's transition logic, rewards, and utilities are encoded into a propositional logic formula.
- 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.
- Amortized Compilation: Unlike previous methods that re-calculate the symbolic structure at each step,
mapl-cirupcompiles the transition logic exactly once. During value iteration, it simply re-evaluates the same circuit with updated utility values. - 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.
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-cirupproduces significantly smaller symbolic representations than SPUDD. For thecoffeedomain, SPUDD's diagram had over 142,000 nodes, whilemapl-cirup's circuit had only 2,542. - Planning Performance: On the tested benchmarks,
mapl-cirupwas 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
coffeedomain, 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