mlsanityData to 7 Oct 2026

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

arXiv 2206.01465 ↗First posted 3 Jun 2022eess.SY cs.LG cs.SYcited by 4

Not on the map. Why?

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.

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

Builds on

13 of 60 references.

References · 13

  1. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 74
  2. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 53
  3. 2014Verification of Markov Decision Processes using Learning Algorithmscited by 38
  4. 2017A storm is Coming: A Modern Probabilistic Model Checkercited by 34
  5. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 30
  6. 2015Faster Statistical Model Checking for Unbounded Temporal Propertiescited by 9
  7. 2018Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithmcited by 8
  8. 2018Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraintscited by 8
  9. 2017Value Iteration for Long-run Average Reward in Markov Decision Processescited by 7
  10. 2018Safe Reinforcement Learning via Probabilistic Shieldscited by 7
  11. 2021Mungojerrie: Reinforcement Learning of Linear-Time Objectivescited by 6
  12. 2013Modelling, Reduction and Analysis of Markov Automata (extended version)cited by 1
1 more
  1. 2017Markov Automata with Multiple Objectivescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 0; 2026: 1.

4 papers.

  1. 2024What Are the Odds? Improving the foundations of Statistical Model Checkingcited by 5
  2. 2024Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Gamescited by 4
  3. 2023Efficient Sensitivity Analysis for Parametric Robust Markov Chainscited by 2
  4. 2026Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guaranteescited by 0