通过动态精炼关键区域，加速大规模马尔可夫决策过程的策略生成。
Accelerating Policy Synthesis in Large-Scale MDPs via Hierarchical Adaptive Refinement
- 分层自适应精炼：只在最脆弱区域迭代优化
- 在100万状态的MDP上实现2倍于PRISM的加速
- 适合大规模软件系统与机器人决策问题
软件密集型系统（如软件产品线和机器人）常使用马尔可夫决策过程（MDPs）建模不确定性并分析序列决策问题。传统策略合成方法难以扩展到大状态空间。本文提出一种动态精炼MDP的分层自适应方法，通过迭代识别最脆弱区域进行局部优化，平衡精度与效率。理论证明，在标准假设下，组合策略近似最优，误差受局部求解器容差和边界不匹配限制。在涵盖多种场景的案例研究中，针对最大达100万状态的MDP，本方法相比PRISM最高提升2倍速度，为实际大规模策略合成提供高效解决方案。
原文摘要 · Abstract (English)
Software-intensive systems, such as software product lines and robotics, utilise Markov decision processes (MDPs) to capture uncertainty and analyse sequential decision-making problems. Despite the usefulness of conventional policy synthesis methods, they fail to scale to large state spaces. Our approach addresses this issue and accelerates policy synthesis in large MDPs by dynamically refining the MDP and iteratively selecting the most fragile MDP regions for refinement. This iterative procedure offers a balance between accuracy and efficiency, as refinement occurs only when necessary. We formally show that the composed policy is near-optimal under standard assumptions, with error bounded by the local solver tolerance and boundary mismatch. Across diverse case studies and MDPs up to 1M states, we demonstrate that our approach achieves up to $2\times$ speedup over PRISM, offering a competitive solution for real-world policy synthesis in large MDPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。