Accelerating Policy Synthesis in Large-Scale MDPs via Hierarchical Adaptive Refinement
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911633924685824 |
|---|---|
| author | Evangelidis, Alexandros Vázquez, Gricel Gerasimou, Simos |
| author_facet | Evangelidis, Alexandros Vázquez, Gricel Gerasimou, Simos |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17792 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accelerating Policy Synthesis in Large-Scale MDPs via Hierarchical Adaptive Refinement Evangelidis, Alexandros Vázquez, Gricel Gerasimou, Simos Artificial Intelligence Logic in Computer Science Software Engineering 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. |
| title | Accelerating Policy Synthesis in Large-Scale MDPs via Hierarchical Adaptive Refinement |
| topic | Artificial Intelligence Logic in Computer Science Software Engineering |
| url | https://arxiv.org/abs/2506.17792 |