# Optimal Decision Tree Policies for Markov Decision Processes

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 30 Jan 2023.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Verifiable Reinforcement Learning via Policy Extraction](https://mlsanity.com/paper/1805.08328/) (2018)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [A Survey on Interpretable Reinforcement Learning](https://mlsanity.com/paper/2112.13112/) (2021)
- [Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methods](https://mlsanity.com/paper/2102.13045/) (2021)
- [dtControl: Decision Tree Learning Algorithms for Controller Representation](https://mlsanity.com/paper/2002.04991/) (2020)
- [Robust Optimal Classification Trees Against Adversarial Examples](https://mlsanity.com/paper/2109.03857/) (2021)
- [Counterexample Explanation by Learning Small Strategies in Markov Decision Processes](https://mlsanity.com/paper/1502.02834/) (2015)

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

- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Breiman meets Bellman: Non-Greedy Decision Trees with MDPs](https://mlsanity.com/paper/2309.12701/) (2023)
- [Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization](https://mlsanity.com/paper/2408.08761/) (2024)
- [Explaining Control Policies through Predicate Decision Diagrams](https://mlsanity.com/paper/2503.06420/) (2025)
- [Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming for Policy Optimization in Mixed Discrete-Continuous MDPs](https://mlsanity.com/paper/2401.12243/) (2024)
- [SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes](https://mlsanity.com/paper/2510.19241/) (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)

Interpretability of reinforcement learning policies is essential for many real-world tasks but learning such interpretable policies is a hard problem. Particularly rule-based policies such as decision trees and rules lists are difficult to optimize due to their non-differentiability. While existing techniques can learn verifiable decision tree policies there is no guarantee that the learners generate a decision that performs optimally. In this work, we study the optimization of size-limited decision trees for Markov Decision Processes (MPDs) and propose OMDTs: Optimal MDP Decision Trees. Given a user-defined size limit and MDP formulation OMDT directly maximizes the expected discounted return for the decision tree using Mixed-Integer Linear Programming. By training optimal decision tree policies for different MDPs we empirically study the optimality gap for existing imitation learning techniques and find that they perform sub-optimally. We show that this is due to an inherent shortcoming of imitation learning, namely that complex policies cannot be represented using size-limited trees. In such cases, it is better to directly optimize the tree for expected return. While there is generally a trade-off between the performance and interpretability of machine learning models, we find that OMDTs limited to a depth of 3 often perform close to the optimal limit.