# In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 5 Sep 2024.

## Builds on (most cited first, 7 of 7)

- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [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)
- [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)
- [Learning Interpretable, High-Performing Policies for Autonomous Driving](https://mlsanity.com/paper/2202.02352/) (2022)

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

- [Uppaal Coshy: Automatic Synthesis of Compact Shields for Hybrid Systems](https://mlsanity.com/paper/2508.16345/) (2025)

## Abstract (arXiv)

Decision trees, owing to their interpretability, are attractive as control policies for (dynamical) systems. Unfortunately, constructing, or synthesising, such policies is a challenging task. Previous approaches do so by imitating a neural-network policy, approximating a tabular policy obtained via formal synthesis, employing reinforcement learning, or modelling the problem as a mixed-integer linear program. However, these works may require access to a hard-to-obtain accurate policy or a formal model of the environment (within reach of formal synthesis), and may not provide guarantees on the quality or size of the final tree policy. In contrast, we present an approach to synthesise optimal decision-tree policies given a deterministic black-box environment and specification, a discretisation of the tree predicates, and an initial set of states, where optimality is defined with respect to the number of steps to achieve the goal. Our approach is a specialised search algorithm which systematically explores the (exponentially large) space of decision trees under the given discretisation. The key component is a novel trace-based pruning mechanism that significantly reduces the search space. Our approach represents a conceptually novel way of synthesising small decision-tree policies with optimality guarantees even for black-box environments with black-box specifications.