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

arXiv: https://arxiv.org/abs/2607.25925 · HTML: https://mlsanity.com/paper/2607.25925/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 31 of its 72 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 30 of 31)

- [Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI](https://mlsanity.com/paper/1910.10045/) (2019)
- [Policy Distillation](https://mlsanity.com/paper/1511.06295/) (2015)
- [A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAI](https://mlsanity.com/paper/1907.07374/) (2019)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods](https://mlsanity.com/paper/2102.13045/) (2021)
- [Interpretable and Editable Programmatic Tree Policies for Reinforcement Learning](https://mlsanity.com/paper/2405.14956/) (2024)
- [dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Experts](https://mlsanity.com/paper/2101.07202/) (2021)
- [dtControl: Decision Tree Learning Algorithms for Controller Representation](https://mlsanity.com/paper/2002.04991/) (2020)
- [Counterexample Explanation by Learning Small Strategies in Markov Decision Processes](https://mlsanity.com/paper/1502.02834/) (2015)
- [A Practitioner's Guide to MDP Model Checking Algorithms](https://mlsanity.com/paper/2301.10197/) (2023)
- [SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processes](https://mlsanity.com/paper/1906.10640/) (2019)
- [Inductive Synthesis of Finite-State Controllers for POMDPs](https://mlsanity.com/paper/2203.10803/) (2022)
- [Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm](https://mlsanity.com/paper/1804.04901/) (2018)
- [Optimal Decision Tree Policies for Markov Decision Processes](https://mlsanity.com/paper/2301.13185/) (2023)
- [Algebraically Explainable Controllers: Decision Trees and Support Vector Machines Join Forces](https://mlsanity.com/paper/2208.12804/) (2022)
- [1-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization](https://mlsanity.com/paper/2410.18293/) (2024)
- [Of Cores: A Partial-Exploration Framework for Markov Decision Processes](https://mlsanity.com/paper/1906.06931/) (2019)
- [Guessing Winning Policies in LTL Synthesis by Semantic Learning](https://mlsanity.com/paper/2305.15109/) (2023)
- [Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Games](https://mlsanity.com/paper/2405.03885/) (2024)
- [Small Decision Trees for MDPs with Deductive Synthesis](https://mlsanity.com/paper/2501.10126/) (2025)
- [An Automaton Learning Approach to Solving Safety Games over Infinite Graphs](https://mlsanity.com/paper/1601.01660/) (2016)
- [Analyzing Intentional Behavior in Autonomous Agents under Uncertainty](https://mlsanity.com/paper/2307.01532/) (2023)
- [Fixed Point Certificates for Reachability and Expected Rewards in MDPs](https://mlsanity.com/paper/2501.11467/) (2025)
- [SWITSS: Computing Small Witnessing Subsystems](https://mlsanity.com/paper/2008.04049/) (2020)
- [Programmatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Programs](https://mlsanity.com/paper/2311.06889/) (2023)
- [Explaining Control Policies through Predicate Decision Diagrams](https://mlsanity.com/paper/2503.06420/) (2025)

## Abstract (arXiv)

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 "varepsilon" functionality: Given an allowed imprecision varepsilon ≥ 0, we construct a smaller decision tree, distilling the essence of the controller, while still guaranteeing its varepsilon-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.