DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2025.33

Chance and Mass Interpretations of Probabilities in Markov Decision Processes

Authors: Yun Chen Tsai, Kittiphon Phalakarn, S. Akshay, and Ichiro Hasuo

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract

Markov decision processes (MDPs) are a popular model for decision-making in the presence of uncertainty. The conventional view of MDPs in verification treats them as state transformers with probabilities defined over sequences of states and with schedulers making random choices. An alternative view, especially well-suited for modeling dynamical systems, defines MDPs as distribution transformers with schedulers distributing probability masses. Our main contribution is a unified semantical framework that accommodates these two views and two new ones. These four semantics of MDPs arise naturally through identifying different sources of randomness in an MDP (namely schedulers, configurations, and transitions) and providing different ways of interpreting these probabilities (called the chance and mass interpretations). These semantics are systematically unified through a mathematical construct called chance-mass (CM) classifier. As another main contribution, we study a reachability problem in each of the two new semantics, demonstrating their hardness and providing two algorithms for solving them.

Cite as

Yun Chen Tsai, Kittiphon Phalakarn, S. Akshay, and Ichiro Hasuo. Chance and Mass Interpretations of Probabilities in Markov Decision Processes. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tsai_et_al:LIPIcs.CONCUR.2025.33,
  author =	{Tsai, Yun Chen and Phalakarn, Kittiphon and Akshay, S. and Hasuo, Ichiro},
  title =	{{Chance and Mass Interpretations of Probabilities in Markov Decision Processes}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.33},
  URN =		{urn:nbn:de:0030-drops-239838},
  doi =		{10.4230/LIPIcs.CONCUR.2025.33},
  annote =	{Keywords: MDP, distribution transformer, antichain, template-based synthesis}
}

Search Results

Documents authored by Tsai, Yun Chen

Chance and Mass Interpretations of Probabilities in Markov Decision Processes

Abstract

Cite as

Thanks for your feedback!

Could not send message