mlsanityData to 7 Oct 2026

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

arXiv 2607.25925 ↗First posted 28 Jul 2026cs.AIcited by 0

Not on the map. Why?

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.

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

Builds on

31 of 72 references.

References · 31

  1. 2019Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AIcited by 1,543
  2. 2015Policy Distillationcited by 414
  3. 2019A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAIcited by 403
  4. 2018Programmatically Interpretable Reinforcement Learningcited by 192
  5. 2018Verifiable Reinforcement Learning via Policy Extractioncited by 176
  6. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  7. 2020The Probabilistic Model Checker Stormcited by 64
  8. 2020MurTree: Optimal Classification Trees via Dynamic Programming and Searchcited by 61
  9. 2021Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methodscited by 31
  10. 2024Interpretable and Editable Programmatic Tree Policies for Reinforcement Learningcited by 18
  11. 2021dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Expertscited by 14
  12. 2020dtControl: Decision Tree Learning Algorithms for Controller Representationcited by 12
19 more
  1. 2015Counterexample Explanation by Learning Small Strategies in Markov Decision Processescited by 10
  2. 2019SOS: Safe, Optimal and Small Strategies for Hybrid Markov Decision Processescited by 9
  3. 2023A Practitioner's Guide to MDP Model Checking Algorithmscited by 9
  4. 2018Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithmcited by 8
  5. 2022Inductive Synthesis of Finite-State Controllers for POMDPscited by 8
  6. 2023Optimal Decision Tree Policies for Markov Decision Processescited by 8
  7. 2022Algebraically Explainable Controllers: Decision Trees and Support Vector Machines Join Forcescited by 5
  8. 20241-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalizationcited by 5
  9. 2019Of Cores: A Partial-Exploration Framework for Markov Decision Processescited by 4
  10. 2023Guessing Winning Policies in LTL Synthesis by Semantic Learningcited by 4
  11. 2024Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Gamescited by 4
  12. 2025Small Decision Trees for MDPs with Deductive Synthesiscited by 3
  13. 2016An Automaton Learning Approach to Solving Safety Games over Infinite Graphscited by 2
  14. 2023Analyzing Intentional Behavior in Autonomous Agents under Uncertaintycited by 2
  15. 2025Fixed Point Certificates for Reachability and Expected Rewards in MDPscited by 2
  16. 2020SWITSS: Computing Small Witnessing Subsystemscited by 1
  17. 2023Programmatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Programscited by 1
  18. 2025Explaining Control Policies through Predicate Decision Diagramscited by 1
  19. 2025Uppaal Coshy: Automatic Synthesis of Compact Shields for Hybrid Systemscited by 1

Built on by

Not cited yet.