用决策树学习小模型最优策略，推广到超大规模马尔可夫决策过程。
1-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization
- 通过小规模实例的最优策略，用决策树学习泛化到更大模型。
- 实验表明策略在超大规模模型上表现良好，超出现有工具处理能力。
- 适合需要高效策略合成但状态空间爆炸的验证场景。
尽管概率模型检测技术已有进展，其可扩展性仍受限。当参数化马尔可夫决策过程（MDPs）实例化时，即使参数值适中，状态空间也会变得极其庞大，导致现有工具无法处理此类超大规模MDP的策略合成。本文提出一种基于学习的方法，通过模型检测获取小规模实例的最优策略，并利用决策树学习将其泛化至更大规模模型。该方法避免了对大规模模型进行显式状态空间探索，为解决状态空间爆炸问题提供了实用方案。我们在定量验证基准集的相关模型上进行了大量实验，结果表明，所生成策略在模型规模远超当前先进分析工具处理范围的情况下仍表现优异。
原文摘要 · Abstract (English)
Despite the advances in probabilistic model checking, the scalability of the verification methods remains limited. In particular, the state space often becomes extremely large when instantiating parameterized Markov decision processes (MDPs) even with moderate values. Synthesizing policies for such \emph{huge} MDPs is beyond the reach of available tools. We propose a learning-based approach to obtain a reasonable policy for such huge MDPs. The idea is to generalize optimal policies obtained by model-checking small instances to larger ones using decision-tree learning. Consequently, our method bypasses the need for explicit state-space exploration of large models, providing a practical solution to the state-space explosion problem. We demonstrate the efficacy of our approach by performing extensive experimentation on the relevant models from the quantitative verification benchmark set. The experimental results indicate that our policies perform well, even when the size of the model is orders of magnitude beyond the reach of state-of-the-art analysis tools.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。