Chance and Mass Interpretations of Probabilities in Markov Decision Processes (Extended Version)

Introduction: Beyond the Coin Toss

Markov Decision Processes (MDPs) are fundamental to modeling decision-making under uncertainty. Traditionally, these models rely on a chance interpretation of probability. In this view, when a scheduler (the decision-maker) selects an action, the environment responds with a random transition—much like a coin toss—leading to a single subsequent state.

Expand

Source, p. 3

However, many real-world scenarios, particularly in robotics, biology, and resource management, are better described by a mass interpretation. Instead of a single agent moving between states, we might consider a swarm of robots or a concentration of chemicals. Here, probabilities represent how a "mass" is distributed across the state space. While reachability in chance-based MDPs is computationally straightforward, the mass-based equivalent is significantly more complex, often linked to unsolved mathematical problems like the Skolem problem.

A Unified Framework: The Chance-Mass Classifier

This research introduces the Chance-Mass (CM) classifier, a mathematical framework that allows for the systematic mixing of these interpretations. By distinguishing between the source of randomness (the scheduler vs. the environment) and its interpretation (chance vs. mass), the authors identify four distinct semantics:

1. (CS, CT) - Chance Scheduler, Chance Transition: The standard MDP model found in textbooks.
2. (MS, MT) - Mass Scheduler, Mass Transition: A "distribution transformer" view where both choices and outcomes split populations.
3. (CS, MT) - Chance Scheduler, Mass Transition: A new semantic where a random choice leads to a mass distribution.
4. (MS, CT) - Mass Scheduler, Chance Transition: A new semantic where a mass is split by the scheduler, but individual components face random outcomes.

Expand

Source, p. 3

Algorithmic Solutions for Reachability

The core contribution of this work is providing the first algorithms to solve reachability problems within these mixed semantics. Reachability—determining if a system can reach a target state with a certain probability—becomes a different beast under mass interpretations.

The (MS, CT) Semantics: Template-Based Synthesis

To handle the (MS, CT) case, the authors developed a template-based synthesis algorithm. This approach utilizes $\gamma$-scaled submartingales as mathematical certificates for reachability. The problem is translated into a system of polynomial inequalities, which can then be solved using automated reasoning tools like Z3. This method is particularly effective for modeling scenarios like a gambler (the "Casino" model) who splits their funds across multiple games with random outcomes.

The (CS, MT) Semantics: Antichain-Based Reachability

The (CS, MT) semantics presents a greater challenge, as the reachability problem in this domain is technically undecidable. To address this, the researchers implemented an antichain-based backward reachability algorithm. This solution is "sound but incomplete"—it can definitively confirm if a path exists, though it may not find every possible path.

Key Insights and Complexity

A major takeaway from this study is that the interpretation of randomness is not a monolith; the source and interpretation drastically alter the computational landscape. The paper formally proves that:

• (MS, CT) reachability is #P-hard, placing it in a complexity class associated with counting solutions.
• (CS, MT) reachability is undecidable under certain conditions, highlighting the inherent difficulty of mixing chance-based scheduling with mass transitions.

Experimental Results and Future Directions

The proposed algorithms were evaluated on several benchmark models, including pharmacokinetics simulations and new "Casino" and "Exam" models. Despite the theoretical hardness, the prototype implementation demonstrated practical feasibility for small-scale systems (3–5 states). Reachability certificates for (MS, CT) were typically found within a minute, while the (CS, MT) algorithm often succeeded in under 6 seconds.

While current scalability is limited to small models, this framework provides a rigorous foundation for future work. Potential applications include optimizing large-scale robotic swarms and exploring Quantum Markov Chains, where the interplay between mass and chance interpretations could offer novel insights into quantum state transitions.

@misc{tsai2025chance,
  author = {Yun Chen Tsai and Kittiphon Phalakarn and S. Akshay and Ichiro Hasuo},
  title = {{Chance and Mass Interpretations of Probabilities in Markov Decision Processes (Extended Version)}},
  year = {2025},
  eprint = {2506.10377},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.10377},
}