mlsanityData to 7 Oct 2026

Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet

arXiv 2411.11451 ↗First posted 18 Nov 2024cs.AI math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

Markov decision processes (MDPs) are a standard model for sequential decision-making problems and are widely used across many scientific areas, including formal methods and artificial intelligence (AI). MDPs do, however, come with the restrictive assumption that the transition probabilities need to be precisely known. Robust MDPs (RMDPs) overcome this assumption by instead defining the transition probabilities to belong to some uncertainty set. We present a gentle survey on RMDPs, providing a tutorial covering their fundamentals. In particular, we discuss RMDP semantics and how to solve them by extending standard MDP methods such as value iteration and policy iteration. We also discuss how RMDPs relate to other models and how they are used in several contexts, including reinforcement learning and abstraction techniques. We conclude with some challenges for future work on RMDPs.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 53 of its 121 references that are in the map. First posted on arXiv 18 Nov 2024.

Builds on

53 of 121 references.

References · 53

  1. 2019Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methodscited by 903
  2. 2020The Probabilistic Model Checker Stormcited by 64
  3. 2016Safe Policy Improvement by Minimizing Robust Baseline Regretcited by 51
  4. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  5. 2014Verification of Markov Decision Processes using Learning Algorithmscited by 38
  6. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  7. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 30
  8. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  9. 2021Risk-Averse Bayes-Adaptive Reinforcement Learningcited by 28
  10. 2020Robust Finite-State Controllers for Uncertain POMDPscited by 23
  11. 2021Automated Verification and Synthesis of Stochastic Hybrid Systems: A Surveycited by 20
  12. 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
38 more
  1. 2022Robust Anytime Learning of Markov Decision Processescited by 16
  2. 2023Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractionscited by 16
  3. 2019Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguitycited by 15
  4. 2019Parameter Synthesis for Markov Models: Covering the Parameter Spacecited by 14
  5. 2019StocHy: automated verification and synthesis of stochastic processescited by 13
  6. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  7. 2014Multiple-Environment Markov Decision Processescited by 12
  8. 2016Parameter Synthesis for Markov Models: Faster Than Evercited by 12
  9. 2023Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimalitycited by 12
  10. 2022Probabilities Are Not Enough: Formal Controller Synthesis for Stochastic Dynamical Models with Epistemic Uncertaintycited by 11
  11. 2018Synthesis in pMDPs: A Tale of 1001 Parameterscited by 10
  12. 2020The Complexity of Reachability in Parametric Markov Decision Processescited by 10
  13. 2020Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processescited by 10
  14. 2022Parameter Synthesis in Markov Models: A Gentle Surveycited by 10
  15. 2023Safe Policy Improvement for POMDPs via Finite-State Controllerscited by 10
  16. 2023Solving Long-run Average Reward Robust MDPs via Stochastic Gamescited by 10
  17. 2015Faster Statistical Model Checking for Unbounded Temporal Propertiescited by 9
  18. 2023A Practitioner's Guide to MDP Model Checking Algorithmscited by 9
  19. 2023More for Less: Safe Policy Improvement With Stronger Performance Guaranteescited by 9
  20. 2021Convex Optimization for Parameter Synthesis in MDPscited by 8
  21. 2021Scenario-Based Verification of Uncertain Parametric MDPscited by 8
  22. 2022HSVI can solve zero-sum Partially Observable Stochastic Gamescited by 8
  23. 2023Decision-Making Under Uncertainty: Beyond Probabilitiescited by 8
  24. 2023Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularizationcited by 8
  25. 2019Optimistic Value Iterationcited by 7
  26. 2022Constructing MDP Abstractions Using Data with Formal Guaranteescited by 7
  27. 2024Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPscited by 7
  28. 2024Pessimistic Iterative Planning with RNNs for Robust POMDPscited by 7
  29. 2017Sequential Convex Programming for the Efficient Verification of Parametric MDPscited by 6
  30. 2019Scenario-Based Verification of Uncertain MDPscited by 6
  31. 2018Sound Value Iterationcited by 5
  32. 2022Sampling-Based Verification of CTMCs with Uncertain Ratescited by 5
  33. 2024What Are the Odds? Improving the foundations of Statistical Model Checkingcited by 5
  34. 2023Robust Almost-Sure Reachability in Multi-Environment MDPscited by 4
  35. 2023Learning Robust Policies for Uncertain Parametric Markov Decision Processescited by 4
  36. 2024IMPaCT: Interval MDP Parallel Construction for Controller Synthesis of Large-Scale Stochastic Systemscited by 3
  37. 2024Sequential Decision-Making under Uncertainty: A Robust MDPs reviewcited by 2
  38. 2024Data-driven Interval MDP for Robust Control Synthesiscited by 2

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 9; 2026: 9.

18 papers.

Sort:

By area:

  1. 2026Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPscited by 5
  2. 2025Deep SPI: Safe Policy Improvement via World Modelscited by 3
  3. 2025A Theoretical Framework for Graph-based Digital Twins for Supply Chain Management and Optimizationcited by 2
  4. 2025Qualitative Analysis of ω-Regular Objectives on Robust MDPscited by 2
  5. 2025Data-Efficient Safe Policy Improvement Using Parametric Structurecited by 2
  6. 2025Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observabilitycited by 2
  7. 2025Supporting Dynamic Agentic Workloads: How Data and Agents Interactcited by 2
  8. 2026Robust Shielding for Safe Reinforcement Learningcited by 2
  9. 2025Best-Effort Policies for Robust Markov Decision Processescited by 1
  10. 2025Bayesian Ambiguity Contraction-based Adaptive Robust Markov Decision Processes for Adversarial Surveillance Missionscited by 1
  11. 2026Robust Parameter Learning for Uncertain MDPscited by 1
  12. 2025AI Agents and Hard Choicescited by 0
6 more
  1. 2026Safety Certification is Classificationcited by 0
  2. 2026Property-driven Causal Abstractions for Markov Decision Processescited by 0
  3. 2026Adaptive Probabilistic Shielding by Learning MDPs for Safe Reinforcement Learningcited by 0
  4. 2026Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Gamescited by 0
  5. 2026Robust PAC Learning of Concurrent Stochastic Gamescited by 0
  6. 2026Bellman-Certified Rounding for Sparse Policy Deployment in MDPscited by 0