dtControl2+$\varepsilon$: Trading Optimality for Ex...

dtControl2+$\varepsilon$: Trading Optimality for Ex... | AI Research

Key Takeaways

dtControl2+$\varepsilon$: Trading Optimality for Explainability in MDPs via Decision Trees introduces a method to simplify complex decision trees used in Mar...
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.

Paper AbstractExpand

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 \geq 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.

dtControl2+$\varepsilon$: Trading Optimality for Explainability in MDPs via Decision Trees introduces a method to simplify complex decision trees used in Markov decision processes (MDPs). By allowing a small, controlled amount of imprecision, the tool creates significantly smaller and more human-comprehensible controllers while maintaining $\varepsilon$-optimality.

The Challenge of Complexity

Decision trees are frequently used to represent controllers in an explainable way, with the existing tool dtControl2 serving as the current state-of-the-art. However, these trees often become too complex for human understanding when applied to large systems or those with numerous corner cases. While reducing the size of these trees is desirable, it is technically difficult because omitting even a single critical case can result in an incorrect controller.

Introducing $\varepsilon$-Optimality

The authors address this by extending dtControl2 with "$\varepsilon$" functionality. This approach allows users to define an allowed imprecision, denoted as $\varepsilon \geq 0$. Instead of forcing the tree to be perfectly optimal, the tool constructs a smaller decision tree that distills the core logic of the controller while guaranteeing that it remains $\varepsilon$-optimal. This allows for "tunably simpler" explanations, where the user can choose to omit a specific, controllable amount of detail to improve readability.

Performance and Results

According to the authors, this new approach produces decision trees that are orders of magnitude smaller than those generated by current state-of-the-art methods. This reduction in size is achieved by trading off absolute optimality for a more concise and explainable representation of the controller.

Research Context

This work, titled "dtControl2+$\varepsilon$: Trading Optimality for Explainability in MDPs via Decision Trees," was authored by Tereza Kinská, Jan Křetínský, Tobias Meggendorfer, Sabine Rieder, and Maximilian Weininger. It has been accepted for presentation at the FMCAD26 conference.