SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes
This work addresses the need for interpretable reinforcement learning policies in high-stakes decision-making, offering a scalable solution that is incremental in improving efficiency over previous methods.
The paper tackles the challenge of optimizing interpretable decision tree policies in Markov Decision Processes (MDPs) by proposing SPOT, a method that formulates it as a mixed-integer linear program and uses a reduced-space branch-and-bound approach, achieving substantial speedup and scalability to larger MDPs with significantly higher state counts.
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.