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

2026/07/28 by Tereza Kinská, Jan Křetínský, Tobias Meggendorfer +2
#cs.AI

paper · pdf

Abstract

Over the past decade, decision trees have been used to represent controllers (a.k.a. policies) in an explainable way, with dtControl2 as a current state-of-the-art tool. However, for systems that are large or have many corner cases, even such representations tend to be too complex and not human-comprehensible. Unfortunately, reducing the size of the decision tree is not straightforward, as missing just a single crucial case might result in an incorrect controller. We tackle this issue in the setting of Markov decision processes, extending dtControl2 by "ε" functionality: Given an allowed imprecision ε ≥ 0, we construct a smaller decision tree, distilling the essence of the controller, while still guaranteeing its ε-optimality. This enables us to provide tunably simpler explanations, omitting a controllable amount of detail. Our tool constructs decision trees that are orders of magnitude smaller than the state of the art.

Citations

• Uppaal Coshy: Automatic Synthesis of Compact Shields for Hybrid Systems
• Explaining Control Policies through Predicate Decision Diagrams
• Fixed Point Certificates for Reachability and Expected Rewards in MDPs
• Small Decision Trees for MDPs with Deductive Synthesis
• Digging for Decision Trees: A Case Study in Strategy Sampling and Learning
• Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning
• Partial Exploration Tool 2.0
• Programmatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Programs
• Analyzing Intentional Behavior in Autonomous Agents under Uncertainty
• Guessing Winning Policies in LTL Synthesis by Semantic Learning
• A Practitioner's Guide to MDP Model Checking Algorithms
• Algebraically Explainable Controllers: Decision Trees and Support Vector Machines Join Forces
• Inductive Synthesis of Finite-State Controllers for POMDPs
• Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods
• A Unified Translation of Linear Temporal Logic to ω-Automata
• SWITSS: Computing Small Witnessing Subsystems
• The Probabilistic Model Checker Storm
• Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI
• Is a Good Representation Sufficient for Sample Efficient Reinforcement\n Learning?
• Verifiable Reinforcement Learning via Policy Extraction
• Programmatically Interpretable Reinforcement Learning
• An Automaton Learning Approach to Solving Safety Games over Infinite Graphs
• Policy Distillation
• Counterexample Explanation by Learning Small Strategies in Markov\n Decision Processes

Related

• Small Decision Trees for MDPs with Deductive Synthesis
• Policies Grow on Trees: Model Checking Families of MDPs
• SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes
• Explaining Control Policies through Predicate Decision Diagrams
• MDPs with Unawareness