Algorithmic minimization of uncertain continuous-time Markov chains
The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. Here we consider uncertain CTMCs (UCTMCs), where rates are assumed to va...
| Main Authors: | , , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
IEEE
2023
|
| _version_ | 1797111694997061632 |
|---|---|
| author | Cardelli, L Grosu, R Larsen, KG Tribastone, M Tschaikowski, M Vandin, A |
| author_facet | Cardelli, L Grosu, R Larsen, KG Tribastone, M Tschaikowski, M Vandin, A |
| author_sort | Cardelli, L |
| collection | OXFORD |
| description | The assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. Here we consider uncertain CTMCs (UCTMCs), where rates are assumed to vary non-deterministically with time from bounded continuous intervals. An uncertain CTMC can be therefore seen as a specific type of Markov decision process for which the analysis is computationally difficult. To tackle this, we develop a theory of minimization which generalizes the notion of lumpability for CTMCs. Our first result is a quantitative and logical characterization of minimization. Specifically, we show that the reduced UCTMC model has a macro-state for each block of a partition of the state space, which preserves value functions and logical formulae whenever rewards are equal within each block. The second result is an efficient minimization algorithm for UCTMCs by means of partition refinement. As application, we show that reductions in a number of CTMCbenchmark models are robust with respect to uncertainties in original rates. |
| first_indexed | 2024-03-07T08:13:55Z |
| format | Journal article |
| id | oxford-uuid:494894ee-3d77-45e9-a7ba-c6c26609fd4b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:13:55Z |
| publishDate | 2023 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:494894ee-3d77-45e9-a7ba-c6c26609fd4b2023-12-12T15:34:09ZAlgorithmic minimization of uncertain continuous-time Markov chainsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:494894ee-3d77-45e9-a7ba-c6c26609fd4bEnglishSymplectic ElementsIEEE2023Cardelli, LGrosu, RLarsen, KGTribastone, MTschaikowski, MVandin, AThe assumption of perfect knowledge of rate parameters in continuous-time Markov chains (CTMCs) is undermined when confronted with reality, where they may be uncertain due to lack of information or because of measurement noise. Here we consider uncertain CTMCs (UCTMCs), where rates are assumed to vary non-deterministically with time from bounded continuous intervals. An uncertain CTMC can be therefore seen as a specific type of Markov decision process for which the analysis is computationally difficult. To tackle this, we develop a theory of minimization which generalizes the notion of lumpability for CTMCs. Our first result is a quantitative and logical characterization of minimization. Specifically, we show that the reduced UCTMC model has a macro-state for each block of a partition of the state space, which preserves value functions and logical formulae whenever rewards are equal within each block. The second result is an efficient minimization algorithm for UCTMCs by means of partition refinement. As application, we show that reductions in a number of CTMCbenchmark models are robust with respect to uncertainties in original rates. |
| spellingShingle | Cardelli, L Grosu, R Larsen, KG Tribastone, M Tschaikowski, M Vandin, A Algorithmic minimization of uncertain continuous-time Markov chains |
| title | Algorithmic minimization of uncertain continuous-time Markov chains |
| title_full | Algorithmic minimization of uncertain continuous-time Markov chains |
| title_fullStr | Algorithmic minimization of uncertain continuous-time Markov chains |
| title_full_unstemmed | Algorithmic minimization of uncertain continuous-time Markov chains |
| title_short | Algorithmic minimization of uncertain continuous-time Markov chains |
| title_sort | algorithmic minimization of uncertain continuous time markov chains |
| work_keys_str_mv | AT cardellil algorithmicminimizationofuncertaincontinuoustimemarkovchains AT grosur algorithmicminimizationofuncertaincontinuoustimemarkovchains AT larsenkg algorithmicminimizationofuncertaincontinuoustimemarkovchains AT tribastonem algorithmicminimizationofuncertaincontinuoustimemarkovchains AT tschaikowskim algorithmicminimizationofuncertaincontinuoustimemarkovchains AT vandina algorithmicminimizationofuncertaincontinuoustimemarkovchains |