Exact sensitivity analysis of Markov reward processes via algebraic geometry
<|reference_start|>Exact sensitivity analysis of Markov reward processes via algebraic geometry: 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}.<|reference_end|>
@article{chan2024exact,
    title={Exact sensitivity analysis of Markov reward processes via algebraic
  geometry},
    author={Timothy C. Y. Chan, Muhammad Maaz},
    journal={arXiv preprint arXiv:2410.05471},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.05471},
    primaryClass={math.OC cs.MS math.AG math.PR}
}