用混合整数规划优化决策树策略，让强化学习更可解释且更快。
SPOT: Scalable Policy Optimization with Trees for Markov Decision Processes
- 将决策树策略优化转化为混合整数线性规划问题
- 在标准基准上实现比现有方法快一个数量级的求解速度
- 适合需要可解释性与高扩展性的高风险决策场景
可解释的强化学习策略对高风险决策至关重要，但马尔可夫决策过程（MDPs）中决策树策略的优化仍具挑战。本文提出SPOT，一种计算决策树策略的新方法，将优化问题建模为混合整数线性规划（MILP）。为提升效率，采用降维空间的分支定界法，将MDP动态与树结构约束解耦，支持高效并行搜索，显著提升运行速度与可扩展性。每次迭代均产出最优决策树。在标准基准上的实验表明，SPOT实现显著加速，可处理状态数更多的大型MDP。生成的决策树策略兼具可解释性与紧凑性，在不牺牲性能的前提下保持透明性。结果表明，该方法同时实现了可解释性与可扩展性，以比现有方法快一个数量级的速度输出高质量策略。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。