mlsanityData to 14 Oct 2026

SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes

arXiv 2510.19241 ↗First posted 22 Oct 2025cs.LG cs.AIcited by 0

On the map: Deep reinforcement learning methods → Interpretable and logic-guided RL

Abstract (arXiv)

Interpretable reinforcement learning policies are essential for high-stakes decision-making, yet optimizing decision tree policies in Markov Decision Processes (MDPs) remains challenging. We propose SPOT, a novel method for computing decision tree policies, which formulates the optimization problem as a mixed-integer linear program (MILP). To enhance efficiency, we employ a reduced-space branch-and-bound approach that decouples the MDP dynamics from tree-structure constraints, enabling efficient parallel search. This significantly improves runtime and scalability compared to previous methods. Our approach ensures that each iteration yields the optimal decision tree. Experimental results on standard benchmarks demonstrate that SPOT achieves substantial speedup and scales to larger MDPs with a significantly higher number of states. The resulting decision tree policies are interpretable and compact, maintaining transparency without compromising performance. These results demonstrate that our approach simultaneously achieves interpretability and scalability, delivering high-quality policies an order of magnitude faster than existing approaches.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods. Builds on 8 of its 27 references that are in the map. First posted on arXiv 22 Oct 2025.

Builds on

8 of 27 references.

References · 8

  1. 2018Programmatically Interpretable Reinforcement Learningcited by 193
  2. 2018Verifiable Reinforcement Learning via Policy Extractioncited by 177
  3. 2019Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Makingcited by 75
  4. 2021A Survey on Interpretable Reinforcement Learningcited by 73
  5. 2020MurTree: Optimal Classification Trees via Dynamic Programming and Searchcited by 63
  6. 2021Iterative Bounding MDPs: Learning Interpretable Policies via Non-Interpretable Methodscited by 31
  7. 2020Efficient Training of Robust Decision Trees Against Adversarial Examplescited by 24
  8. 2023Optimal Decision Tree Policies for Markov Decision Processescited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search
  2. 2025Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead
  3. 2024Optimizing Interpretable Decision Tree Policies for Reinforcement Learning
  4. 2025TreePO: Bridging the Gap of Policy Optimization and Efficacy and Inference Efficiency with Heuristic Tree-based Modeling
  5. 2026SPOTting the Future: Lookahead Explanations for Deep Reinforcement Learning
  6. 2024Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization
  7. 2026Performance-Driven Environment Abstraction with Multi-Timescale Learning
  8. 2026CATPO: Critique-Augmented Tree Policy Optimization