# Counterexample Explanation by Learning Small Strategies in Markov Decision Processes

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2015.

## Built on by (most cited first, 10 of 10)

- [dtControl 2.0: Explainable Strategy Representation via Decision Tree Learning Steered by Experts](https://mlsanity.com/paper/2101.07202/) (2021)
- [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)
- [Natural Strategic Ability in Stochastic Multi-Agent Systems](https://mlsanity.com/paper/2401.12170/) (2024)
- [Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs](https://mlsanity.com/paper/2503.00788/) (2025)
- [Explaining Control Policies through Predicate Decision Diagrams](https://mlsanity.com/paper/2503.06420/) (2025)
- [Explainable Representation of Finite-Memory Policies for POMDPs using Decision Trees](https://mlsanity.com/paper/2411.13365/) (2024)
- [Explaining Hitori Puzzles: Neurosymbolic Proof Staging for Sequential Decisions](https://mlsanity.com/paper/2508.14294/) (2025)
- [Explainably Safe Reinforcement Learning](https://mlsanity.com/paper/2606.04634/) (2026)
- [dtControl2+varepsilon: Trading Optimality for Explainability in MDPs via Decision Trees](https://mlsanity.com/paper/2607.25925/) (2026)

## Abstract (arXiv)

While for deterministic systems, a counterexample to a property can simply be an error trace, counterexamples in probabilistic systems are necessarily more complex. For instance, a set of erroneous traces with a sufficient cumulative probability mass can be used. Since these are too large objects to understand and manipulate, compact representations such as subchains have been considered. In the case of probabilistic systems with non-determinism, the situation is even more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism) is a straightforward choice, we take a different approach. Instead, we focus on the strategy - which can be a counterexample to violation of or a witness of satisfaction of a property - itself, and extract the most important decisions it makes, and present its succinct representation. The key tools we employ to achieve this are (1) introducing a concept of importance of a state w.r.t. the strategy, and (2) learning using decision trees. There are three main consequent advantages of our approach. Firstly, it exploits the quantitative information on states, stressing the more important decisions. Secondly, it leads to a greater variability and degree of freedom in representing the strategies. Thirdly, the representation uses a self-explanatory data structure. In summary, our approach produces more succinct and more explainable strategies, as opposed to e.g. binary decision diagrams. Finally, our experimental results show that we can extract several rules describing the strategy even for very large systems that do not fit in memory, and based on the rules explain the erroneous behaviour.