# Robust Anytime Learning of Markov Decision Processes

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 63 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [The Importance of Pessimism in Fixed-Dataset Policy Optimization](https://mlsanity.com/paper/2009.06799/) (2020)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPs](https://mlsanity.com/paper/1902.07605/) (2019)
- [A Bayesian Approach to Robust Reinforcement Learning](https://mlsanity.com/paper/1905.08188/) (2019)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Robust Markov Decision Process: Beyond Rectangularity](https://mlsanity.com/paper/1811.00215/) (2018)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes](https://mlsanity.com/paper/2012.04626/) (2020)
- [A Channel-Based Perspective on Conjugate Priors](https://mlsanity.com/paper/1707.00269/) (2017)
- [Active Learning of Markov Decision Processes using Baum-Welch algorithm (Extended)](https://mlsanity.com/paper/2110.03014/) (2021)

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

- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [A CMDP-within-online framework for Meta-Safe Reinforcement Learning](https://mlsanity.com/paper/2405.16601/) (2024)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Certifiably Robust Policies for Uncertain Parametric Environments](https://mlsanity.com/paper/2408.03093/) (2024)
- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [Formally Verifying and Explaining Sepsis Treatment Policies with COOL-MC](https://mlsanity.com/paper/2602.14505/) (2026)
- [Efficient Sensitivity Analysis for Parametric Robust Markov Chains](https://mlsanity.com/paper/2305.01473/) (2023)
- [Robust Shielding for Safe Reinforcement Learning](https://mlsanity.com/paper/2606.00270/) (2026)
- [Strategy Synthesis in Markov Decision Processes Under Limited Sampling Access](https://mlsanity.com/paper/2303.12718/) (2023)
- [Robust Parameter Learning for Uncertain MDPs](https://mlsanity.com/paper/2605.01339/) (2026)
- [Smart Exploration in Reinforcement Learning using Bounded Uncertainty Models](https://mlsanity.com/paper/2504.05978/) (2025)
- [COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Management](https://mlsanity.com/paper/2603.02396/) (2026)
- [Safety Certification is Classification](https://mlsanity.com/paper/2605.06087/) (2026)
- [Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees](https://mlsanity.com/paper/2606.29681/) (2026)
- [Adaptive Probabilistic Shielding by Learning MDPs for Safe Reinforcement Learning](https://mlsanity.com/paper/2608.19836/) (2026)

## Abstract (arXiv)

Markov decision processes (MDPs) are formal models commonly used in sequential decision-making. MDPs capture the stochasticity that may arise, for instance, from imprecise actuators via probabilities in the transition function. However, in data-driven applications, deriving precise probabilities from (limited) data introduces statistical errors that may lead to unexpected or undesirable outcomes. Uncertain MDPs (uMDPs) do not require precise probabilities but instead use so-called uncertainty sets in the transitions, accounting for such limited data. Tools from the formal verification community efficiently compute robust policies that provably adhere to formal specifications, like safety constraints, under the worst-case instance in the uncertainty set. We continuously learn the transition probabilities of an MDP in a robust anytime-learning approach that combines a dedicated Bayesian inference scheme with the computation of robust policies. In particular, our method (1) approximates probabilities as intervals, (2) adapts to new data that may be inconsistent with an intermediate model, and (3) may be stopped at any time to compute a robust policy on the uMDP that faithfully captures the data so far. Furthermore, our method is capable of adapting to changes in the environment. We show the effectiveness of our approach and compare it to robust policies computed on uMDPs learned by the UCRL2 reinforcement learning algorithm in an experimental evaluation on several benchmarks.