Exact sensitivity analysis of Markov reward processes via algebraic geometry
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909339893104640 |
|---|---|
| author | Chan, Timothy C. Y. Maaz, Muhammad |
| author_facet | Chan, Timothy C. Y. Maaz, Muhammad |
| contents | We introduce a new approach for deterministic sensitivity analysis of Markov reward processes, commonly used in cost-effectiveness analyses, via reformulation into a polynomial system. Our approach leverages cylindrical algebraic decomposition (CAD), a technique arising from algebraic geometry that provides an exact description of all solutions to a polynomial system. While it is typically intractable to build a CAD for systems with more than a few variables, we show that a special class of polynomial systems, which includes the polynomials arising from Markov reward processes, can be analyzed much more tractably. We establish several theoretical results about such systems and develop a specialized algorithm to construct their CAD, which allows us to perform exact, multi-way sensitivity analysis for common health economic analyses. We develop an open-source software package that implements our algorithm. Finally, we apply it to two case studies, one with synthetic data and one that re-analyzes a previous cost-effectiveness analysis from the literature, demonstrating advantages of our approach over standard techniques. Our software and code are available at: \url{https://github.com/mmaaz-git/markovag}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05471 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact sensitivity analysis of Markov reward processes via algebraic geometry Chan, Timothy C. Y. Maaz, Muhammad Optimization and Control Mathematical Software Algebraic Geometry Probability We introduce a new approach for deterministic sensitivity analysis of Markov reward processes, commonly used in cost-effectiveness analyses, via reformulation into a polynomial system. Our approach leverages cylindrical algebraic decomposition (CAD), a technique arising from algebraic geometry that provides an exact description of all solutions to a polynomial system. While it is typically intractable to build a CAD for systems with more than a few variables, we show that a special class of polynomial systems, which includes the polynomials arising from Markov reward processes, can be analyzed much more tractably. We establish several theoretical results about such systems and develop a specialized algorithm to construct their CAD, which allows us to perform exact, multi-way sensitivity analysis for common health economic analyses. We develop an open-source software package that implements our algorithm. Finally, we apply it to two case studies, one with synthetic data and one that re-analyzes a previous cost-effectiveness analysis from the literature, demonstrating advantages of our approach over standard techniques. Our software and code are available at: \url{https://github.com/mmaaz-git/markovag}. |
| title | Exact sensitivity analysis of Markov reward processes via algebraic geometry |
| topic | Optimization and Control Mathematical Software Algebraic Geometry Probability |
| url | https://arxiv.org/abs/2410.05471 |