# PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP

arXiv: https://arxiv.org/abs/2206.01465 · HTML: https://mlsanity.com/paper/2206.01465/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 60 references that are in the map.
- First posted on arXiv 3 Jun 2022.

## Builds on (most cited first, 13 of 13)

- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [A storm is Coming: A Modern Probabilistic Model Checker](https://mlsanity.com/paper/1702.04311/) (2017)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Faster Statistical Model Checking for Unbounded Temporal Properties](https://mlsanity.com/paper/1504.05739/) (2015)
- [Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm](https://mlsanity.com/paper/1804.04901/) (2018)
- [Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints](https://mlsanity.com/paper/1804.08924/) (2018)
- [Value Iteration for Long-run Average Reward in Markov Decision Processes](https://mlsanity.com/paper/1705.02326/) (2017)
- [Safe Reinforcement Learning via Probabilistic Shields](https://mlsanity.com/paper/1807.06096/) (2018)
- [Mungojerrie: Reinforcement Learning of Linear-Time Objectives](https://mlsanity.com/paper/2106.09161/) (2021)
- [Modelling, Reduction and Analysis of Markov Automata (extended version)](https://mlsanity.com/paper/1305.7050/) (2013)
- [Markov Automata with Multiple Objectives](https://mlsanity.com/paper/1704.06648/) (2017)

## Built on by (most cited first, 4 of 4)

- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Games](https://mlsanity.com/paper/2405.03885/) (2024)
- [Efficient Sensitivity Analysis for Parametric Robust Markov Chains](https://mlsanity.com/paper/2305.01473/) (2023)
- [Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees](https://mlsanity.com/paper/2606.29681/) (2026)

## Abstract (arXiv)

Markov decision processes (MDP) and continuous-time MDP (CTMDP) are the fundamental models for non-deterministic systems with probabilistic uncertainty. Mean payoff (a.k.a. long-run average reward) is one of the most classic objectives considered in their context. We provide the first algorithm to compute mean payoff probably approximately correctly in unknown MDP; further, we extend it to unknown CTMDP. We do not require any knowledge of the state space, only a lower bound on the minimum transition probability, which has been advocated in literature. In addition to providing probably approximately correct (PAC) bounds for our algorithm, we also demonstrate its practical nature by running experiments on standard benchmarks.