1-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913768999485440 |
|---|---|
| author | Azeem, Muqsit Chakraborty, Debraj Kanav, Sudeep Kretinsky, Jan Mohagheghi, Mohammadsadegh Mohr, Stefanie Weininger, Maximilian |
| author_facet | Azeem, Muqsit Chakraborty, Debraj Kanav, Sudeep Kretinsky, Jan Mohagheghi, Mohammadsadegh Mohr, Stefanie Weininger, Maximilian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18293 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | 1-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization Azeem, Muqsit Chakraborty, Debraj Kanav, Sudeep Kretinsky, Jan Mohagheghi, Mohammadsadegh Mohr, Stefanie Weininger, Maximilian Artificial Intelligence Machine Learning Logic in Computer Science Systems and Control 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. |
| title | 1-2-3-Go! Policy Synthesis for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization |
| topic | Artificial Intelligence Machine Learning Logic in Computer Science Systems and Control |
| url | https://arxiv.org/abs/2410.18293 |