🤖 AI

dtControl2+ $\varepsilon$ : Trading Optimality for Explainability in MDPs via Decision Trees

This paper introduces dtControl2+ $\varepsilon$ , an extension of the state-of-the-art tool dtControl2 that generates significantly smaller and more human-comprehensible decision tree controllers for Markov decision processes by trading a controllable amount of optimality ( $\varepsilon$ ) for enhanced explainability.

Original authors: Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, Maximilian Weininger

Published 2026-07-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, Maximilian Weininger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to navigate a maze. In the world of computer science, this is called "controller synthesis." You give the robot a set of rules and a goal, and a computer program figures out the perfect moves to get there. But here's the catch: for complex mazes, the computer often spits out a massive, messy list of instructions—one for every single square the robot might ever land on. It's like having a cookbook with a million pages, where every page just says "turn left" or "turn right" for a specific, tiny moment. While this list is mathematically perfect, it's impossible for a human to read, let alone understand. If the robot crashes, no one can look at that giant list and say, "Ah, I see, it turned left because it was confused about the red wall." We need these instructions to be short, simple, and explainable, like a clear map rather than a giant spreadsheet.

This is where "decision trees" come in. Think of a decision tree as a flowchart or a game of "20 Questions." Instead of a giant list, you have a simple structure: "If the wall is on the left, go right; otherwise, go straight." These are much easier for humans to understand. However, even these trees can get too big and complicated if the robot faces tricky situations or rare "corner cases." The big question researchers are asking is: Can we make these trees even smaller and simpler without making the robot crash? The answer lies in a concept called "epsilon-optimality." Imagine you tell the robot, "You don't have to be 100% perfect; you can be 99.9% perfect." This tiny bit of allowed imperfection gives the robot (and the computer) the freedom to ignore tiny, unlikely details, resulting in a much shorter, cleaner set of instructions that still gets the job done safely.

The paper "dtControl2+ε: Trading Optimality for Explainability in MDPs via Decision Trees" introduces a new tool called dtControl 2+ε that does exactly this. The researchers, working with Markov Decision Processes (a fancy math way of describing systems with randomness, like a robot that might slip on a wet floor), have built a system that takes a complex, perfect controller and shrinks it down into a tiny, human-readable decision tree. They do this by allowing a tiny, controlled amount of error (called $\epsilon$ ).

Here is how their magic works: Instead of trying to explain every single move the robot makes, the tool looks at the map and asks, "Which moves actually matter?" If a robot is in a spot where it will almost certainly never go, or where any move it makes leads to the same result, the tool says, "Let's skip explaining that part." It distills the controller down to its "essence." For example, in a test with a robot on a hillside, the perfect controller had dozens of complex rules. The new tool, allowing a tiny error of just 0.001, reduced the instructions to just five nodes (the decision points in the tree). The resulting rule was beautifully simple: "Go up to the top, go right to the edge, then go down." It wasn't mathematically perfect in every single microscopic scenario, but it was so close to perfect that the difference was negligible, and it was something a human could understand in seconds.

The team tested their tool against other state-of-the-art methods and found it to be a massive improvement. In many cases, their tool produced decision trees that were orders of magnitude smaller than the competition. In fact, for nearly half of the test cases they ran, allowing a small error of $\epsilon = 10^{-2}$ (0.01) allowed them to shrink the entire controller down to a single node. This means the robot could just pick one main action and, if that action wasn't possible, pick any other available move at random, and it would still be almost as good as the perfect, complex strategy. This is a fact that previous tools missed entirely.

The researchers are careful to note that they didn't just guess; they used a powerful model checker (a tool that mathematically verifies if a system works) to double-check every simplified tree. They proved that even with these aggressive simplifications, the robot's performance never drops below the allowed safety limit. They also showed that their tool works on various types of goals, not just reaching a destination, but also avoiding danger or collecting rewards.

In short, this paper presents a way to trade a tiny, controllable amount of mathematical perfection for a huge gain in human understanding. By letting the computer admit it doesn't need to explain every single tiny detail, the researchers have created controllers that are not only safe and effective but also small enough to fit on a postcard and simple enough for a human to explain to a friend. It turns a confusing, million-page instruction manual into a clear, three-step guide.

Technical Summary: dtControl2+ε: Trading Optimality for Explainability in MDPs via Decision Trees

Problem Statement

Controller synthesis for Markov Decision Processes (MDPs) often yields optimal controllers represented as large, unstructured state-action tables. While these tables are mathematically precise, they are impractical for implementation on resource-constrained devices and lack explainability, hindering validation and certification. Existing tools, such as dtControl2, attempt to represent these controllers as Decision Trees (DTs) to improve interpretability. However, for large systems or those with many corner cases, even these DTs can become too complex for human comprehension.

A critical challenge is that reducing DT size is non-trivial; removing a single crucial decision can render a controller incorrect. Furthermore, many scalable synthesis methods only provide $\epsilon$ -optimal controllers (performance within $\epsilon$ of the optimal value), yet existing DT construction tools typically aim for exact ( $\epsilon=0$ ) representation, failing to leverage the allowed imprecision to simplify the explanation.

