Trace refinement in labelled Markov decision processes
Given two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Formáid: | Journal article |
| Foilsithe / Cruthaithe: |
European Joint Conferences on Theory and Practice of Software (ETAPS)
2015
|
| _version_ | 1826281193966927872 |
|---|---|
| author | Fijalkow, N Kiefer, S Shirmohammadi, M |
| author_facet | Fijalkow, N Kiefer, S Shirmohammadi, M |
| author_sort | Fijalkow, N |
| collection | OXFORD |
| description | Given two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if the second MDP is a Markov chain. The algorithm is based on new results on a particular notion of bisimulation between distributions over the states. However, we show that the general trace-refinement problem is undecidable, even if the first MDP is a Markov chain. Decidability of those problems has been open since 2008. We further study the decidability and complexity of the trace-refinement problem provided that the strategies are restricted to be memoryless. |
| first_indexed | 2024-03-07T00:25:08Z |
| format | Journal article |
| id | oxford-uuid:7de2f830-1e3b-45e6-a5bc-a4c3f8353a27 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:25:08Z |
| publishDate | 2015 |
| publisher | European Joint Conferences on Theory and Practice of Software (ETAPS) |
| record_format | dspace |
| spelling | oxford-uuid:7de2f830-1e3b-45e6-a5bc-a4c3f8353a272022-03-26T21:06:32ZTrace refinement in labelled Markov decision processesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7de2f830-1e3b-45e6-a5bc-a4c3f8353a27Symplectic Elements at OxfordEuropean Joint Conferences on Theory and Practice of Software (ETAPS)2015Fijalkow, NKiefer, SShirmohammadi, MGiven two labelled Markov decision processes (MDPs), the trace-refinement problem asks whether for all strategies of the first MDP there exists a strategy of the second MDP such that the induced labelled Markov chains are trace-equivalent. We show that this problem is decidable in polynomial time if the second MDP is a Markov chain. The algorithm is based on new results on a particular notion of bisimulation between distributions over the states. However, we show that the general trace-refinement problem is undecidable, even if the first MDP is a Markov chain. Decidability of those problems has been open since 2008. We further study the decidability and complexity of the trace-refinement problem provided that the strategies are restricted to be memoryless. |
| spellingShingle | Fijalkow, N Kiefer, S Shirmohammadi, M Trace refinement in labelled Markov decision processes |
| title | Trace refinement in labelled Markov decision processes |
| title_full | Trace refinement in labelled Markov decision processes |
| title_fullStr | Trace refinement in labelled Markov decision processes |
| title_full_unstemmed | Trace refinement in labelled Markov decision processes |
| title_short | Trace refinement in labelled Markov decision processes |
| title_sort | trace refinement in labelled markov decision processes |
| work_keys_str_mv | AT fijalkown tracerefinementinlabelledmarkovdecisionprocesses AT kiefers tracerefinementinlabelledmarkovdecisionprocesses AT shirmohammadim tracerefinementinlabelledmarkovdecisionprocesses |