mlsanityData to 14 Oct 2026

PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games

arXiv 1905.04403 ↗First posted 10 May 2019eess.SY cs.LG cs.SYcited by 32

Not on the map. Why?

Abstract (arXiv)

Statistical model checking (SMC) is a technique for analysis of probabilistic systems that may be (partially) unknown. We present an SMC algorithm for (unbounded) reachability yielding probably approximately correct (PAC) guarantees on the results. We consider both the setting (i) with no knowledge of the transition function (with the only quantity required a bound on the minimum transition probability) and (ii) with knowledge of the topology of the underlying graph. On the one hand, it is the first algorithm for stochastic games. On the other hand, it is the first practical algorithm even for Markov decision processes. Compared to previous approaches where PAC guarantees require running times longer than the age of universe even for systems with a handful of states, our algorithm often yields reasonably precise results within minutes, not requiring the knowledge of mixing time or the topology of the whole model.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). First posted on arXiv 10 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 4; 2023: 9; 2024: 4; 2025: 1; 2026: 10.

32 papers.

Sort:

By area:

  1. 2021Multi-Agent Reinforcement Learning with Temporal Logic Specificationscited by 27
  2. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  3. 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
  4. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meetcited by 18
  5. 2022Robust Anytime Learning of Markov Decision Processescited by 16
  6. 2023Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractionscited by 16
  7. 2023Policy Synthesis and Reinforcement Learning for Discounted LTLcited by 14
  8. 2021Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noisecited by 13
  9. 2023Computably Continuous Reinforcement-Learning Objectives are PAC-learnablecited by 13
  10. 2023A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPscited by 13
  11. 2023Decision-Making Under Uncertainty: Beyond Probabilitiescited by 9
  12. 2023Monitoring Algorithmic Fairnesscited by 8
20 more
  1. 2023Monitoring Algorithmic Fairness under Partial Observationscited by 7
  2. 2024Certifiably Robust Policies for Uncertain Parametric Environmentscited by 7
  3. 2024What Are the Odds? Improving the foundations of Statistical Model Checkingcited by 5
  4. 2022PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDPcited by 4
  5. 2021Learning Optimal Strategies for Temporal Tasks in Stochastic Gamescited by 3
  6. 2024On the Uniqueness of Solution for the Bellman Equation of LTL Objectivescited by 3
  7. 2023Efficient Sensitivity Analysis for Parametric Robust Markov Chainscited by 2
  8. 2023Strategy Synthesis in Markov Decision Processes Under Limited Sampling Accesscited by 1
  9. 2026Robust Parameter Learning for Uncertain MDPscited by 1
  10. 2022Reinforcement Causal Structure Learning on Order Graphcited by 0
  11. 2025Monitoring of Static Fairnesscited by 0
  12. 2026Resilient Strategies for Stochastic Systems: How Much Does It Take to Break a Winning Strategy?cited by 0
  13. 2026Missingness-MDPs: Bridging the Theory of Missing Data and POMDPscited by 0
  14. 2026Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimalitycited by 0
  15. 2026Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guaranteescited by 0
  16. 2026PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distancecited by 0
  17. 2026Exact Model-Free Policy Iteration for Co-safe LTL Planningcited by 0
  18. 2026Adaptive Probabilistic Shielding by Learning MDPs for Safe Reinforcement Learningcited by 0
  19. 2026Q-Learning for Reachability in MEC-Free MDPscited by 0
  20. 2026Certifying Almost-Sure Reachability in Unknown MDPscited by 0