Methodology

The paper presents dtControl2+ε, a tool that extends the state-of-the-art dtControl2 by introducing an " $\epsilon$ " functionality. The core workflow integrates tightly with the probabilistic model checker Storm to construct smaller, explainable DTs while guaranteeing that the resulting controller remains $\epsilon$ -optimal.

The methodology proceeds in three main steps:

1. Model Solving and Dataset Construction

Instead of starting with a deterministic optimal controller, the tool generates an initial dataset that is permissive (mapping states to sets of allowed actions) or combined (restricting permissive actions to reachable states).

Permissive Strategies: The tool identifies actions that are optimal or yield the same value, allowing the DT to "unify" states.
Reduction Heuristics: Before learning the DT, the tool identifies and removes states where the specific choice of action does not impact the outcome or where the error introduced is bounded by $\epsilon$ $ϵ$ . Key reduction techniques include:
- AllOpt: Removing states where all available actions are optimal.
- Agency: Removing states where the difference between the best and worst possible outcomes is less than $\epsilon$ .
- Dominance: Removing states that are almost surely reached from other states regardless of the choice made.
- Unreach: Removing states unreachable from the initial state under any consistent controller.

2. Decision Tree Learning

The tool employs a modified version of the standard heuristic-based DT construction algorithm (Algorithm 1) with several enhancements:

Predicate Extraction: Automatically extracts relevant predicates from the high-level model description (e.g., PRISM language transition guards), improving upon the semi-automatic template approach of previous tools.
Impurity Measures: Introduces model-specific weighting for impurity calculations. Instead of uniform weighting, it uses:
- Imp_Simulation: Weights states by visit frequency (with a safety floor to ensure $\epsilon$ -optimality).
- Imp_Agency: Weights states by their agency (potential error).
- Imp_CoE (Cost of Error): Weights states by the impact of choosing the worst action in that specific state.
Aggressive Heuristics with Verification: The tool employs Early-Stopping (terminating splits when impurity is below a threshold) and Greedy Pruning (collapsing subtrees). Unlike previous "aggressive" approaches that risked soundness, dtControl2+ε uses Storm to verify the $\epsilon$ -optimality of the resulting tree after these steps. If the precision constraint is violated, the tool relaxes the heuristics and retries.

3. Verification Loop

A unique feature is the tight coupling with Storm for post-construction verification. The tool checks the precision of the generated DT. If the deviation from the optimal value exceeds $\epsilon$ , it backtracks and reduces the aggressiveness of the heuristics (e.g., increasing the stopping threshold or disabling pruning), ensuring the final output is guaranteed to be $\epsilon$ -optimal.

Key Contributions

The dtControl2+ε Tool: A self-contained tool that extends dtControl2 to construct smaller DTs by exploiting allowed imprecision $\epsilon$ .
Safe vs. Aggressive Heuristics: A framework that cleanly separates "safe" reductions (which preserve $\epsilon$ -optimality by definition) from "aggressive" heuristics (which are validated via model checking).
Automatic Predicate Extraction: A method to derive decision predicates directly from the model's transition guards, removing the need for manual domain expertise in predicate selection.
Support for Diverse Objectives: The approach covers standard objectives (reachability, safety, reach-avoid, reward-based) and, uniquely, supports Linear Temporal Logic (LTL) properties by handling memory-based controllers.

Results

The authors evaluated dtControl2+ε against dtControl2, dtPaynt, dtNESt, and a reimplementation of the CAV15 approach on 38 benchmarks (including PRISM models with up to 500,000 states).

Size Reduction: Even for exact representation ( $\epsilon=0$ ), dtControl2+ε produces DTs orders of magnitude smaller than dtControl2 due to improved initial datasets and safe heuristics.
Impact of $\epsilon$ : When allowing $\epsilon = 10^{-2}$ , the tool produced single-node DTs for nearly half of the benchmarks, revealing that a single action (with uniform random fallback) is often sufficient for $\epsilon$ -optimality.
Comparison:
- vs. dtControl2: dtControl2+ε consistently produces smaller trees.
- vs. dtPaynt: dtPaynt timed out on most benchmarks and produced larger trees where it succeeded.
- vs. dtNESt: dtNESt is a strong competitor for $\epsilon=0$ , but dtControl2+ε produces trees at most half the size in 23 of 38 benchmarks and an order of magnitude smaller in 10. Notably, dtNESt often fails or produces larger trees when $\epsilon > 0$ , whereas dtControl2+ε excels at exploiting imprecision.
Scalability: The tool solved all but one benchmark within a 20-minute timeout, demonstrating feasibility on large, complex models.

Significance

The paper claims that dtControl2+ε represents a significant advancement in the state of the art for explainable controller synthesis. By trading a controllable amount of optimality for compactness, the tool enables the generation of human-comprehensible controllers that were previously too complex to interpret. The ability to automatically derive structural insights (e.g., identifying that a single rule suffices for $\epsilon$ -optimality) and to support LTL properties distinguishes it from existing tools. The authors emphasize that their approach provides guarantees of $\epsilon$ -optimality, unlike previous heuristic-based pruning methods that could compromise correctness.