mlsanityData to 7 Oct 2026

Optimal Decision Tree Policies for Markov Decision Processes

arXiv 2301.13185 ↗First posted 30 Jan 2023cs.AI cs.LGcited by 8

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

Key facts. Cited by 8 papers in the map (data through 7 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.

Builds on

11 of 48 references.

References · 11

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  2. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  3. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  4. 2018Verifiable Reinforcement Learning via Policy Extractioncited by 176
  5. 2020Generalized and Scalable Optimal Sparse Decision Treescited by 98
  6. 2019Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Makingcited by 75
  7. 2021A Survey on Interpretable Reinforcement Learningcited by 70
  8. 2021Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methodscited by 31
  9. 2020dtControl: Decision Tree Learning Algorithms for Controller Representationcited by 12
  10. 2021Robust Optimal Classification Trees Against Adversarial Examplescited by 11
  11. 2015Counterexample Explanation by Learning Small Strategies in Markov Decision Processescited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 2; 2026: 2.

8 papers.

  1. 2024Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performancecited by 7
  2. 2023Breiman meets Bellman: Non-Greedy Decision Trees with MDPscited by 5
  3. 2024Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimizationcited by 5
  4. 2025Explaining Control Policies through Predicate Decision Diagramscited by 1
  5. 2024Constraint-Generation Policy Optimization (CGPO): Nonlinear Programming for Policy Optimization in Mixed Discrete-Continuous MDPscited by 0
  6. 2025SPOT: Scalable Policy Optimization with Trees for Markov Decision Processescited by 0
  7. 2026Explainably Safe Reinforcement Learningcited by 0
  8. 2026dtControl2+varepsilon: Trading Optimality for Explainability in MDPs via Decision Treescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Optimizing Interpretable Decision Tree Policies for Reinforcement Learning
  2. 2020CDT: Cascading Decision Trees for Explainable Reinforcement Learning
  3. 2024Solving Offline Reinforcement Learning with Decision Tree Regression
  4. 2025Learning Reward Machines from Partially Observed Policies
  5. 2024On the Convergence Rate of MCTS for the Optimal Value Estimation in Markov Decision Processes
  6. 2020Toward the Fundamental Limits of Imitation Learning
  7. 2020PAC Bounds for Imitation and Model-based Batch Learning of Contextual Markov Decision Processes
  8. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning