# Best-Effort Policies for Robust Markov Decision Processes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 32 references that are in the map.
- First posted on arXiv 11 Aug 2025.

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

- [Model-based Reinforcement Learning: A Survey](https://mlsanity.com/paper/2006.16712/) (2020)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Parameter Synthesis for Markov Models: Covering the Parameter Space](https://mlsanity.com/paper/1903.07993/) (2019)
- [Parameter Synthesis for Markov Models: Faster Than Ever](https://mlsanity.com/paper/1602.05113/) (2016)
- [Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularization](https://mlsanity.com/paper/2309.01107/) (2023)
- [Simple Strategies in Multi-Objective MDPs (Technical Report)](https://mlsanity.com/paper/1910.11024/) (2019)
- [Are Parametric Markov Chains Monotonic?](https://mlsanity.com/paper/1907.08491/) (2019)
- [The Complexity of Graph-Based Reductions for Reachability in Markov Decision Processes](https://mlsanity.com/paper/1710.07903/) (2017)

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

- [Bellman-Certified Rounding for Sparse Policy Deployment in MDPs](https://mlsanity.com/paper/2610.00325/) (2026)

## Abstract (arXiv)

We study the common generalization of Markov decision processes (MDPs) with sets of transition probabilities, known as robust MDPs (RMDPs). A standard goal in RMDPs is to compute a policy that maximizes the expected return under an adversarial choice of the transition probabilities. If the uncertainty in the probabilities is independent between the states, known as s-rectangularity, such optimal robust policies can be computed efficiently using robust value iteration. However, there might still be multiple optimal robust policies, which, while equivalent with respect to the worst-case, reflect different expected returns under non-adversarial choices of the transition probabilities. Hence, we propose a refined policy selection criterion for RMDPs, drawing inspiration from the notions of dominance and best-effort in game theory. Instead of seeking a policy that only maximizes the worst-case expected return, we additionally require the policy to achieve a maximal expected return under different (i.e., not fully adversarial) transition probabilities. We call such a policy an optimal robust best-effort (ORBE) policy. We prove that ORBE policies always exist, characterize their structure, and present an algorithm to compute them with a manageable overhead compared to standard robust value iteration. ORBE policies offer a principled tie-breaker among optimal robust policies. Numerical experiments show the feasibility of our approach.